1.3.1算法案例PPT课件.ppt

1.31.3算法案例算法案例.表示算法的三种方式：表示算法的三种方式：算法步骤（自然语言）算法步骤（自然语言）程序框图（图形语言）程序框图（图形语言）计算机程序（程序语言）计算机程序（程序语言）复习引入复习引入.3 59 15 问题问题11：在小学，我们已经学过求最大公约数：在小学，我们已经学过求最大公约数的知识，你能求出的知识，你能求出1818与与3030的最大公约数吗？的最大公约数吗？18 30231818和和3030的最大公约的最大公约数是数是23=6.23=6.先用两个数公有的先用两个数公有的质因数质因数连续去除连续去除,一直除到所得一直除到所得的商是互质数为止的商是互质数为止,然后然后把所有的除数连乘起来把所有的除数连乘起来.问题问题2:2:求求8251与与6105的最大公约数的最大公约数?新课讲解新课讲解.辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求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+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最大公约数，的最大公约数，也就是也就是8251和和6105的最大的最大公约公约数数.新课讲解新课讲解.一、辗转相除法（欧几里得算法）一、辗转相除法（欧几里得算法）1、定义：、定义：所谓辗转相除法，就是对于给定的两个所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为数，用较大的数除以较小的数。若余数不为零，则零，则将除数变被除数，余数变除数将除数变被除数，余数变除数，继续，继续上面的除法，直到大数被小数除尽，则这时上面的除法，直到大数被小数除尽，则这时最后的除数就是原来两个数的最大公约数。最后的除数就是原来两个数的最大公约数。辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的算法停止的算法 问题问题3你能把辗转相除法写成算法步骤吗？你能把辗转相除法写成算法步骤吗？研探新知研探新知.第四步第四步,若若r=0,则则m,n的最大公约数等于的最大公约数等于m;否则，返回第二步否则，返回第二步辗转相除法求最大公约数算法步骤：辗转相除法求最大公约数算法步骤：第一步第一步,给定两个正数给定两个正数m,n第二步第二步,计算计算m除以除以n所得到余数所得到余数r第三步第三步,m=n,n=r研探新知研探新知 问题问题4:4:该算法的程序框图如何表示？该算法的程序框图如何表示？.开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否新课讲解新课讲解问题问题5:5:该该程序框图程序框图对应的程对应的程序如何表序如何表述？述？.INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRINT mENDEND开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn=rr=0？是是输出输出m结束结束否否新课讲解新课讲解.问题问题6:6:如果用当型循环结构构造算法，如果用当型循环结构构造算法，求两个正整数求两个正整数m m，n n的最大公约数的程序的最大公约数的程序框图和程序分别如何表示？框图和程序分别如何表示？研探新知研探新知.开始开始输入输入m，n求求m除以除以n的余数的余数rm=nn0？否否输出输出m结束结束是是n=rINPUT mINPUT m，n nWHILE WHILE n n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND.九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等之数，以少减多，更相减损，求其等也，以等数约之。数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是任意给定两个正整数；判断他们是否都是偶数。若是，则用偶数。若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：第二步：以较大的数减较小的数，接着把所得的差以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则直到所得的减数和差相等为止，则这个等数这个等数或或这个这个数与约简的数的乘积数与约简的数的乘积就是所求的最大公约数。就是所求的最大公约数。研探新知研探新知.2、更相减损术、更相减损术（1）算理）算理：所谓更相减损术，就是对于给：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。原来两个数的最大公约数。研探新知研探新知.例例 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数.解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数以大数减小数，并辗转相减，减小数，并辗转相减，即：即：986335;633528;35287;28721;21714;1477.所以，所以，9898与与6363的最大公约数是的最大公约数是7 7。练习：用更相减损术求两个正数练习：用更相减损术求两个正数8484与与7272的最大的最大公约数。公约数。(12)(12)研探新知研探新知.辗转相除法与更相减损术的比较辗转相除法与更相减损术的比较:（1 1）都是求最大公约数的方法，计算上辗）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别别当两个数字大小区别较大时计算次数的区别较明显。较明显。（2 2）从结果体现形式来看，辗转相除法体）从结果体现形式来看，辗转相除法体现结果是以相除余数为现结果是以相除余数为0 0则得到，而更相减损术则得到，而更相减损术则以减数与差相等而得到则以减数与差相等而得到.研探新知研探新知.1：用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果分析：将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可解：用辗转相除法：803628，36844，8420.故80和36的最大公约数是4.课堂测试课堂测试.2、分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168168与与9393的最大公约的最大公约数数.辗转相除法：辗转相除法：168=931+75168=931+75，93=751+1893=751+18，75=184+375=184+3，18=36.18=36.更相减损术更相减损术:168-93=75:168-93=75，93-75=1893-75=18，75-18=5775-18=57，57-18=3957-18=39，39-18=2139-18=21，21-18=321-18=3，18-3=1518-3=15，15-3=1215-3=12，12-3=912-3=9，9-3=69-3=6，6-3=3.6-3=3.课堂测试课堂测试.3求三个数175、100、75的最大公约数分析：求三个数的最大公约数时，可以先求出其中两个数的最大公约数，用这个最大公约数再与第三个数求最大公约数，所得结果就是这三个数的最大公约数解：(辗转相除法)：先求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次除法答案：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.1.辗转相除法，就是对于给定的两个正整数，辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数来两个数的最大公约数.2.2.更相减损术，就是对于给定的两个正整数，更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公数相等，此时相等的两数即为原来两个数的最大公约数约数.小结与作业小结与作业.3 3、辗转相除法与更相减损术的区别、辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。大小区别较大时计算次数的区别较明显。（2 2）从结果体现形式来看，辗转相除法体现结果）从结果体现形式来看，辗转相除法体现结果是以相除余数为是以相除余数为0 0则得到，而更相减损术则以减数与则得到，而更相减损术则以减数与差相等而得到差相等而得到小结与作业小结与作业课本课本P48页练习页练习T1;.