1.3.1算法案例

《1.3.1算法案例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.3算法案例（第一课时）表示算法的三种方式：算法步骤（自然语言）程序框图（图形语言）计算机程序（程序语言）复习引入315945[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与90的最大公约数吗？189023∴18和90的最大公约数是2×3×3=18.先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.[问题2]:求8251与6105的最大公约数?新课讲解153辗转相除法（欧几里得算法）观察用辗转相除法求8251和6105的最大公约数的过程第一步用两数中较大的数除以较小的数，求得商和余数825

2、1=6105×1+2146结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。第二步对6105和2146重复第一步的做法6105=2146×2+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。为什么呢？思考：从上述的过程你体会到了什么？新课讲解完整的过程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0显然37是1

3、48和37的最大公约数，也就是8251和6105的最大公约数新课讲解一、辗转相除法（欧几里得算法）1、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将除数变被除数，余数变除数，继续上面的除法，直到大数被小数除尽，则这时最后的除数就是原来两个数的最大公约数。辗转相除法是一个反复执行直到余数等于0停止的算法[问题3]你能把辗转相除法写成算法步骤吗？研探新知第四步,若r=0,则m,n的最大公约数等于m;否则，返回第二步辗转相除法求最大公约数算法步骤：第一步,给定两个正数m,n第二步,计算m除以n所得到余数r第三步,

4、m=n,n=r研探新知[问题4]:该算法的程序框图如何表示？开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否新课讲解问题5:该程序框图对应的程序如何表述？INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否新课讲解问题6:如果用当型循环结构构造算法，求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？研探新知开始输入m，n求m除以n的余数rm=nn>0？否输出m结束是n=rINPUTm，nWHILEn>0r=mMODnm

5、=nn=rWENDPRINTmEND《九章算术》——更相减损术算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。研探新知2、更相减损术（1）算理：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行

6、此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。研探新知例用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝35;63－35＝28;35－28＝7;28－7＝21;21－7＝14;14－7＝7.所以，98与63的最大公约数是7。练习：用更相减损术求两个正数84与72的最大公约数。(12)研探新知辗转相除法与更相减损术的比较:（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区

7、别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.研探新知1：用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果．分析：将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可．解：用辗转相除法：80＝36×2＋8，36＝8×4＋4，8＝4×2＋0.故80和36的最大公约数是4.课堂测试2、分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：168=93×1+75，93=75×1+18，75=18×4+3，18=3×6.更相

8、减损术:168-93=75，93-75=18，75-18=57，57-18=39，39-18=21，21-18=3，18-3=15，15