9512.net
甜梦文库
当前位置:首页 >> 数学 >>

高中数学 算法案例第1课时辗转相除法与更相减损术学案课件 新人教A版必修3【课件】_图文

? 1.3 算 法 案 例

? 1.用两数中

构成新的一对数,再用 减 ,以同样的操作一直做下去,直到所得的两数相等为止,这个 所得差和较小数 数就是这两个数的最大公约数.这个方法称作“更相减损术”,用 大数 小数 它编写的算法称作“等值算法”.

的数减去 较大

的数,再用 较小

? 2.古希腊求两个正整数的最大公约数的方法是 :用 除以 所得的 和 构成新的一对数,继续做上面的除法,直到大数被小数除尽, 较大数 余数 辗转相除法 较小数 这个较小的数就是最大公约数.据此编写的算法,也称作“欧几里 得算法”. 较小数

? 3.对于正整数m与n(m>n),总能找到整数q和r(0≤r<n)使得m=nq+r 成立,这个除法称为带余除法.通常记r=mMODn.

? 重点:算法案例的原理、算法设计及算法思想的体会. ? 难点:理解算法案例的内容及具体算法设计的关键步骤.

? 一、弄清算法原理,掌握算法程序,经历算法设计过程,体会算法设 计的关键环节,领悟算法思想.

? 1.辗转相除法 ? (1)辗转相除的原理: ? 设 m , n 是两个整数 ( 不妨设 m>n) ,用 m 除以 n ,若商为 q1 ,余数为 r1(0≤r1<n),则m=n·q1+r1,显然若x是m和n的公约数,即x能整除 m和n,则x也必然能整除r1,这样x也是n和r1的公约数,故求m和n的 公约数就是求 n 和 r1 的公约数;同理,用 n 除以 r1 ,得 n = r1·q2 + r2(0≤r2<r1),故求m和n的公约数就是求r2和r1的公约数,…,依次下 去,由于m>n>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<n)就是一个反复执行的步骤,因此可 以用循环结构实现算法.如图.

? (3)用辗转相除法求任意两个正整数最大公约数的程序框图. ? 由于辗转相除法总是用较大的数去除以较小的数,所以首先要对一 开始给定的两数的大小进行判断,并将大数赋给m,小数赋给n,然 后再执行下面的过程.程序框图如图.

? (4)用辗转相除法求两个数的最大公约数的程序设计:

? 2.更相减损术 ? (1)更相减损术求两数最大公约数的过程与算法设计. ? 对于给定的两个数,用较大的数减去较小的数,接着把得到的差与 较小的数比较,用这时两个数中较大的数减去较小的数,继续这样 的操作(大数减小数),直到所得的数相等为止,那么这个数(相等数) 就是所求的最大公约数.

? 显然,上述过程中大数减去小数是一个重复执行的过程,因此只需 将大数赋给变量a,小数赋给变量b,那么就可以通过循环结构实现 算法.或当a>b时,将a-b赋给a,b=b,当a<b时,a=a,将b-a 赋给b然后再进行比较,依次类推用循环结构实现.

? (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,输出这两个数的最小公 倍数的算法,画出程序框图,写出算法语句.

从键盘输入两数 a,b 后,先求两数的最大公 a· b 约数 k,再计算两数的最小公倍数 p= k ,输出 p 即可. 程序框图如右图. 程序为: INPUT “正整数 a,b=”;a,b p=a*b IF a<b THEN t =a a=b b=t END IF DO

[解析]

? ? ? ? ? ? ?

r=a MOD b a= b b= r LOOP UNTIL r=0 p=p/a PRINT “m、n的最小公倍数为”;p END.



学霸百科 | 新词新语

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图