13算法案例(第1课时)学案（人教A版必修3）

1、第一课时辗转相除法与更相减损术、秦九韶算法1理解辗转相除法与更相减损术的含义，了解其执行过程，并会求最大公约数2掌握秦九韶算法的计算过程，了解它提高计算效率的实质，并会求多项式的值3进一步体会算法的基本思想1辗转相除法与更相减损术(1)辗转相除法算法步骤：第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数r.第三步，mn，nr.第四步，若r_，则m，n的最大公约数等于m；否则返回第_步程序框图如图所示程序：INPUTm，nDOrm MOD nmnnrLOOP UNTIL_PRINT_END(2)更相减损术算法分析：第一步，任意给定两个正整数，判断它们是否都是_若是，用_约简；若不是，

2、执行第二步第二步，以较大的数_去较小的数，接着把所得的差与较小的数比较，并以_数减_数继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数【做一做1】 用更相减损术求294和84的最大公约数时，第一步是_2秦九韶算法(1)概念：求多项式f(x)anxnan1xn1a1xa0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个_多项式的值，共进行_次乘法运算和_次加法运算其过程是：改写多项式为：f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1

3、)xa0(anxan1)xan2)xa1)xa0.设v1_，v2v1xan2，v3v2xan3，vn_.(2)算法步骤：第一步，输入多项式的次数n、最高次项的系数an和x的值第二步，将v的值初始化为an，将i的值初始化为n1.第三步，输入i次项的系数ai.第四步，vvxai，i_.第五步，判断i是否大于或等于_若是，则返回第三步；否则，输出多项式的值_(3)程序框图如图所示(4)程序：INPUT“n”；nINPUT“an”；aINPUT“x”；xvain1WHILE_PRINT“i”；iINPUT“ai”；av_ii1WENDPRINT_END【做一做2】 设计程序框图，用秦九韶算法求多项式的

4、值，所选用的结构是()A顺序结构B条件结构C循环结构D以上都有答案：1(1)0二r0m(2)偶数2减大小【做一做1】 用2约简由于294和84都是偶数，先用2约简2(1)一次nnanxan1vn1xa0(2)i10v(4)i0v xav【做一做2】 D1更相减损术与辗转相除法的区别与联系剖析：如表所示辗转相除法更相减损术区别以除法为主两个整数差值较大时运算次数较少相除余数为零时得结果.以减法为主两个整数的差值较大时，运算次数较多相减，差与减数相等得结果相减前要做是否都是偶数的判断.联系都是求最大公约数的方法二者的实质都是递归的过程二者都要用循环结构来实现.2秦九韶算法是比较先进的算法剖析：计算

5、机的最重要特点就是运算速度快.2003年2月26日，以色列科学家宣布研制出一台依靠DNA运行、速度达每秒运算330万亿次的生物计算机这种计算机的运算速度比现在普通计算机的运算速度要快10万倍，但是即便如此，计算机也不是万能的同一个问题有多种算法，如果某个算法比其他算法的步骤少，运算的次数少，那么这个算法就是比较先进的算法算法好坏的一个重要标志就是运算的次数越少越好求多项式f(x)anxnan1xn1a1xa0的值时，通常是先计算anxn，进行n次乘法运算；再计算an1xn1，进行n1次乘法运算；这样继续下去共进行nn121(其计算方法以后学习)次乘法运算，还需要进行n次加法运算，总共进行n次运

6、算但是用秦九韶算法时，改写多项式为f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xa2)xa1)xa0.先计算v1anxan1，需1次乘法运算，1次加法运算；v2v1xan2，需1次乘法运算，1次加法运算；vnvn1xa0，需1次乘法运算，1次加法运算所以需进行n次乘法运算，n次加法运算，共进行2n次运算由于2n0，则n2n.因此说秦九韶算法与其他算法相比运算次数少，秦九韶算法是比较先进的算法题型一 求最大公约数【例题1】 (1)用辗转相除法求840与1 785的最大公约数；(2)用更相减损术求612与46

7、8的最大公约数分析：本题是关于辗转相除法和更相减损术的直接应用辗转相除法的操作是较大的数除以较小的数；更相减损术的操作是以大数减小数反思：(1)利用辗转相除法求最大公约数时经常会取错最后一个余数因为辗转相除法有有限个除法式子，而最后一个余数在倒数第二个式子的最后(2)利用更相减损术求解最大公约数时，最大公约数是直到差等于减数时的那个差，或是该差与约简的数的乘积题型二 求多项式的值【例题2】 用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值分析：解决本题首先需要将原多项式化成f(x)(7x6)x5)x4)x3)x2)x1)x的形式，其次再弄清v0，v1，v2，v7分

8、别是多少，再针对这些式子进行计算反思：本题中比较容易出现的问题主要集中在计算上，多步计算必须保证每一步的正确性，否则最后不但将题目算错，而且浪费了宝贵的时间题型三 易错辨析【例题3】 已知f(x)3x42x24x2，利用秦九韶算法求f(2)的值错解：f(x)(3x22)x4)x2，v13×(2)2214；v214×(2)424；v324×(2)250.故f(2)50.错因分析：所求f(2)的值是正确的，但是错解中没有抓住秦九韶算法原理的关键，正确改写多项式，并使每一次计算只含有x的一次项答案：【例题1】 解：(1)用辗转相除法求840和1 785的最大公约数1 7

9、85840×2105，840105×8.所以840和1 785的最大公约数是105.(2)首先612和468都是偶数，所以用2约简，得到306和234，但它们还都是偶数，需要再用2约简，得到153和117，最后用更相减损术计算得15311736，1173681，813645，45369，36927，27918，1899.所以612和468的最大公约数是9×2×236.【例题2】 解：f(x)(7x6)x5)x4)x3)x2)x1)x，所以有v07；v17×3627；v227×3586；v386×34262；v4262

10、5;33789；v5789×322 369；v62 369×317 108；v77 108×321 324.故当x3时，多项式f(x)7x76x65x54x43x32x2x的值为21 324.【例题3】 正解：f(x)3x40·x32x24x2(3x0)x2)x4)x2，v13×(2)06；v26×(2)214；v314×(2)424；v424×(2)250.故f(2)50.1用更相减损术可求得78与36的最大公约数是()A24 B18 C12 D62用秦九韶算法计算f(x)3x64x55x46x37x28x1当x

11、0.4时的值，需要进行乘法运算和加法运算的次数分别为()A6,6 B5,6 C6,5 D6,123利用辗转相除法求3 869与6 497的最大公约数时，第二步是_4用秦九韶算法求多项式f(x)x55x410x310x25x1在x2时的值为_5用辗转相除法求242与154的最大公约数答案：1D先用2约简得39,18；然后辗转相减得391821，21183，18315,15312,1239,936，633.所以所求的最大公约数为3×26.2A改写多项式f(x)(3x4)x5)x6)x7)x8)x1，则需进行6次乘法和6次加法运算33 8692 628×11 241第一步：6 4973 869×12 628，第二步：3 8692 628×11 241.41改写多项式为f(x)(x5)x10)x10)x