算法案例课件市名师优质课比赛一等奖市公开课获奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,辗转相除法,与,最大条约数,最小公倍数,第1页,问题情境,求18和30最大条约数,结论,18和30最大条约数为6,18和30最小公倍数为90 (切记方法!),第2页,问题1 求204与85最大条约数,问题2 求8251与6105最大条约数,204与85最大条约数是17,8251与6105最大条约数是34,辗转相除法:我们能够证实，对于任意两个正整数，上述步骤总能够在有限步之后完成，从而总能够用辗转相除方法求出最大条约数,第3页,算法设计:,怎样用辗转相除法找出两个正整数,a,b,最大条约数？,(1)结合问题1和问题2，应该利用什么结构实现该算法?,（循环结构）,(2)每一次循环中所进行是什么样运算？,（求,a,b,余数）,(3)下一次循环输入整数应该是什么？循环何时结束？,设ab,a除以b余数为r(br),则下一次循环两个数为b,r.,直到r=0为止.,第4页,算法,S1 输入两个正整数,a,b,（,a,b,）；,S2 若Mod（,a,b,）0，,则输出最大条约数,b,，,算法结束；不然r,Mod（,a,b,），,a,b,，,b,r，转S2,流程图,第5页,伪代码,Read,a,b,While Mod(,a,b,),0,r,mod(,a,b,),a,b,b,r,End While,Print,b,思索：,r,mod(,a,b,),a,b,b,r,能否改为,a,b,b,mod(,a,b,),第6页,例1 试画出求正整数,a,b,最小公倍数流程图，并写出其伪代码。,Read,a,b,c,ab,While Mod(,a,b,),0,r,Mod(,a,b,),a,b,b,r,End While,Print,c,/,b,第7页,例2下面一段伪代码目标是求,10 Read,a,b,20 If,a,/,b,Int(,a,/,b,)Then Goto 70,30,c,a,Int,(,a,/,b,),b,40,a,b,50,b,c,60 Goto 20,70 Print,b,A.求,a,b,最小公倍数 B.求,a,b,最大条约数,C.求,a,被,b,整除商 D.求,b,除以,a,余数,分析：解题关键就是：,a,int(,a,/,b,),b,mod(,a,b,),第8页,回顾反思 1辗转相除法算法；2怎样实现当型循环。,第9页,