Question

我國《算經十書》之一《孫子算經》中有這樣一個問題：“今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？答曰：二十三。”你能用程序解決這個問題嗎？

   

Answer 1

思路解析：這個問題的通用解法稱為“孫子剩余定理”或“中國剩余定理”。著名的“韓信點兵問題”即為此例的應用。

設物共m個，被3，5，7除所得的商分別為x、y、z，則這個問題相當于求不定方程

的正整數解。m應同時滿足下列三個條件：（1）mMOD 3=2；（2）mMOD 5=3；（3）mMOD 7=2。因此，可以讓m從2開始檢驗，若3個條件中有任何一個不成立，則m遞增1，一直到m同時滿足三個條件為止�？紤]到m被7除余數為2，故m至少是9，也可以從m=9開始驗證。

    答案：m=2

          f=0

          WHILE　f=0

          IF　mMOD 3=2　AND　mMOD 5=3

          AND　mMOD 7=2　THEN

          PRINT　“物體的個數為：”；m

              f=1

          ELSE

              m=m+1

          END　IF

          WEND

          END