数学必修3《1.3.1辗转相除法与更相减损术》ppt课件免费下载
以下为幻灯片页面截图，请点击左边“我要下载”按钮免费下载无水印完整文件
1．3 算 法 案 例
1．用两数中 的数减去 的数，再用 构成新的一对数，再用 减 ，以同样的操作一直做下去，直到所得的两数相等为止，这个数就是这两个数的最大公约数．这个方法称作“更相减损术”，用它编写的算法称作“等值算法”．
较大
较小
所得差和较小数
大数
小数
2．古希腊求两个正整数的最大公约数的方法是 ：用 除以 所得的 和 构成新的一对数，继续做上面的除法，直到大数被小数除尽，这个较小的数就是最大公约数．据此编写的算法，也称作“欧几里得算法”．
辗转相除法
较大数
较小数
余数
较小数
3．对于正整数m与n(m>n)，总能找到整数q和r(0≤r重点：算法案例的原理、算法设计及算法思想的体会．
难点：理解算法案例的内容及具体算法设计的关键步骤．
一、弄清算法原理，掌握算法程序，经历算法设计过程，体会算法设计的关键环节，领悟算法思想．
1．辗转相除法
(1)辗转相除的原理：
设m，n是两个整数(不妨设m>n)，用m除以n，若商为q1，余数为r1(0≤r1n>r1>r2>…，所以到某一步必然有ri＝ri＋1·qi＋2，即ri恰能被ri＋1整除，这时ri＋1是ri和ri＋1的最大公约数，它也必然是ri－1和ri、ri－2和ri－1、…、r1与r2、n和r2、m和n的最大公约数．
(2)辗转相除法的算法分析：
由以上辗转相除法的原理可以发现，辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m表示，把较小的数用变量n表示，这样式子m＝n·q＋r(0≤r(3)用辗转相除法求任意两个正整数最大公约数的程序框图．
由于辗转相除法总是用较大的数去除以较小的数，所以首先要对一开始给定的两数的大小进行判断，并将大数赋给m，小数赋给n，然后再执行下面的过程．程序框图如图．
(4)用辗转相除法求两个数的最大公约数的程序设计：
2．更相减损术
(1)更相减损术求两数最大公约数的过程与算法设计．
对于给定的两个数，用较大的数减去较小的数，接着把得到的差与较小的数比较，用这时两个数中较大的数减去较小的数，继续这样的操作(大数减小数)，直到所得的数相等为止，那么这个数(相等数)就是所求的最大公约数．
显然，上述过程中大数减去小数是一个重复执行的过程，因此只需将大数赋给变量a，小数赋给变量b，那么就可以通过循环结构实现算法．或当a>b时，将a－b赋给a，b＝b，当a(2)更相减损术求最大公约数的程序设计如下：
请自行将其直到型循环结构算法写出来．
3．辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别，辗转相除法的上一次运算的除数和余数分别作为下一次运算的被除数和除数，其结果直至余数为零得出．更相减损术在上一次运算结束后，比较减数和差的大小，将大的作为下一次运算的被减数，小的作为减数，直至出现相等数时得到结果．
由此可见，二者算法是相似的．主要区别在于，辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递归过程．另外两者在算法设计上有一个重要的区别点，辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可．而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数．这些内容都是应特别注意的关键环节．
4．用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求最大公约数．
[例1] 用辗转相除法和更相减损术两种方法求80和36的最大公约数．
[解析] 用辗除相除法：
80＝36×2＋8，
36＝8×4＋4，
8＝4×2＋0.
故80和36的最大公约数是4.
用更相减损术：
80－36＝44，
44－36＝8，
36－8＝28，
28－8＝20，
20－8＝12，
12－8＝4，
8－4＝4.
∴80和36的最大公约数是4.
[点评] (1)辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数；更相减损术是当大数减去小数的差等于小数时停止减法运算，较小的数就是最大公约数．
(2)用更相减损术求时，如果先约去2×2，则变为求20和9的最大约数，最后结果再乘以4.
(1)用辗转相除法求288与123的最大公约数．
(2)用更相减损术求57与93的最大公约数．
(3)求567与405的最小公倍数．
[解析] (1)288＝123×2＋42,123＝42×2＋39，
42＝39×1＋3,39＝3×13，
∴288和123的最大公约数是3.
(2)(93,57)―→(36,57)―→(36,21)―→(15,21)―→(15,6)―→(9,6)―→(3,6)―→(3,3)，
∴93与57的最大公约数是3.
(3)567＝405×1＋162
405＝162×2＋81
162＝81×2＋0
∴81是567与405的最大公约数，从而567与405的最小公倍数为567×405÷81＝2835.
[例2] 求324,243和135的最大公约数．
[解析] 先求324与243的最大公约数a，再求a与135的最大公约数b，则b为这三个数的最大公约数．
∵324＝243×1＋81
243＝81×3＋0
则324与243最大公约数为：a＝81
又∵135＝81×1＋54
81＝54×1＋27
54＝27×2＋0
则81与135的最大公约数为27
∴324、243、135的最大公约数为27.
一、填空题
1．在对16和12求最大公约数时，整个操作如下：(16,12)―→(4,12)―→(4,8)―→(4,4)，由此可以看出12和16的最大公约数是________．
[答案] 4
2．1443与999的最大公约数是________．
[答案] 111
[解析]
(999,1443)―→(999,444)―→(555,444)―→(111,444)―→(111,333)―→(111,222)―→(111,111)
或1443－999＝444,999－444＝555,555－444＝111,444－111＝333,333－111＝222,222－111＝111.
自己用辗转相除法写出解答过程．
3．运算速度快是计算机一个很重要的特点，而算法好坏的一个重要标志是________．
[答案] 运算次数
4．2004与4509的最大公约数为________．
[答案] 501
[解析]
∴4509＝33×167，∴2004与4509的最大公约数为3×167＝501.
自己用辗转相除法和更相减损术写出解答．
二、解答题
5．写出从键盘任意输入两个正整数a，b，输出这两个数的最小公倍数的算法，画出程序框图，写出算法语句．
r＝a MOD b
a＝b
b＝r
LOOP UNTIL r＝0
p＝p/a
PRINT “m、n的最小公倍数为”；p
END.
