新课标人教A版高中数学必修三1.3.1算法案例课件

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

2、105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。第二步 对6105和2146重复第一步的做法6105=21462+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。 新课讲解完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0显然37是148和37的最大公约数，也就是8251和6105的最大公约数.新课讲解一、辗转相除法（欧几里得算法）1、定义： 所谓辗转相除法，就是对于给定的两个数，用较大的数除

3、以较小的数。若余数不为零，则将除数变被除数，余数变除数，继续上面的除法，直到大数被小数除尽，则这时最后的除数就是原来两个数的最大公约数。辗转相除法是一个反复执行直到余数等于0停止的算法 问题3你能把辗转相除法写成算法步骤吗？研探新知第四步,若r=0,则m,n的最大公约数等于m;否则，返回第二步辗转相除法求最大公约数算法步骤：第一步,给定两个正数m,n第二步,计算m除以n所得到余数r第三步,m=n,n=r研探新知问题4:该算法的程序框图如何表示？开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否新课讲解问题5:该程序框图对应的程序如何表述？INPUT m，nDOr=m MOD n

4、m=nn=rLOOP UNTIL r=0PRINT mEND开始输入m，n求m除以n的余数rm=nn=rr=0？是输出m结束否新课讲解问题6:如果用当型循环结构构造算法，求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？研探新知开始输入m，n求m除以n的余数rm=nn0？否输出m结束是n=rINPUT m，nWHILE n0r=m MODnm=nn=rWENDPRINT mEND九章算术更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较

5、大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数。研探新知2、更相减损术（1）算理：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。研探新知例 用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减， 即：986335; 633528; 35287; 28721; 21714; 1477.所

6、以，98与63的最大公约数是7。练习：用更相减损术求两个正数84与72的最大公约数。 (12)研探新知辗转相除法与更相减损术的比较: （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.研探新知1：用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果分析：将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可解：用辗转相除法： 803628， 36844

7、， 8420.故80和36的最大公约数是4.课堂测试2、分别用辗转相除法和更相减损术求168与93的最大公约数. 辗转相除法：168=931+75， 93=751+18， 75=184+3， 18=36.更相减损术:168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3.课堂测试3求三个数175、100、75的最大公约数分析：求三个数的最大公约数时，可以先求出其中两个数的最大公约数，用这个最大公约数再与第三个数求最大公约数，所得结果就是这三个数的最大公约

8、数解：(辗转相除法)：先求175与100的最大公约数：175100175，10075125，75253.175与100的最大公约数是25.课堂测试以下再求25与75的最大公约数：7525325和75的最大公约数是25.故25是75和25的最大公约数，也就是175、100、75的最大公约数课堂测试1.(2011宁夏模拟)用辗转相除法计算60与48的最大公约数时，需要做的除法次数是()A1B2C3 D4解析：6048112,481240.仅需要两步运算答案：B随堂练习2用辗转相除法求294和84的最大公约数时，需要做除法的次数是()A1B2C3 D4解析：29484342,84422.故需做2次除

9、法答案：B随堂练习3求378和90的最大公约数解：37890418,90185，378和90的最大公约数是18.随堂练习4：求三个数324,243,108的最大公约数解：先求324与243的最大公约数，324243181，243813，324与243的最大公约数为81.下面再求108与81的最大公约数：1088127，81273.108与81的最大公约数是27.故324,243,108的最大公约数为27.随堂练习 1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.小结与作业3、辗转相除法与更相减损术的区别（1）