典型例题探究（算法案例）.doc.doc

[典型例题探究] 规律发现【例 1】我国《算经十书》之一《孙子算经》中有这样一个问题:“今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二. 问物几何? 答曰:二十三.”你能用程序解决这个问题吗? 分析: 设物共 m个,被3,5,7 除所得的商分别为 x、y、z, 则这个问题相当于求不定方程这个问题的通用解法称为“孙子剩余定理”或“中国剩余定理”. 著名的“韩信点兵问题”即为此例的应用. ???????????27 ,35 ,23zm ym xm 应同时满足下列三个条件:(1)m MOD 3=2 ;(2)m MOD 5=3 ; (3)m MOD 7=2. 因此, 可以让 m从2 开始检验,若3 个条件中有任何一个不成立,则 m 递增 1 ,一直到 m 同时满足三个条件为止. 考虑到 m被7 除余数为 2, 故m 至少是 9, 也可以从 m =9开始验证. 解: m =2 f =0 WHILE f =0 IFm MOD 3=2 AND m MOD 5=3 AND m MOD 7=2 THEN PRINT “物体的个数为:”;m f =1 ELSE 设置 f =0 ,f =1 的目的是让循环进行或结束,否则循环无法停下来. 此处让 f =0 时进行循环,f=1 时中止循环. m=m +1 END IF WEND END 实际上按此法求出来的只是符合条件的最小正整数. 【例 2】我有有趣的数学问题:“今有鸡翁一, 值钱五; 鸡母一, 值钱三; 鸡雏三, 值钱一凡百钱, 买鸡百只,问鸡翁、母、雏各几何? ”你能用程序解决这个问题吗? 分析:设鸡翁、母、雏各 x、y、z 只,则这个问题在数学上称为“百鸡问题”. ???????????②, ①, 100 100 3 35zyx zyx 由②,得z =100 -x-y,③把三元一次方程组转化为二元一次不定方程. ③代入①,得5x +3 y+3 100 yx??=100 , 即7x +4 y =100. ④求方程④的解,可由程序解之. 解: x =1 y =1 WHILE x< =14 WHILE y< =25 IF7* x +4 * y =100 THEN z =100 -x-y 从x 的最小值开始验证,循环进行. 由于 7x +4 y =100 ,且x、y∈Z, 故x≤ 14,y≤ 25. PRINT “鸡翁、母、雏的个数别为:”;x,y,z END IF y=y +1 WEND x=x +1 y =1 WEND END 实际上, 该题可以不对方程组进行化简, ①、②可得 x 最大值为 20,y 最大值为 33,z 最大值为 100 ,且 z为3 的倍数. 程序如下: x =1 y =1 z =3 WHILE x< =20 WHILE y< =33 WHILE z< =100 IF5* x +3 * y+z /3=100 AND x+y+z =100 THEN PRINT “鸡翁、母、雏的个数分别为:”;x、y、z END IF z=z +3 WEND y=y +1 z =3 WEND x=x +1 y =1 WEND END 对于多重循环或条件嵌套, 要注意每一重都有开头和结尾, 程序本身也有一个结尾,不能丢掉