I00022 孙子定理

男娘i 2021-12-21 05:31 175阅读 0赞

问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？答曰：二十三。

这个问题用现在的话说就是，有一个数，用3除余2，用5除余3，用7除余2，问该数是多少？

该问题最早可见于中国南北朝时期（公元5世纪）的数学著作[《孙子算经》卷下][Link 1]第二十六题。是一个数学问题，更准确地说是一个数论问题，也是一个经典的数论问题。

孙子定理是中国古代求解一次同余式组的方法，是数论四大定理之一，国际上称为中国剩余定理。该题是孙子定理中的典型问题。

现在是计算机时代，绝大多数问题都用计算来解决，即编写程序计算解决。用数论算法来解，应该说是正解。参见：[《模乘逆元与孙子定理》][Link 2]一文。

如果只学过计算机语言而不懂数论，是不是就没有办法来解这个问题了？答案显然是否定的。解决这个问题，穷举法的应该是一个办法，总是能够算出结果来的。

然而，计算过程不同，速度有快慢之别。这里给出的程序，从模（除数）最大开始穷举试探，步伐大必然步数少。根据本题题意，7为最大除数，所以优先使用除数为7的条件；除7余2，其解必然是2+7k（k=0,1,2,,3,......）的形式，k从0开始逐一增大穷举试算，把满足条件的解找出来。

用孙子定理或者说用数论的方法解决问题，对于模（除数）是有要求的。要求模（除数）必须是两辆互素的。而这个程序对此没有要求。

对于标准的孙子定理问题，算出的解是23。其实，该问题的通解是23+105k（k=0,1,2,,3,......），105=3\*5\*7。

还需要主意的一点是，编写程序需要有通用性，才能做到一劳永逸。

程序如下：

/* 孙子定理（中国剩余定理）：穷举法 */
    
    #include <stdio.h>
    
    int crt(int m[], int r[], int n)
    {
        int x, flag, i, temp;
    
        // step1 找出最大的模（除数），放在m[0]，相应的余数也放在r[0]
        for(i=1; i<n; i++) {
            if(m[i] > m[0]) {
                temp = m[i];
                m[i] = m[0];
                m[0] = temp;
    
                temp = r[i];
                r[i] = r[0];
                r[0] = temp;
            }
        }
    
        // step2 试探法求满足各个模（除数）条件的数
        x = r[0];
        flag = 0;
        while(!flag) {
            flag = 1;
            for(i=1; i<n; i++)
                if(x % m[i] != r[i]) {
                    flag = 0;
                    break;
                }
            if(flag)
                break;
            x += m[0];
        }
    
        return x;
    }
    
    int main(void)
    {
        int m[] = {3, 5, 7};
        int r[] = {2, 3, 2};
        printf("%d\n", crt(m, r, sizeof(m)/sizeof(int)));
    
        int m2[] = {103, 107, 109};
        int r2[] = {44, 63, 21};
        printf("%d\n", crt(m2, r2, sizeof(m2)/sizeof(int)));
    
        int m3[] = {30, 51, 34, 103};
        int r3[] = {29, 2, 19, 30};
        printf("%d\n", crt(m3, r3, sizeof(m3)/sizeof(int)));
    
        return 0;
    }

3组数据的计算结果如下：

23  
2310  
2399

转载于:https://www.cnblogs.com/tigerisland/p/7564778.html

[Link 1]: http://blog.csdn.net/tigerisland45/article/details/51593924
[Link 2]: http://blog.csdn.net/tigerisland45/article/details/51263470