必修三算法案例课件省公共课一等奖全国赛课获奖课件.pptx

算法案例辗转相除法辗转相除法更相减损术更相减损术秦九韶算法秦九韶算法进位制进位制第1页辗转相除法辗转相除法第2页1、求两个正整数最大条约数、求两个正整数最大条约数（1）求）求25和和35最大条约数最大条约数（2）求）求49和和63最大条约数最大条约数2、求、求8251和和6105最大条约数最大条约数 25（1）55357所以，所以，25和和35最大条约数为最大条约数为5第3页辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105最大条约数过程最大条约数过程 第一步第一步 用两数中较大数除以较小数，求得商和余数用两数中较大数除以较小数，求得商和余数8251=61051+2146结论：结论：8251和和6105条约数就是条约数就是6105和和2146条约数，求条约数，求8251和和6105最最大条约数，只要求出大条约数，只要求出6105和和2146条约数就能够了。条约数就能够了。第二步第二步 对对6105和和2146重复第一步做法重复第一步做法6105=21462+1813同理同理6105和和2146最大条约数也是最大条约数也是2146和和1813最大条约数。最大条约数。第4页完整过程完整过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37最大条约数，最大条约数，也就是也就是8251和和6105最大条约数最大条约数 思索思索1：从上面两个例子能够看出计算：从上面两个例子能够看出计算规律是什么？规律是什么？S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3：重复：重复S1，直到余数为，直到余数为0第5页 辗转相除法是一个重复执行直到余数等于辗转相除法是一个重复执行直到余数等于0停顿停顿步骤，这实际上是一个循环结构。步骤，这实际上是一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m=n q r用程序框图表示出右边过程用程序框图表示出右边过程r=m MOD nm=nn=rr=0?是否第6页九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子之数，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。以少减多，更相减损，求其等也，以等数约之。第一步：第一步：任意给顶两个正整数；判断他们是否都是任意给顶两个正整数；判断他们是否都是偶数。若是，则用偶数。若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：第二步：以较大数减较小数，接着把所得差与较小以较大数减较小数，接着把所得差与较小数比较，并以大数减小数。继续这个操作，直到所数比较，并以大数减小数。继续这个操作，直到所得减数和差相等为止，则这个等数就是所求最大条得减数和差相等为止，则这个等数就是所求最大条约数。约数。第7页例例3 用更相减损术求用更相减损术求98与与63最大条约数最大条约数解：因为解：因为63不是偶数，把不是偶数，把98和和63以大数减小数，并辗转相减以大数减小数，并辗转相减 9863356335283528728721217141477所以，所以，98和和63最大条约数等于最大条约数等于7 第8页这种算法用了几次乘法？几次加法？这种算法用了几次乘法？几次加法？第9页这种算法用了几次乘法？几次加法？这种算法用了几次乘法？几次加法？5次乘法，次乘法，5次加法次加法.第10页第11页第12页第13页进位制是人们为了计数和运算便而约定记进位制是人们为了计数和运算便而约定记数系统数系统.“满十进一满十进一”就是十进制，就是十进制，“满二满二进一进一”就是二进制，就是二进制，“满满k进一进一”就是就是k进进制制，所以，所以k进制需数进制需数k个数字个数字.判断以下数表示是否正确？判断以下数表示是否正确？(1)12(2)(2)061(7)(3)291(8)第14页普通地，若普通地，若k是一个大于是一个大于1整数，那么整数，那么以以k为基数为基数k进制数进制数能够表示为一串数字连写能够表示为一串数字连写在一起形式：在一起形式：3721=3103+7 102+2 101+1 100110011(2)=125+1 24+023+0 22+121+1 207342(8)=783+3 82+4 81+280第15页将将k进制数转为十进制数：进制数转为十进制数：例例 把二进制数把二进制数110011(2)化为十进制数化为十进制数.解：解：110011(2)=125+1 24+023+0 22+121+1 20 =51第16页练习：把以下数化为十进制数练习：把以下数化为十进制数(1)1011010(2)(2)10212(3)(3)2376(3)第17页将十进制数转为将十进制数转为k进制数：进制数：除除k取余法取余法例例 把把89化为二进制数化为二进制数.例例 把把89化为五进制数化为五进制数.除除2取余法取余法除除5取余法取余法第18页2、十进制转换为二进制、十进制转换为二进制例例2 把把89化为二进制数化为二进制数522212010余数余数11224889222201101注意：注意：1.最终一步商为最终一步商为0，2.将上式各步所得余数将上式各步所得余数从下到上排列从下到上排列，得到：，得到：89=1011001（2）第19页练习练习将下面十进制数化为二进制数？将下面十进制数化为二进制数？（1）10（2）20（3）128（4）256第20页例把例把89化为五进制数化为五进制数3、十进制转换为其它进制、十进制转换为其它进制解：解：依据依据除除k取余法取余法以以5作为除数，对应除法算式为：作为除数，对应除法算式为：所以，所以，89=324（5）。895175350423余数余数第21页练习：完成以下进位制间转化练习：完成以下进位制间转化(1)154(6)=_(7)(2)412(5)=_(7)(3)119(10)=_(6)第22页