•1. 3算法案例第1课时 極特相除法与更相濒损术
* T « • * * T • -t * * 1 « *KQZZYX课前自主预习 • 1.用两数中较人的数减去较小的数, 再用 所得差和较小数 构成新的一对数，
再用 ______ ^减 ______ ;数以同样的操作
一直做下去，直到所得的两数相等为止，
这个数就是这两个数的最大公约数.这个 方法称作“更相减损术”，用它编写的算 法称作“等值算法”・• 2.古希腊求两个正整数的最大公约数的 方法是辗转相除法：用较大数除以较小数所 得的
余数 和较小数 构成新的一对数， 继续做上面的除法，直到大数被小数除尽, 这个较小的数就是最大公约数.据此编写 的算法，也称作“欧几里得算法” •3・对于正整数加与n(m>n),总能找到整数g 和r(O
•重点：算法案例的原理、算法设计及算法 思想的体会.
•难点：理解算法案例的内容及具体算法设 计的关键步骤.XXYDDB学习要点点拨
• 一、弄清算法原理，掌握算法程序，经历 蠶翳■，聶’体会算法设计的关键环节,• 1 •辗转相除法
• (1)辗转相除的原理：
・设zn, 〃是两个整数(不妨设m>ri),用加除以〃，若商为务,
余数为厂1(00］
和斤的公约数就是求厂2和厂1的公约薮，…，依次下去，由
于加>〃>厂］>厂2>…，所以到某一步必然有rz = r/+1 9q汁"即
耳恰能被厂计］整除，这时耳+1是耳和厂j+1的最关公约数，它 也必然是耳_1和乙、厂—2和耳_1、…、厂1与厂2、〃和厂2、加和〃 的最大公约数. • (2)辗转相除法的算法分析:
•由以上辗转相除法的原理可以发现，辗转 相除法的基本步骤是用较大的数除以较小 的数，考虑到算法中的赋值语句可以对同 一变量多次赋值，我们可以把较大的数用 变量加表示，把较小的数用变量〃表示，这 样式子m = n -q +
r(O
• (3)用辗转相除法求任意两个正整数最大公 约数的程序框图.
1.3 算法案例
［学习目标导航］ 学习提示
1. 通过对中国古代算法研究的学习，了解中国古代伟大的文化成就，增强民族自豪感.
2.通过对算法案例的学习，进一步理解算法的思想，能够用程序来解决生活中常见的数学问题.
3.理解进位制，能进行各种进位制之间的相互转化. 重点是进位制，用算法设计程序；难点是在程序设计中用好三种基本的逻辑结构.
［教材优化全析］ 全析提示
我们通过程序框图形象、直观地表示算法，因此，在编制程序前，先绘出程序框图，能使思路清晰，并且对于三种基本的逻辑结构：顺序结构、条件结构、循环结构的脉络表达准确，有助于我们准确写出程序语言.
（一）教材上介绍了辗转相除法（欧几里得算法），求两个数的最大公约数，其基本步骤是带余除法m=nq+r（0≤r＜n），反复执行，直到余数r=0为止.求任意两个数的最大公约数的算法是： 程序框图比自然语言的描述更容易理解.一般说来，设计程序时，先画程序框图比较好.
第一步：输入两个正整数a，b（a＞b）；
第二步：求出a÷b的余数r；
第三步：令a=b，b=r，若r≠0，重复第二步；
第四步：输出最大公约数a.
相应的程序框图是：
举例说明.
m=90，n=36，
m=2n+18，r=18.
令m=36， n=18.
又有36=18×2，
即m=2n，
此时r=0.
令m=18，n=0.
故最大公约数为18.
开始输入,(＞)abab求÷的余数abrab=br=r=0?是否输出a结束 两个数a，b的最大公约数一般写成（a，b），如90与36的最大公约数为18，写成（90，36）=18.
“更相减损术”是我国古代求最大公约数的方法，反映了我国古代劳动人民的伟大智慧，让我们感到无比的光荣与自豪.
其程序语言是：
INPUT “请输入两个正整数a，b：”；a，b
PRINT a；b；
WHILE a＜＞b
IF a＞=b THEN
1 1.3 算法案例
1.3 算法案例——案例1 辗转相除法与更相减损术8
**学习目标**
1．理解辗转相除法与更相减损术求最大公约数的方法。
2．把辗转相除法与更相减损术的方法转换成程序框图与程序语言．
**要点精讲**
1．辗转相除法
例如，求两个正数8251和6105的最大公约数。
分析与解：8251与6105两数都比较大，而且没有明显的公约数，可以考虑用两数中较大的数除以较小的数，求得商和余数：
8251＝6105×1＋2146
显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。
6105＝2146×2＋1813， 2146＝1813×1＋333， 1813＝333×5＋148
333＝148×2＋37， 148＝37×4＋0
则37为37与148的最大公约数，也是148与333的最大公约数，也是333与1813的最大公约数，也是1813与2146的最大公约数，也是2146与6105的最大公约数。
所以，2146与6105的最大公约数是37。
以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。
2．更相减损术
我国早期也有解决求最大公约数问题的算法，就是更相减损术。在《九章算术》中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。
翻译为：
（1）任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。
（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。
**范例分析**
例1．试分别用辗转相除法和更相减损术求840与1764、440与556的最大公约数。
▁▂▃▄▅▆▇█▉▊▋▌精诚凝聚 =^_^= 成就梦想 ▁▂▃▄▅▆▇█▉▊▋▌
▃ ▄ ▅ ▆ ▇ █ █ ■ ▓点亮心灯 ~~~///(^v^)\\\~~~ 照亮人生 ▃ ▄ ▅ ▆ ▇ █ █ ■ ▓ 1.3.1 算法案例---辗转相除法与更相减损术
教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.
教学重点：理解辗转相除法与更相减损术求最大公约数的方法.
教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.
教学过程：
一、复习准备：
1. 回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）.
2. 提问：①小学学过的求两个数最大公约数的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出36和64的最大公约数. ②除了用这种方法外还有没有其它方法？6436128，36和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至842，得出4即是36和64的最大公约数.
二、讲授新课：
1. 教学辗转相除法：
例1：求两个正数1424和801的最大公约数.
分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数. （适用于两数较大时）
①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的. 利用辗转相除法求最大公约数的步骤如下：
（1）用较大的数m除以较小的数n得到一个商0S和一个余数0R；（2）若0R＝0，则n为m，n的最大公约数；若0R≠0，则用除数n除以余数0R得到一个商1S和一个余数1R；（3）若1R＝0，则1R为m，n的最大公约数；若1R≠0，则用除数0R除以余数1R得到一个商2S和一个余数2R；……依次计算直至nR＝0，此时所得到的1nR即为所求的最大公约数.
