프로그래밍과 수학 프로그래밍과 수학

1. 카프리카 상수란 인도 수학자인 D.R.카프리카가 발견한 숫자이다.base(진수)와 digit(자리수)에 따라정수의 자릿수를 내림차순으로 정렬한 정수 - 올림차순으로 정렬한 정수 = 기존 정수를 만족하는 수를 카프리카 상수라고 한다.(단 모든 자릿수가 같아서는 안된다.)간단하게 예를 보자. base가 10, digit이 4라고 정해져있다고 하자.그러면 0000 ~ 9999까지 정수가 있을 것이다. 하지만 조건에 의해 모든 자릿수가 같으면 안되므로 0000 1111 2222 ~ 9999 같은 자릿수 4개가 모두 동일한 수는 제외한다.이 정수중에서 하나인 2134를 뽑았다하면,2134의 자릿수를 내림차순으로 정렬한 정수인 4321 오름차순으로 정렬한 정수인 1234 이 둘의 차는 3087이다.3087은 ..

1. 칸터 표현이란.. 기본적으로 10진수 8진수 등등과 달리 FACTORIAL을 이용해 수를 표현하는 것이다. 어떤 10진수 x가 있다면 이 x는 다음과 같이 유일무이하게 표현할 수 있다. 이를 10진수 2진수처럼 표현하기 위해 두가지를 증명해야한다. 1. 모든 정수를 cantor expression으로 표현할 수 있다.2. 그 표현은 유일하다(unique) 이 두가지 증명은 따로 하지 않겠다. ( 기존 진수 표현 증명과 비슷하다. ) 2. 칸터 표현 프로그램다음 프로그램은 정수를(10진수) 형태로 집어 넣으면 그 정수를 cantor 표현으로 바꿔주는 프로그램이다. 예제 입력312예제 출력2*5! + 3*4! + 0*3! + 0*2! + 0*1! Colored By Color Scripter™12345..

앞서 올린 big_integer_operation 프로그램으로 구한 피보나치 수열 10만항 25974069347221724166155034021275915414880485386517696584724770703952534543511273686265556772836716744754637587223074432111638399473875091030965697382188304493052287638531334921353026792789567010512765782716356080730505322002432331143839865161378272381247774537783372999162146340500546698603908627509966393664092118901252719601721050603003505868940..

1. 님 게임의 규칙 님(Nim)은 수학적 전략 보드 게임이다. 몇개의 줄에 숫자나 자연수개의 돌을 두고 순서대로 돌아가면서 한 줄에서 정해진 수의 숫자를 제거한다. 가져오는 숫자에는 상한이 있으며 무조건 1개는 가져와야 한다. 마지막 돌을 가져오는 사람이 이긴다. 2. 님 게임의 필승 전략 일단 박스에 담겨져 있는 구슬을 2진수화 한다. 예를 들어 박스 2개에 구슬이 각각 3, 2개가 들어 있다면 0 1 1 : 3개 0 1 0 : 2개 이때 각 열(column)의 1의 개수가 짝수라면 (0도 짝수에 포함) 이를 상태 A라 하자. 짝수가 아닌게 적어도 하나가 있다면 상태 ~A 라 하자. 위 예제는 상태 ~A이다. 따라서 필승전략을 하려면 다음 두가지 조건을 증명해야한다. 1. 상태 A에서 아무 박스에서 ..

int 보다 큰 범위의 정수들을 기본연산해주는 함수들이다. (음수 연산 가능) 기본 원리는 int 연산과 같다. 그러나 int는 32개의 bit라면 이 big_int는 32 * size 개의 bit이다. size가 1000이라면 약 자릿수 10000자리정도까지 계산 가능하다. main 함수에 적혀있는 것은 fibonacci 수열의 10만항을 구하도록 예제를 적어놓았다. size가 클 수록 연산의 속도가 눈에 띄게 감소한다. Colored By Color Scripter™ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 ..

수학적 귀납법은 고등학교 교육과정 때 많이 배웠을 것이다. 그러나 정수론에서 다루는 수학적 귀납법의 정의는 다소 낯설 수도 있지만 본질은 같다. 즉, 1) 양의 정수 집합 S가 1을 포함하고 있는지. 2) 양의 정수 집합 S가 양의 정수 k를 포함하고 있다면 k+1을 포함하고 있는지. 이 두 조건을 만족한다면 집합 S는 무조건 모든 양의 정수 집합일 수 밖에 없다는 뜻이다. 예를 한번 들어보자. 우리는 이제 Mathematical Induction을 The well ordering property를 이용해 보일 것이다. 지금 까지 살펴본 Mathematical Induction과 비슷하지만 더 강력한 버전이 존재한다. 이를 The Second Principle of Mathematical Inductio..

디리클레 근사를 살펴보기전에 "비둘기 집의 원리" 부터 살펴보기로 한다. 증명은 매우 자명하다. 만약 어느 박스에도 2개이상의 물체가 들어가지 않았다면, 최대 물체 개수는 k개로 모순이 된다. 이제 디리클레 근사를 살펴보도록 한다. 이 디리클레 근사는 비둘기집 원리를 증명에 이용하는 정리로 유명하나, 무리수를 유리수로 근사하는데도 유용하다. Colored By Color Scripter™ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 //이 프로그램은 단순한 제곱근의 디리클레 근사를 구하는 프로그램입니다. #include #include int main() { double D; int ..