第12课时5.4 算法案例
重点难点
重点：通过案例分析理解辗转相除法与更相减损术求最大公约数的方法，体会算法思想.
难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.
学习要求
1．理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析.
2．基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.
【课堂互动】
问题：
写出求两个正整数a,b(a>b)的最大公约数的一个算法。
1.辗转相除法
公元前3世纪，欧几里得介绍了求两个正整数a,b(a>b)的最大公约数的方法，求出一列数：，这列数从第三项开始，每一项都是前两项相除所得的余数（即），余数等于0的前一项，即是a和b的最大公约数，这种方法称为“欧几里得辗转相除法”。
例1 求两个正数8 251和6 105的最大公约数．
（分析：8 251与6 105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）
【解】8 251＝6 105×1＋2 146
显然8 251和的2 146最大公约数也必是2 146的约数，同样6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数．
6 105＝2146×2＋1813
2 146＝1813×1＋333
1 813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
则37为8 251与6 105的最大公约数．
【小结】以上我们求最大公约数的方法就是欧几里得辗转相除法．其求最大公约数的步骤如下：
第一步：用较大的数除以较小的数,得到一个商和一个余数；
第二步：若，则为的最大公约数；若，则用除数除以余数,得到一个商和一个余数；
第三步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数；
……
依次计算直至，此时所得到的即为所求的最大公约数.
【练习】求a=204，b=85的最大公约数，步骤为：
S1 204÷85的余数为34，
S2 85÷34的余数为17，
S3 34÷17的余数为0。
所以它们的最大公约数为17。
算法描述：计算出a÷b的余数r，若r=0，则b为a，b的最大公约数；若r≠0，则把前面的除数b作为新的被除数，把余数r作为新的除数（a，b要重新赋值，a←b，b←r），继续进行上述运算，直到余数为0(用While循环语句，循环的执行条件是r≠0，当r=0时，循环终止)，此时的除数即为所求的最大公约数。
算法如下:
S1 输入两个正整数a,b(a>b)；
S2 若Mod(a，b)=0，则转S3；否则，r←Mod(a,b)， a←b，b←r，转S2。
S3 输出最大公约数b.
【流程图】
【伪代码】
2. 更相减损法
我国早期也有解决求最大公约数问题的算法，就是更相减损术．
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以等数约之．
翻译出来为：
第一步：任意给出两个正数,判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数．
再从这个角度看一下“求a=204，b=85的最大公约数”的问题，S1步可以等价为等式：。S2步可以等价为等式：。这两步从减法的角度可以理解为：204-85，所得的差与减式中的较小数比较，再用大的数减小的数，循环执行以上步骤,直到结果为0。此时减数就是a和b的最大公约数。这一算法根据它的特点，也可以用循环语句完成。
参考代码：
/a放较大的数，b放较小的数
If a < b Then
m ← a
a ← b
b ← m /交换a，b中的数
End If /确保a是a，b中较大的数
r ← a – b /两数相减
While r ≠ 0
If b > r Then
a ← b
b ← r
Else
a ← r
End If
r ← a – b
/确保相减后仍用较大的数减去较小的数
End While
Print b
用“更相减损法”求多于两个数的最大公约数就可以显示出其优越性
【小结】比较辗转相除法与更相减损术的区别
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显．
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到．
【追踪训练】
1.分析下面一段代码的目的：
Read m,n
While m/n≠Int(m/n)
c←m- Int(m/n)×n
m←n
n←c
End While
Print n
(Int(x)表示不超过x的最大整数)
【解】 求m，n的最大公约数 。
2.用辗转相除法求下列各组数的最大公约数。
（1）225,135; （2）98,196.
3.用更相减损法求下列各组数的最大公约数。
（31）72,168; （2）153,119.
4. 现有长度为360cm和780cm两种规格的钢筋若干.要焊接一批正方形模型.问:怎样才能保证正方体体积最大且不浪费?
思路点拨: 正方体的所有棱长都相等,故必须将钢筋剪裁成长度相等的钢筋条;又必须不浪费,这就说明必须剪后无剩余.于是为了保证正方体的体积最大,故剪的钢筋的最大长度为360cm和780cm的最大公约数,可用更相减损术求最大公约数.
第11课时算法案例(2)
分层训练
1、阅读下列代码，写出该代码的运行结果
t←1
n←3
s←0
While s<10
t←t×n
s←s+t
End While
Print s
答：
2、设计一个计算1×3×5×7×9的算法．下面给出了程序的一部分，则在横线上不能填入下面数据中的( )
S←l
I←3
While I<
S←S×I
I←I+2
End While
Print S
A．9 B．9．5 C． 10 D．10.5
3、下列一段伪代码执行结束后S的目的是( )
S←0
a←l
For I From l To 4
a←2a
S←S+a
End For
A．计算2+22+23+24 B．计算2+22+23 C．计算23 D．计算24
4. 先用不同的算法计算
，再比较其优劣。
5. 已知△ABC中，试写出作△ABC的一个算法。
6. 用条件语句表示：输入x的值，通过 计算y的值。
7. 写出求中最大数的一个算法。
8、一球从l00m高度落下，每次落地后反弹回原高度的一半，再落下，在第十次落地时，共经过多少路程?第十次下落多高?
思考运用
9. 我国古代劳动人民对不定方程的研究作出过重要贡献，其中《张丘建算经》中的百鸡问题就是一个很有影响力的问题：“今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百钱买百鸡，问鸡翁、母、雏各几何？”
其意思是：一只公鸡的价钱是五钱，一只母鸡的价钱是三钱，三只小鸡的价钱是一钱。现在用一百钱买一百鸡，可以买公鸡、母鸡、小鸡各几个？
这是一个不定方程的整数解问题，假设公鸡x只，母鸡y只，小鸡z只，首先，可以大致得到x在1至20之间，y在1至33之间，z=100-x-y可以确定。
根据上述算法思想，画出求解的流程图，并写出相应的伪代码。
w.w.w.k.s.5.u.c.o.m
【点此下载】