高中数学 第一章 算法初步 1_3 中国古代数学中的算法案例课堂探究 新人教b版必修31

我们在这里，召开私营企业家联谊会，借此机会，我代表成都市渝中工商局、渝中区私营企业协会，祝各位领导新年快乐、工作愉快、身体健康，祝各位企业家事业兴旺高中数学 第一章 算法初步 1.3 中国古代数学中的算法案例课堂探究 新人教B版必修31辗转相除法与更相减损之术的异同剖析：相同点：都是求最大公约数的方法更相减损之术的理论依据为：由mnr，得mnr，可以看出，m，n与n，r有相同的公约数；辗转相除法的理论依据是：由mnqr可以看出，m，n和n，r有相同的公约数，即二者的“算理”相似不同点：更相减损之术进行的是减法运算，辗转相除法进行的是除法运算，计算次数上辗转相除法计算次数相对较少结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损之术则以减数与差相等而得到2.秦九韶算法是多项式求值最先进的方法剖析：(1)秦九韶算法把求一个n次多项式的值转化为求n个一次多项式的值，即把求f(x)anxnan1xn1a1xa0的值转化为求递推公式(k1,2, ，n)中vn的值，所以我们可以将这个递推关系通过循环结构编写程序在计算机上来实现(2)运算次数减少，只需至多n次乘法和n次加法运算，而直接求和所用乘法的次数为，加法的次数为n次，从而大大提高了运算效率计算机做一次乘法运算需要的时间是做加法运算的几倍到十几倍，衡量一个算法“优”“劣”的标准之一就是运算效率，减少乘法运算的次数也就加快了计算速度所以说，秦九韶算法是多项式求值的最先进的算法3教材中的“探索与研究”古希腊求两个正整数的最大公约数的方法是辗转相除法(即欧几里得算法)：用较大的数除以较小的数所得的余数和较小的数构成新的一对数，继续做上面的除法，直到大数被小数除尽，这个较小的数就是最大公约数以求288和123的最大公约数为例，操作如下：(288,123)(42,123)(42,39)(3,39)想一想这种算法的道理试着编写程序在计算机上实现剖析：欧几里得辗转相除法求正整数a，b(ab)的最大公约数的步骤是：计算出ab的余数r，若r0，则b为a，b的最大公约数；若r0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为零，此时的除数即为a，b的最大公约数从其算法思想我们可以看出，辗转相除法的基本步骤是用较大的数(用a表示)除以较小的数(用b表示)，得到除式：anbr(0rb)由于这是一个反复执行的步骤，且执行的次数由余数r是否等于0决定，所以我们可以把它看做一个循环体，用循环结构就可以来实现其算法程序略【例1】 分别用辗转相除法和更相减损之术求下列两数的最大公约数(1)261,319；(2)1 734,816.分析：使用辗转相除法可依据mnqr，反复执行，直到r0为止；用更相减损之术就是根据mnr，反复执行，直到nr为止解：(1)辗转相除法：3192611(余58)261584(余29)58292(余0)319与261的最大公约数是29.更相减损之术：(261,319)(261,58)(203,58)(145,58)(87,58)(29,58)(29,29)319与261的最大公约数是29.(2)辗转相除法：1 7348162(余102)，8161028(余0)，1 734与816的最大公约数是102.更相减损之术：因为两数皆为偶数，首先除以2得到867,408，再求867与408的最大公约数.(867,408)(459,408)(51,408)(51,357)(51,306)(51,255)(51,204)(51,153)(51,102)(51,51)1 734与816的最大公约数是512102.反思 对于第二个问题，用更相减损之术求解时，最后的结论有的同学可能会写成51，而没有乘以2，从而得出与用辗转相除法不一样的答案，51是它们的公约数，2也是它们的公约数，所以最大公约数就为512102.【例2】 求375,85两数的最小公倍数分析：两数的最小公倍数就是两数之积与此两数最大公约数的商解：先求最大公约数，37585435,8535215，351525，15530，375与85的最大公约数是5，375与85的最小公倍数是3758556 375.反思 先求最大公约数，因为两数的最小公倍数就是两数之积与两数最大公约数的商，所以这种方法也可以推广到n(n3)个数的情况.【例3】 用秦九韶算法计算多项式f(x)x612x560x4160x3240x2192x64当x2时的值分析：用秦九韶算法计算多项式的值，关键是正确地将多项式改写，然后由内向外依次计算求得解：先将多项式f(x)进行改写：f(x)x612x560x4160x3240x2192x64(x12)x60)x160)x240)x192)x64.然后由内向外计算得v01，v1v0xa5121210，v2v1xa41026040，v3v2xa340216080，v4v3xa280224080，v5v4xa180219232，v6322640.所以当x2时多项式f(x)的值为f(2)0.反思 有的同学习惯于常规解法，可能会直接代入求解，但这种算法计算机在执行时要进行20次乘法和6次加法运算，而利用秦九韶算法只需进行6次乘法、6次加法运算即可