Dirichlet Approximation Theorem (디리클레 근사)

디리클레 근사를 살펴보기전에 "비둘기 집의 원리" 부터 살펴보기로 한다.

증명은 매우 자명하다. 만약 어느 박스에도 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 <stdio.h> #include <math.h>   int main() {     double D;     int a = 0, b;     double n;     double sqrt_D;       printf("We will get Dirichlet Approximation of root of D\n");     printf("Please input the positive integer D : ");     scanf("%lf", &D);     printf("Please input the positive integer n : ");     scanf("%lf", &n);       sqrt_D = sqrt((double)D);       do     {         a++;         b = 1;         while (fabs(a*sqrt_D - b) >= 1)             b++;     } while (fabs(a*sqrt_D - b) >= 1/n);       printf("a : %d b: %d\n", a, b);     printf("Real value = %.6lf\n", sqrt_D);     printf("Approximation value = %.6lf (tolerance %.6lf)\n", (double)b / (double)a, 1 / (double)(n*a));       return 0; }