《辗转相除法与更相减损术》.ppt

《《辗转相除法与更相减损术》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1．3算法案例1．3.1辗转相除法与更相减损术学习目标预习导学典例精析栏目链接辗转相除法求最大公约数求228与1995的最大公约数．分析：因为两数没有明显的公约数，可以考虑用辗转相除法．解析：1995＝8×228＋171，228＝1×171＋57，171＝3×57，所以228与1995最大公约数为57.答案：57►跟踪训练1．用辗转相除法求得459和357的最大公约数是()A．3B．9C．17D．51D学习目标预习导学典例精析栏目链接更相减损术求最大公约数用更相减损术求98与63的最大公约数．解析

2、：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7所以，98与63的最大公约数是7.►跟踪训练2．用更相减损术求225与135的最大公约数为()A．45B．5C．9D．15A学习目标预习导学典例精析栏目链接比较辗转相除法与更相减损术用辗转相除法求下面两数的最大公约数，并用更相减损术检验你的结果：(1)80，36；(2)294，84.分析：使用辗转相除法，我们可依据a＝nb＋r这个式子，反复执行，直到r

3、＝0为止．用更相减损术就是根据r＝a－b这个式子，反复执行．学习目标预习导学典例精析栏目链接解析：(1)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.(2)294＝84×3＋42，84＝42×2，即294与84的最大公约数是42.验证：∵294与84都是偶数可同时除以2，即取147与42的最大公约数后再乘2.147－4

4、2＝105，105－42＝63，63－42＝21，42－21＝21，∴294与84的最大公约数为21×2＝42.点评：由该题可以看出，辗转相除法求最大公约数步骤较少，而更相减损术运算简易，解题时要灵活运用．学习目标预习导学典例精析栏目链接►跟踪训练3．用更相减损术求98与64的最大公约数．解析：由于64是偶数，减半为32，把98和32以大数减小数，并辗转相减，即：98－32＝66，66－32＝34，34－32＝2，32－2＝30，30－2＝28，…，4－2＝2，所以，98与64的最大公约数是2.学

5、习目标预习导学典例精析栏目链接辗转相除法的程序框图与程序写出辗转相除法的程序框图及程序．解析：r＝mMODn表示m除以n的余数为r，例如：3＝15MOD6.程序框图：学习目标预习导学典例精析栏目链接程序：点评：借助程序框图准确理解程序的本质．学习目标预习导学典例精析栏目链接►跟踪训练4．下边程序运行后输出的结果为()A．50B.5C.25D.0D