§ 13．3 算法案例 一、知识导学
1．算法设计思想： （1）“韩信点兵—孙子问题”对正整数m 从2开始逐一检验条件，若三个条件中有任何一个不满足，则m 递增1，一直到m 同时满足三个条件为止(循环过程用Goto 语句实现) （2）用辗转相除法找出b a .的最大公约数的步骤是：计算出b a ÷的余数r ，若0=r ，则b 为b a ,的最大公约数；若0≠r ，则把前面的除数b 作为新的被除数，继续运算，直到余数为0，此时的除数即为正整数b a ,的最大公约数.
2.更相减损术的步骤：（1）任意给出两个正数，判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.
（3）二分法求方程0)(=x f 在区间[]b a ,内的一个近似解*x 的解题步骤可表示为 S1 取[b a ,]的中点()b a x +=
2
10，将区间 一分为二；
S2 若()00=x f ，则0x 就是方程的根；否则判别根*x 在0x 的左侧还是右侧：
若()()00>⋅x f a f ，()b x x ,*0∈，以0x 代替a ； 若()()00<⋅x f a f ，则()0,*x a x ∈，以0x 代替b ；
S3 若c b a <-，计算终止，此时0x x ≈*
，否则转S1.
二、疑难知识导析
1．)int(x 表示不超过x 的整数部分，如0)32.0int(,5)86.5int(==，但当x 是负数时极易出错，如1)14.1int(-=-就是错误的，应为-2.
2．),mod(b a 表示a 除以b 所得的余数，也可用a mod b 表示. 3．辗转相除法与更相减损术求最大公约数的联系与区别：
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.
4．用二分法求方程近似解，必须先判断方程在给定区间[b a ,]上是否有解,即()x f 连续且满足()()0<b f a f .并在二分搜索过程中需对中点处函数值的符号进行多次循环判定，故需要选择结构、循环结构，即可用Goto 语句和条件语句实现算法.
三、经典例题导讲
[例1]=)5int(π ， =-)05.0int( ， =)9,67mod( ， 45 mod 7= . A ．16，-1，4，3 B.15，0，4，3 C.15,-1,3,4 D.15,-1,4,3
错解：根据)int(x 表示不超过x 的整数部分, ),mod(b a 表示a 除以b 所得的余数,选择B. 错因:对)int(x 表示的含义理解不透彻,将不超过-0.05的整数错认为是0,将负数的大小比较与正数的大小比较相混淆.
正解：不超过-0.05的整数是-1,所以答案为D.
[例2] 所谓同构数是指此数的平方数的最后几位与该数相等.请设计一算法判断一个大于0且小于1000的整数是否为同构数.
错解： 算法思想：求出输入数的平方，考虑其个位或最后两位或最后三位与输入数是否相等，若相等，则为同构数.
Read x
x x y *=
If )10(y x = or )100(y x = or )1000(y x = Then Print x
End if End
错因：在表示个位或最后两位或最后三位出现错误，“/”仅表示除，y/10,y/100,y/1000都仅仅表示商.
正解：可用)1000,mod(),100,mod(),10,mod(y y y 来表示个位，最后两位以及最后三位.
Read x
x x y *=
If ))10,mod((y x = or ))100,mod((y x = or ))1000,mod((y x = Then Print x End if End
[例3]《孙子算经》中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”可以用下面的算法解决：先在纸上写上2，每次加3，加成5除余3的时候停下来，再在这个数上每次加15，到得出7除2的时候，就是答数. 试用流程图和伪代码表示这一算法. 解：流程图为：
伪代码为： 10 2←m 20 3+←m m
30 If ()35,mod ≠m Then Goto 20 40 If 2)7,mod(=m Then Print m Goto 80
50 End if 60 15+←m m 70 Goto 40
80 End
点评：这是孙子思想的体现，主要是依次满足三个整除条件. [例4]分别用辗转相除法、更相减损法求192与81的最大公约数.
解：辗转相除法：
S1 30281192 =÷
S2 2123081 =÷ S3 912130 =÷ S4 32921 =÷ S5 0339 =÷
故3是192 与81 的最大公约数. 更相减损法： S1 11181192=- S2 3081111=- S3 513081=- S4 213051=- S5 92130=- S6 12921=- S7 3912=- S8 639=-
S9 336=-
故3 是192与81的最大公约数.
点评：辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少.辗转相除法是当大数被小数整除时停止除法运算，此时的小数就是两者的最大公约数，更相减损术是当大数减去小数的差等于小数时减法停止，较小的数就是最大公约数. [例5]为了设计用区间二分法求方程0123=-+x x 在[0，1]上的一个近似解（误差不超过0.001）的算法,流程图的各个框图如下所示,请重新排列各框图,并用带箭头的流线和判断符号“Y”、“N ”组成正确的算法流程图,并写出其伪代码.(其中b a ,分别表示区间的左右端点)
图13-3-2 流程图为
图13-3-3
伪代码为
10 Read b a , 20 2)(0b a x +← 30 1)(23-+←a a a f 40 1)(2
0300-+←x x x f 50 If 0)(0=x f Then Goto 120 60 If 0)()(0<x f a f Then 70 0x b ← 100 End if
80 Else 90 0x a ← 100 End if
110 If 001.0≥-b a Then Goto 20 120 Print 0x 130 End
点评：二分法的基本思想在必修一中已渗透，这里运用算法将二分法求方程近似解的步骤更清晰的表述出来.
[例6] 用秦九韶算法计算多项式6
5
4
3
2
3567983512)(x x x x x x x f ++++-+=在
4-=x 时的值时，3v 的值为 .
解： 根据秦九韶算法，此多项式可变形为
()()()()()()1235879653++-+++=x x x x x x x f
按照从内到外的顺序，依次计算一次多项式当4-=x 时的值： 40-=v
75)4(31-=+-⨯=v 346)7()4(2=+-⨯-=v 577934)4(3-=+⨯-=v 故当4-=x 时多项式的值为57-.
点评：秦九韶算法的关键是n 次多项式的变形.
把一个n 次多项式0111)(a x a x a x a x f n n n n ++++=-- 改写成
0121)))(()(a x a x a x a x a x f n n n +++++=-- ，求多项式的值，首先计算最内层括号
内一次多项式的值，然后由内向外逐层计算一次多项式的值，这样把求n 次多项式的值问题转化为求n 个一次多项式的值的问题，这种方法成为秦九韶算法.这种算法中有反复执行的步骤，因此，可考虑用循环结构实现. 四、典型习题导练
1．以下短文摘自古代《孙子算经》一书，其引申出的“大衍求一术”称为“中国剩余原理”：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”答曰（ ）.
A ．二十一 B.二十二 C.二十三 D.二十四 2．用辗转相除法求52与39的最大公约数的循环次数为（ ）.
A ．1次 B.2次 C.3次 D.5次
3．下面程序功能是统计随机产生的十个两位正整数中偶数和奇数的个数，并求出偶数与奇数各自的总和.
For I from 1 to 10 10)90int(+*←Rnd x Print x;
If Then x
s s n n +←+←22122
Else
x s s +←11 End If End for Print
Print “奇数个数=”；1n ，“偶数个数=”；2n 4．若一个数的各因子之和正好等于该数本身，则该数成为完数.请补充完整下列找出1～100之间的所有完数的伪代码.
For a from 2 to 100
1←c
For b from 2 to If mod(a,b)=0 Then
End if End For
If Then Print a End if End For
End
5．设计求被9除余4，被11除余3的最小正整数的算法，画出流程图，写出伪代码. 6．利用辗转相除法或更相减损术求324,243,135的最大公约数.。