PAGE算法
案例
全员育人导师制案例信息技术应用案例心得信息技术教学案例综合实践活动案例我余额宝案例
（第1课时）1．更相减损术与辗转相除法的区别与联系剖析：如表所示.辗转相除法更相减损术区别①以除法为主．②两个整数差值较大时运算次数较少．③相除余数为零时得结果①以减法为主．②两个整数的差值较大时，运算次数较多．③相减，差与减数相等得结果．④相减前要做是否都是偶数的判断联系①都是求最大公约数的方法．②二者的实质都是递归的过程．③二者都要用循环结构来实现2．秦九韶算法是比较先进的算法剖析：同一个问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
有多种算法，如果某个算法比其他算法的步骤少，运算的次数少，那么这个算法就是比较先进的算法．判断算法是否先进的一个重要标志就是运算的次数越少越好．求多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值时，通常是先计算anxn，进行n次乘法运算；再计算an－1xn－1，进行n－1次乘法运算；这样继续下去共进行n＋n－1＋…＋2＋1＝eq\f(n(n＋1),2)(其计算方法以后学习)次乘法运算，还需要进行n次加法运算，总共进行eq\f(n(n＋1),2)＋n次运算．但是用秦九韶算法时，改写多项式为f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0……＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0.先计算v1＝anx＋an－1，需1次乘法运算，1次加法运算；v2＝v1x＋an－2，需1次乘法运算，1次加法运算；……vn＝vn－1x＋a0，需1次乘法运算，1次加法运算．所以需进行n次乘法运算，n次加法运算，共进行2n次运算．由于eq\b\lc\[\rc\](\a\vs4\al\co1(\f(n(n＋1),2)＋n))－2n＝eq\f(n(n－1),2)≥0，则eq\f(n(n＋1),2)＋n≥2n.因此说秦九韶算法与其他算法相比运算次数少，秦九韶算法是比较先进的算法．题型一求最大公约数【例题1】(1)用辗转相除法求840与1785的最大公约数；(2)用更相减损术求612与468的最大公约数．分析：本题是关于辗转相除法和更相减损术的直接应用．辗转相除法的操作是较大的数除以较小的数；更相减损术的操作是以大数减小数．解：(1)用辗转相除法求840和1785的最大公约数．1785＝840×2＋105，840＝105×8.所以840和1785的最大公约数是105.(2)首先612和468都是偶数，所以用2约简，得到306和234，还是偶数，需要再用2约简，得到153和117，最后用更相减损术计算得153－117＝36，117－36＝81，81－36＝45，45－36＝9，36－9＝27，27－9＝18，18－9＝9.所以612和468的最大公约数是9×2×2＝36.反思求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术．用辗转相除法，即根据a＝nb＋r这个式子，反复相除，直到r＝0为止；用更相减损术，即根据r＝|a－b|这个式子，反复相减，直到r＝0为止.题型二求多项式的值【例题2】用秦九韶算法求多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x当x＝3时的值．分析：解决本题首先需要将原多项式化成f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x的形式，其次再弄清v0，v1，v2，…，v7分别是多少，再针对这些式子进行计算．解：f(x)＝((((((7x＋6)x＋5)x＋4)x＋3)x＋2)x＋1)x，所以有v0＝7；v1＝7×3＋6＝27；v2＝27×3＋5＝86；v3＝86×3＋4＝262；v4＝262×3＋3＝789；v5＝789×3＋2＝2369；v6＝2369×3＋1＝7108；v7＝7108×3＝21324.故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21324.反思秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行.题型三易错辨析【例题3】已知f(x)＝3x4＋2x2＋4x＋2，利用秦九韶算法求f(－2)的值．错解：f(x)＝((3x2＋2)x＋4)x＋2，v1＝3×(－2)2＋2＝14；v2＝14×(－2)＋4＝－24；v3＝－24×(－2)＋2＝50.故f(－2)＝50.错因分析：所求f(－2)的值是正确的，但是错解中没有抓住秦九韶算法原理的关键，正确改写多项式，并使每一次计算只含有x的一次项．正解：f(x)＝3x4＋0·x3＋2x2＋4x＋2＝(((3x＋0)x＋2)x＋4)x＋2，v1＝3×(－2)＋0＝－6；v2＝－6×(－2)＋2＝14；v3＝14×(－2)＋4＝－24；v4＝－24×(－2)＋2＝50.故f(－2)＝50.
浙公网安备 33021202002483