1.3小学数学算法案例（一）PPT课件.ppt

<p><span id="_baidu_bookmark_start_0" style="display: none; line-height: 0px;">‍</span>1.3 算法案例算法案例1.辗转相除法与更相减损术秦九韶算法进位制2.辗转相除法与更相减损术3.1、求两个正整数的最大公约数、求两个正整数的最大公约数（1）求）求25和和35的最大公约数的最大公约数（2）求）求225和和135的最大公约数的最大公约数2、求、求8251和和6105的最大公约数的最大公约数 25（1）55357所以，所以，25和和35的最大公约数为的最大公约数为5所以，所以，225和和135的最大公约数为的最大公约数为533=45课前复习225（2）545135273159知识回顾：知识回顾：先用先用两个数公有的质两个数公有的质因数连续去除，因数连续去除，一直除到所得的一直除到所得的商是互质数为止，商是互质数为止，然后把所有的除然后把所有的除数连乘起来数连乘起来3354.辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得用两数中较大的数除以较小的数，求得商商和和余数余数8251=61051+2146结论：结论：8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，只要求出的最大公约数，只要求出6105和和2146的公约数的公约数就可以了。就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大的最大公约数。公约数。5.完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大公约的最大公约数，也就是数，也就是8251和和6105的最的最大公约数大公约数 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考1：从上面的两个例子可以看出计：从上面的两个例子可以看出计算的规律是什么？算的规律是什么？S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3：重复：重复S1，直到余数为，直到余数为06.第一步第一步,给定两个正数给定两个正数m m、n n第二步第二步,计算计算m m除以除以n n所得到余数所得到余数r r第三步第三步,m=n,m=n；n=rn=r第四步第四步,若若r=0,r=0,则则m m、n n的最大公约数等于的最大公约数等于m;m;否则返回第二步否则返回第二步辗转相除法求最大公约数算法：辗转相除法求最大公约数算法：辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止停止的步骤，这实际上是一个循环结构。的步骤，这实际上是一个循环结构。7.否否开始开始 输入两个正数输入两个正数m,nmn?r=m MOD nr=0?输出输出m结束结束m=xm=nn=r否否是是是是INPUT m,nIF m=0 PRINT “i=”;IINPUT “ai=”;a v=v*x+a i=i-1WENDPRINT vEND输入输入ai22.P45 P45 练习练习2 223.</p>