必修三(算法案例)ppt课件

1、.1算法案例辗转相除法辗转相除法更相减损术更相减损术秦九韶算法秦九韶算法进位制进位制.2辗转相除法辗转相除法.31、求两个正整数的最大公约数、求两个正整数的最大公约数（1）求）求25和和35的最大公约数的最大公约数（2）求）求49和和63的最大公约数的最大公约数2、求、求8251和和6105的最大公约数的最大公约数 25（1）55357所以，所以，25和和35的最大公约数为的最大公约数为5.4辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得商和余数用

2、两数中较大的数除以较小的数，求得商和余数8251=61051+2146结论：结论： 8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大的最大公约数，只要求出公约数，只要求出6105和和2146的公约数就可以了。的公约数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。 .5完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=

3、18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最大公约数，的最大公约数，也就是也就是8251和和6105的最大公约数的最大公约数 思考思考1：从上面的两个例子可以看出计算的：从上面的两个例子可以看出计算的规律是什么？规律是什么？ S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3：重复：重复S1，直到余数为，直到余数为0.6 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循停止的步骤，这实际上是一个循环结构。环结构。8

4、251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否.7九章算术九章算术更相减损术更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。其等也，以等数约之。第一步：任意给顶两个正整数；判断他们是否都是偶数。若是，则用第一步：任意给顶两个正整数；判断他们是否都是偶

5、数。若是，则用2约简；若约简；若不是则执行第二步。不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。的最大公约数。.8例例3 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，并辗转相减以大数减小数，并辗转相减 9863356335283528728721217

6、141477所以，所以，98和和63的最大公约数等于的最大公约数等于7 .9这种算法用了几次乘法？几次加法？这种算法用了几次乘法？几次加法？.10这种算法用了几次乘法？几次加法？这种算法用了几次乘法？几次加法？5次乘法，次乘法，5次加法次加法.11.12.13.14进位制是人们为了计数和运算便而约定的记数系统进位制是人们为了计数和运算便而约定的记数系统.“满十进一满十进一”就是十进制，就是十进制，“满二进满二进一一”就是二进制，就是二进制，“满满k进一进一”就是就是k进制，因此进制，因此k进制需数进制需数k个数字个数字.判断下列数表达是否正确？判断下列数表达是否正确？(1) 12(2)(2)

7、061(7)(3) 291(8).15一般地，若一般地，若k是一个大于是一个大于1的整数，那么以的整数，那么以k为基数的为基数的k进制数可以表示为一串数字进制数可以表示为一串数字连写在一起的形式：连写在一起的形式：),0 ,0( 011)(011kaaakaaaaannknn 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.16将将k进制数转为十进制数：进制数转为十进制数：)(011 knnaaaa 001111kakakakannnn 例例 把二进制数把二进

8、制数110011(2)化为十进制数化为十进制数.解：解：110011(2)=125+1 24+ 023+0 22 + 121+1 20 =51.17练习：把下列数化为十进制数练习：把下列数化为十进制数(1) 1011010(2)(2) 10212(3)(3) 2376(3).18将十进制数转为将十进制数转为k进制数：进制数：除除k取余法取余法例例 把把89化为二进制数化为二进制数.例例 把把89化为五进制数化为五进制数.除除2取余法取余法除除5取余法取余法.192、十进制转换为二进制、十进制转换为二进制例例2 把把89化为二进制数化为二进制数522212010余数余数11224889222201101注意：注意：1.最后一步商为最后一步商为0，2.将上式各步所得的余数从下到上排列，得到：将上式各步所得的余数从下到上排列，得到：89=1011001（2）.20练习练习将下面的十进制数化为二进制数？将下面的十进制数化为二进制数？（1）10（2）20（3）128（4）256.21例把例把89化为五进制数化为五进制数3、十进制转换为其它进制、十进制转换为其它进制解：解：根据除根据除k取余法取余法以以5作为除数