有一堆机器零件(零件个数小于 100),3 个为一组则剩下 2 个,5 个为一组则剩 下 1 个,7 个为一组则剩下 6 个,求这堆零件一共有多少个? 函数原型:int calc(int x[], int len); 并验证《孙子算经》卷下“物不知
时间: 2024-02-19 09:03:04 浏览: 63
第一次作业 编程题目1
此题是一道中国古代数学经典问题,可以使用中国剩余定理进行求解。
根据题意,设这堆机器零件的数量为 N,则可以列出如下的同余方程组:
N ≡ 2 (mod 3)
N ≡ 1 (mod 5)
N ≡ 6 (mod 7)
根据中国剩余定理,可以得到:
N ≡ a1M1y1 + a2M2y2 + a3M3y3 (mod M)
其中,ai 为同余方程组右侧的余数,Mi 为同余方程组右侧的模数,M = M1M2M3,yi 为 M1、M2、M3 在模 Mi 意义下的逆元。
计算得到 M1 = 5×7 = 35,M2 = 3×7 = 21,M3 = 3×5 = 15,M = 35×21×15 = 11025。
接着,我们需要求出 M1、M2、M3 在模 Mi 意义下的逆元:
35y1 ≡ 1 (mod 21),解得 y1 = 8
21y2 ≡ 1 (mod 35),解得 y2 = 6
15y3 ≡ 1 (mod 23),解得 y3 = 17
最后,代入公式计算得到:
N ≡ 2×35×8 + 1×21×6 + 6×15×17 ≡ 2339 (mod 11025)
因此,这堆机器零件一共有 2339 个。
下面是对应的 C++ 代码实现:
```cpp
int calc(int x[], int len) {
int a[] = {2, 1, 6};
int m[] = {3, 5, 7};
int M = 3*5*7;
int y[] = {5*7, 3*7, 3*5};
int res = 0;
for (int i = 0; i < len; i++) {
res += a[i] * y[i] * (M / m[i]);
}
res %= M;
return res;
}
```
至于《孙子算经》卷下所述的“物不知数,数不知物”问题,它是一道古代代数学题,与这道题目没有直接联系,但二者都反映了中国古代的数学思维和数学成就。
阅读全文