rjl《算法案例》课件(人教A版必修3)

《rjl《算法案例》课件(人教A版必修3)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、(1)UNTIL语句的一般格式是:DO循环体LOOPUNTIL条件循环体是否满足条件？直到型循环结构从UNTIL型循环结构分析,计算机执行该语句时,先执行一次循环体,然后进行条件的判断,如果条件不满足,继续返回执行循环体,然后再进行条件的判断,这个过程反复进行,直到某一次条件满足时,不再执行循环体,跳到LOOPUNTIL语句后执行其他语句,是先执行循环体后进行条件判断的循环语句.10/6/2021(2)WHILE语句的一般格式是WHILE条件循环体WEND当计算机遇到WHILE语句时,先判断条件的真假,如果条件符合,就执行WHILE与WEND之间的循环体;然后再检查上述

2、条件,如果条件仍符合,再次执行循环体,这个过程反复进行,直到某一次条件不符合为止.这时,计算机将不执行循环体,直接跳到WEND语句后,接着执行WEND之后的语句.满足条件？循环体是否当型循环结构10/6/2021是是否f(a)f(m)<0?程序框图开始f(x)=x2-2输入误差d和初值a,bb=m否a=m

3、a-b

4、

5、.3算法案例10/6/2021案例1辗转相除法与更相减损术10/6/202135915[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？〖创设情景，揭示课题〗183023∴18和30的最大公约数是2×3=6.先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.[问题2]:我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数?10/6/2021〖研探新知〗1.辗转相除法:例1求两个正数8

6、251和6105的最大公约数。分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数.解：8251＝6105×1＋2146显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。10/6/2021〖研探新知〗1.辗转相除法:例1求两个正数8251和6105的最大公约数。解：8251＝6105×1＋2146;6105＝2146×2＋1813;2146＝1813×1＋333;1813＝333×5

7、＋148;333＝148×2＋37;148＝37×4＋0.则37为8251与6105的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。10/6/2021利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；(m=n×q0+r0)第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；(n=r0×q1+r1)第三步：若r1＝0，则r0为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q

8、2和一个余数r2；(r0=r1×q2+r2)……依次计算直至rn＝0，此时所得到的rn-1即为所求的最大公约数。10/6/2021思考:你能把辗转相除法编成一个计算机程序吗？(1)、算法步骤：第一步：输入两个正整数m,n(m>n).第二步：计算m除以n所得的余数r.第三步：m=n,n=r.第四步：若r＝0,则m,n的最大公约数等于m；否则转到第二步.第五步：输出最大公约数m.10/6/2021(2)、程序框图：开始输入m,nr=mMODnm=nr=0?是否n=r输出m结束10/6/2021(3)、程序：INPUT“m,n=“;m,nDOr=mMODnm=nn=rLOOP

9、UNTILr=0PRINTmEND10/6/2021否4.辗转相除法的程序框图及程序:开始输入两个正数m,nm0m=nn=rr=mMODnWENDPRINTnENDx=nn=m10/6/2021练习1：利用辗转相除法求两数4081与20723的最大公约数.20723=4081×5+318;4081=318×12+265;318=265×1+53;265=53×5+0.10/6/20212