高中数学1.3算法案例1课件新人教A必修3

1.3算法案例(1),辗转相除法与更相减损术,高中数学人教版必修三第一章算法初步,表示算法的三种方式：,算法步骤（自然语言）,程序框图（图形语言）,算法语句（程序语言）,复习引入,315,945,问题1：在小学，我们已经学过求最大公约数的知识，你能求出12与16、18与90的最大公约数吗？,1890,2,3,18和90的最大公约数是233=18.,先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.,问题2:求8251与6105的最大公约数?,新课讲解,15,3,辗转相除法（欧几里得算法）,观察用辗转相除法求8251和6105的最大公约数的过程,第一步用两数中较大的数除以较小的数，求得商和余数8251=61051+2146,结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的最大公约数就可以了。,第二步对6105和2146重复第一步的做法6105=21462+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。,新课讲解,完整的过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,显然37是148和37的最大公约数，也就是8251和6105的最大公约数,新课讲解,一、辗转相除法（欧几里得算法）,1、定义：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将除数变被除数，余数变除数，继续上面的除法，直到大数被小数除尽，则这时最后的除数就是原来两个数的最大公约数。,辗转相除法是一个反复执行直到余数等于0停止的算法,问题3你能把辗转相除法写成算法步骤吗？,研探新知,.第四步,若r=0,则m,n的最大公约数等于m;否则，返回第二步,辗转相除法求最大公约数算法步骤：,第一步,给定两个正数m,n(mn).,第二步,计算m除以n所得到的余数r.,第三步,m=n,n=r.,研探新知,问题4:该算法的程序框图如何表示？,求m除以n的余数r,新课讲解,问题5:该程序框图对应的程序如何表述？,INPUTm，n,DO,r=mMODn,m=n,n=r,LOOPUNTILr=0,PRINTm,END,求m除以n的余数r,m=n,n=r,新课讲解,问题6:如果用当型循环结构构造算法，求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？,研探新知,INPUTm，n,WHILEn0,r=mMODn,m=n,n=r,WEND,PRINTm,END,练习,1.用辗转相除法求下列两数的最大公约数：（1）225,135；（2）98,196；（3）72,168；（4）153,119.,（3）24.,（2）98.,（1）45.,（4）17.,九章算术更相减损术,算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：任意给定两个正整数，判断他们是否都是偶数.若是，则用2约简；若不是,执行第二步。,第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数.继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,研探新知,2、更相减损术,（1）定义：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数.,研探新知,例用更相减损术求98与63的最大公约数.,解：由于63不是偶数，把98和63以大数减小数，并辗转相减，,即：9863356335283528728721217141477,所以，98与63的最大公约数是7.,练习：用更相减损术求两个正数84与72的最大公约数.,(12),研探新知,辗转相除法与更相减损术的比较:,（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.,研探新知,1：用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果分析：将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可解：用辗转相除法：803628，36844，8420.故80和36的最大公约数是4.,课堂测试,80-36=4444-36=836-8=2828-8=2020-8=1212-8=48-4=4,2.求三个数175、100、75的最大公约数分析：求三个数的最大公约数时，可以先求出其中两个数的最大公约数，用这个最大公约数再与第三个数求最大公约数，所得结果就是这三个数的最大公约数解：(辗转相除法)：先求175与100的最大公约数：175100175，10075125，75253.175与100的最大公约数是25.,课堂测试,以下再求25与75的最大公约数：7525325和75的最大公约数是25.故25是75和25的最大公约数，也就是175、100、75的最大公约数,课堂测试,175-100=75100-75=2575-25=5050-25=25,75-25=5050-25=25,1.用辗转相除法计算60与48的最大公约数时，需要做的除法次数是()A1B2C3D4解析：6048112,481240.仅需要两步运算答案：B,随堂练习,2用辗转相除法求294和84的最大公约数时，需要做除法的次数是()A1B2C3D4解析：29484342,84422.故需做2次除法答案：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）都是求最大公约