数学必修三131辗转相除法与更相减损术.ppt

《数学必修三131辗转相除法与更相减损术.ppt》由会员分享，可在线阅读，更多相关《数学必修三131辗转相除法与更相减损术.ppt（20页珍藏版）》请在三一办公上搜索。

1、1.3 算法案例,第一课时,案例一辗转相除法与更相减损术,知识探究（一）:辗转相除法（欧几里得算法）,知识探究（一）:辗转相除法（欧几里得算法）,3 5,9 15,18 30,2,3,18和30的最大公约数是23=6.,知识探究（一）:辗转相除法（欧几里得算法）,2146=18131+333，,148=374+0.,333=1482+37，,1813=3335+148，,8251=61051+2146，,6105=21462+1813，,8251和6150的最大公约数是37.,辗转相除法（或欧几里得算法）！,第一步,给定两个正数m,n(假定mn)第二步,计算m除以n所得到余数r第三步,m=n,

2、n=r第四步,若r=0,则m,n的最大公约数等于m;否则返回第二步,思考4：用辗转相除法（欧几里得算法）求最大公约数算法：,思考5:该算法的程序框图如何表示？,思考6:该程序框图对应的程序如何表述？,INPUT m，n,DO,r=m MODn,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,理论迁移,(1)1515，600(2)117，182,例1 用辗转相除法求下列各数的最大公约数.,答案：(1)15(2)13,知识探究（二）:更相减损术,98-63=35，,14-7=7.,21-7=14，,28-7=21，,35-28=7，,63-35=28，,理论迁移,用辗转相除法

3、求80和36的最大公约数，并用更相减损术检验所得结果.,练习,小结作业,小结作业,作业：P45T1 P48AT1.,更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，输入两个正整数m，n(mn).,第二步，计算m-n所得的差k.,第三步，比较n与k的大小，其中大者用m表 示，小者用n表示.,第四步，若m=n，则m，n的最大公约数等于 m；否则，返回第二步.,思考3:该算法的程序框图如何表示？,思考4:该程序框图对应的程序如何表述？,INPUT m，n,WHILE mn,k=m-n,IF nk THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,