1.3算法案例（1）

1、1.3 算法案例教学目标1、理解掌握辗转相除法、更相减损术、秦九韶算法以及进位制的含义，了解他们的计算过程。2、提升学生的数学逻辑思维水平，发展有条理的思考与数学表达水平。3、了解古代著名的算法，培养学生的民族自豪感与爱国情怀，激发学生学习的热情。教学重难点重点：辗转相除法、更相减损术、秦九韶算法以及进位制的算法思想，辗转相除法与更相减损术的区别与联系。难点：1、如何选择辗转相除法与更相减损术。 2、理解秦九韶算法的先进性。 3、理解进位制的概念，不同进位制之间的转换。教学过程一、复习引入问题：求18与30的最大公约数通过该例来回忆小学求最大公约数的方法，进而引入辗转相除法与更相减损术，以体现

2、这两种算法的优越性。学生：2 18 30 3 9 15 3 5所以18与30的最大公约数是2*3=6教师：若两个数的公共因子不容易发现，又如何求它们的最大公约数？二、新课讲解例如：求8251与6105的最大公约数分析：如果使用上述方法求最大公约数比较困难，因为我们很难发现这两个数字的公共因子，下面我们介绍一种古老而有效的算法辗转相除法。这种算法是由欧几里得在公元前300年左右首先提出来的，因而又叫欧几里得算法。所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时的较小的数就是原来两个数的最大公约

3、数。用这个思想求解8251与6105的最大公约数8251=6105*1+21466105=2146*2+18132146=1813*1+3331813=333*5+148333=148*2+37148=37*4所以8251与6105的最大公约数是37.说明：这里学生可能要产生疑问：为什么37是8251与6105的最大公约数？教师稍做解释。比如由等式8251=6105*1+2146可知，8251与6105的公约数和6105与2146的公约数相同，从而最大公约数相同，这样求8251与6105的最大公约数就转化为求6105与2146的最大公约数，如此继续下去，除到能够整除为止，即得最大公约数。辗转相

4、除法用的是除法，我们也能够用减法来求两个数的最大公约数，这就是更相减损术。学生阅读课本36页更相减损术相关内容。所谓更相减损术，第一步，任意给定两个正整数，判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数。下面用一个例子说明这个算法。例1 用更相减损术求18与30的最大公约数解：18与30都是偶数，先除以2，得到9与15， 15-9=6 9-6=3 6-3=3 直到2个小的数相等为止，因为开始18与30同时除以了2，所以

5、最后用这两个相等的数字乘以2即3*2=6,6才是18与30的最大公约数。例2 用辗转相除法与更相减损术求98与63的最大公约数解：辗转相除法 更相减损术 98=63*1+35 98-63=35 63=35*1+28 63-35=28 35=28*1+7 35-28=7 28=4*7 28-7=21 最大公约数为7 21-7=14 14-7=7 最大公约数为7对比两种方法，前者的步骤更少，后者的步骤多，如果用更相减损术求例1，要用14步，所以在解题中选择哪种方法较为重要。案例2 秦九韶算法例：求多项式当时的值学生自不过然直接将代入中，但是这样我们要做10次乘法运算，5次加法运算，有没有更有效的算

6、法呢？我国南宋时期的数学家秦九韶在数书九章中提出了下面的算法。（计算时由内到外）所以，当时，多项式的值等于7031这个算法实际上是通过提取公因式将高次降低为低次，这样我们只需要算5次乘法，5次加法。从这里我们能够看出，要算多少次乘法与最高次项的次数相同，要算多少次加法与加号的个数相同。课本38页的思考题，因为最高次项的次数为n，所以需要n次乘法运算，因为有n个加号，所以需要n次加法运算。案例3 进位制1、我们平时最熟悉的进位制是十进制，十进制的数字由0-9这十个数字组成，教师：除了十进制，我们生活中还会出现什么进制？学生：每个星期从星期一到星期天再从星期一到星期天，这是七进制教师：七进制由那些

7、数字组成？学生：0-6教师：在计算机中用的都是二进制，二进制由那些数字组成？学生：0,1从这几个我们生活中的例子，你能发现几进制（这个几叫做基数）的基数与它所构成的数字间有什么联系吗？学生发现:十进制就是0-9，七进制就是0-7，二进制就是0-1，都是从0开始，到的数比基数小1.老师：那么五进制由什么数字组成？学生：0-4大于10的进制借助ABCDEF.这些字母来表示。比如固学案2、进位制的转换3721读作三千七百二十一，3表示3个1千，7表示7个1百，2表示2个十，一表示1，所以，同理，这些都是十进制到十进制的计算，那么由二进制到十进制怎么转换呢？随堂练习：课本48页习题1.3A组第3题（1

8、）、（3）这些都是由k进制转换到十进制，那么十进制如何转换到k进制呢？这里我们采用除k取余法，例如：把89化为二进制数。分析：根据二进制数“满二进一”的原则，可以用2连续去除89或所得商，然后取余数。解：2 89 余数2 44 12 22 02 11 02 5 12 2 12 1 0 0 1也可以用除法算式表示 把上式中各步所得的余数从下到上排列，得到这就是除k取余法，用来将十进制的数转换为k进制的数，要注意最后的余数从下到上排列。三、课堂练习课本45页练习1、2、3四、课堂小结本节课学习了几种古老的算法辗转相除法和更相减损术，这两种方法都可以求数字比较大并且较难发现公共因子的数的最大公约数；秦九韶算法，可