（苏教版必修3）数学：1.4《算法案例》课件.

课件9张PPT。辗转相除法
与
最大公约数,最小公倍数问题情境 求18和30的最大公约数 结论18和30的最大公约数为618和30的最小公倍数为90 (牢记方法!)问题1 求204与85的最大公约数 问题2 求8251与6105的最大公约数 204与85的最大公约数是17 8251与6105的最大公约数是34 辗转相除法: 我们可以证明，对于任意两个正整数，上述步骤总可以在有限步之后完成，从而总可以用辗转相除的方法求出最大公约数 算法设计 :
如何用辗转相除法找出两个正整数a,b的最大公约数？ (1)结合问题1和问题2，应该利用什么结构实现该算法? （循环结构） (2)每一次循环中所进行的是什么样的运算？ （求a÷b的余数） (3)下一次循环的输入整数应该是什么？循环何时结束？ 设a>b,a除以b的余数为r(b>r),则下一次循环的两个数为b,r.
直到r=0为止.算法 S1 输入两个正整数a,b
（a＞b）；
S2 若Mod（a,b）＝0，
则输出最大公约数b，
算法结束；否则r?
Mod（a,b），a? b，
b?r，转S2． 流程图 伪代码 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) 例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分析：解题关键就是：a－int(a/b)×b＝mod(a,b) 回顾反思 1．辗转相除法的算法； 2．如何实现当型循环。