2019年数学新同步湘教版必修2第11章 11.4 算法案例.doc

114算法案例算法案例1辗转相除法辗转相除法用辗转相除法求两个正整数用辗转相除法求两个正整数 a，b(a>b)的最大公约数的算法步骤：的最大公约数的算法步骤：S1：输入两个正整数：输入两个正整数 a，b；S2：计算：计算 a 除以除以 b 所得的余数所得的余数 r，即，即 ra_MOD_b；S3：ab，br；S4：判断：判断 r0 是否成立，若成立，输出最大公约数是否成立，若成立，输出最大公约数 a；否则返回否则返回 S2.2秦九韶算法秦九韶算法功能功能它是一种用于计算它是一种用于计算一元一元 n 次多项式次多项式的值的方法的值的方法改写后的形式改写后的形式f(x)anxnan1xn1a1xa0(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1)xan2)xa1)xa0计算方法计算方法从括号最内层开始，由内向外逐层计算从括号最内层开始，由内向外逐层计算v1anxan1，v2v1xan2，v3v2xan3，vnvn1xa0，这样，求这样，求 n 次多项式次多项式 f(x)的值就转化为求的值就转化为求 n 个一次多项式个一次多项式的的值值辗转相除法与更相减损术有什么区别和联系？辗转相除法与更相减损术有什么区别和联系？提示：提示：名称名称辗转相除法辗转相除法更相减损术更相减损术区别区别以除法为主以除法为主以减法为主以减法为主两个整数差值较大时运算次数较少两个整数差值较大时运算次数较少相除余数为零时得结果相除余数为零时得结果两个整数的差值较大时，运算次数较两个整数的差值较大时，运算次数较多多相减，两数相等得结果相减，两数相等得结果相减前要做是否都是偶数的判断相减前要做是否都是偶数的判断联系联系都是求两个正整数的最大公约数的方法都是求两个正整数的最大公约数的方法二者的实质都是递推的过程二者的实质都是递推的过程二者都要用循环结构来实现二者都要用循环结构来实现辗转相除法的应用辗转相除法的应用用辗转相除法求用辗转相除法求 6 731 与与 2 809 的最大公约数的最大公约数解解 6 7312 809××21 113；2 8091 113××2583；1 113583××1530；583530××153；53053××10.6 731 与与 2 809 的最大公约数为的最大公约数为 53.所谓辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不所谓辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数这时较小的数就是原来两个数的最大公约数1用辗转相除法求用辗转相除法求 123 和和 48 的最大公约数的最大公约数解：解：用辗转相除法求最大公约数的过程如下：用辗转相除法求最大公约数的过程如下：1232××4827，481××2721，271××216，213××63，62××30，所以所以 123 和和 48 的最大公约数为的最大公约数为 3.秦九韶算法的应用秦九韶算法的应用用秦九韶算法计算当用秦九韶算法计算当 x2 时，多项式：时，多项式：f(x)x612x560x4160x3240x2192x64 的值的值解解 将将 f(x)改写为改写为f(x)(x12)x60)x160)x240)x192)x64，由内向外依次计算一次多项式当由内向外依次计算一次多项式当 x2 时的值时的值v01，v11××21210，v210××26040，v340××216080，v480××224080，v580××219232，v632××2640.f(2)0，即，即 x2 时，原多项式的值为时，原多项式的值为 0.秦九韶算法的步骤秦九韶算法的步骤S1：输入多项式次数：输入多项式次数 n、最高次项的系数、最高次项的系数 an和和 x 的值；的值；S2：将：将 v 的值初始化为的值初始化为 an，将，将 k 的值初始化为的值初始化为 n1；S3：输入：输入 k 次项的系数次项的系数 ak；S4：vvxak，kk1；S5：判断：判断 k 是否大于或等于是否大于或等于 0.若是，则返回若是，则返回 S3；否则，输出多项式的值；否则，输出多项式的值 v.2用秦九韶算法求当用秦九韶算法求当 x0.3 时，多项式时，多项式 f(x)x50.11x30.15x0.04 的值的值解：解：根据秦九韶算法，将根据秦九韶算法，将 f(x)写为：写为：f(x)(x0)x0.11)x0)x0.15)x0.04.按照从内到外的顺序，依次计算一次多项式当按照从内到外的顺序，依次计算一次多项式当 x0.3 时的值：时的值：v01；v11××0.300.3；v20.3××0.30.110.2；v30.2××0.300.06；v40.06××0.30.150.132；v50.132××0.30.040.079 6.所以，当所以，当 x0.3 时，多项式的值为时，多项式的值为0.079 6.随堂体验落实随堂体验落实11 037 和和 425 的最大公约数是的最大公约数是( )A51 B17C9 D3解析：解析：选选 B 1 037425××2187，425187××251，18751××334，5134××117，3417××2，即即 1 037 和和 425 的最大公约数是的最大公约数是 17.2用秦九韶算法求多项式用秦九韶算法求多项式 f(x)7x66x53x22.当当 x4 时的值时，先算的是时的值时，先算的是( )A4××416 B7××428C4××4××464 D7××4634解析：解析：选选 D 用秦九韶算法求多项式用秦九韶算法求多项式 f(x)7x66x53x22 当当 x4 时的值时，应先时的值时，应先算算 7××4634.3秦九韶是我国南宋时期的数学家，普州秦九韶是我国南宋时期的数学家，普州(现四川省安岳县现四川省安岳县)人，他在所著的人，他在所著的数书九数书九章章中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法如图所示的程序框图中提出的多项式求值的秦九韶算法，至今仍是比较先进的算法如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例若输入给出了利用秦九韶算法求某多项式值的一个实例若输入 n，x 的值分别为的值分别为 3,2，则输出，则输出 v的值为的值为( )A9 B18C20 D35解析：解析：选选 B 由程序框图知，初始值：由程序框图知，初始值：n3，x2，v1，i2，第一次循环：第一次循环：v4，i1；第二次循环：第二次循环：v9，i0；第三次循环：第三次循环：v18，i1.结束循环，输出当前结束循环，输出当前 v 的值的值 18.故选故选 B.4求两个正整数求两个正整数 840 与与 1 785 的最大公约数的最大公约数_解析：解析：1 785840××2105，840105××8，所以所以 105 为为 840 与与 1 785 的最大公约数的最大公约数答案：答案：1055已知函数已知函数 f(x)x32x25x8，利用秦九韶算法求，利用秦九韶算法求 f(9)的值的值_解析：解析：f(x)x32x25x8(x2)x5)x8，f(9)(92)××95)××98530.答案：答案：5306用秦九韶算法求出当用秦九韶算法求出当 x3 时时 f(x)2x54x33x25x1 的值的值解：解：f(x)(2x0)x4)x3)x5)x1，v02，v12××306，v26××3414，v314××3345，v445××35130，v5130××31391，所以所以 f(3)391.感悟高手解题感悟高手解题妙解题妙解题有甲、乙、丙三种溶液，分别为有甲、乙、丙三种溶液，分别为 4 200 毫升，毫升，3 220 毫升和毫升和 2 520 毫升，现要将它们分毫升，现要将它们分别都装入相同的小瓶，每个瓶子装入液体的体积相同问：要使所有溶液都刚好装满小瓶别都装入相同的小瓶，每个瓶子装入液体的体积相同问：要使所有溶液都刚好装满小瓶且所用瓶子数量最少，则小瓶的容积应为多少毫升？且所用瓶子数量最少，则小瓶的容积应为多少毫升？解解 本题实质是求本题实质是求 4 200,3 220,2 520 的最大公约数先求的最大公约数先求 4 200 和和 3 220 的最大公约的最大公约数：数：4 2003 220××1980，3 220980××3280，980280××3140，280140××2，所以所以 4 200 和和 3 220 的最大公约数是的最大公约数是 140.再求再求 140 和和 2 520 的最大公约数：的最大公约数：2 520140××18，所以所以 140 和和 2 520 的最大公约数是的最大公约数是 140.综上，综上，4 200,3 220, 2 520 的最大公约数是的最大公约数是 140，所以小瓶的容积应为，所以小瓶的容积应为 140 毫升毫升一、选择题一、选择题1用辗转相除法求用辗转相除法求 72 与与 120 的最大公约数时，需要做除法次数为的最大公约数时，需要做除法次数为( )A4 B3C5 D6解析：解析：选选 B 用辗转相除法：用辗转相除法：12072××148,7248××124,4824××2.2用用“辗转相除法辗转相除法”求得求得 459 和和 357 的最大公约数是的最大公约数是( )A3 B9C17 D51解析：解析：选选 D 用辗转相除法：用辗转相除法：459357××1102,357102××351,10251××2.459 与与 357 的最大公约数为的最大公约数为 51.3用秦九韶算法计算多项式用秦九韶算法计算多项式 f(x)3x64x55x46x37x28x1 当当 x2 时的值时，时的值时，需要做乘法和加法的次数分别是需要做乘法和加法的次数分别是( )A6,6 B5,6C5,5 D6,5解析：解析：选选 A 由秦九韶算法将多项式改成如下形式：由秦九韶算法将多项式改成如下形式：f(x)(3x4)x5)x6)x7)x8)x1，按由内到外的顺序，依次计算按由内到外的顺序，依次计算 x2 时的值时的值v03，v13××2410.v210××2515，v315××2636，v436××2765，v565××28138，v6138××21277.这样求多项式的值时，是通过这样求多项式的值时，是通过 6 个一次多项式的值得到的，个一次多项式的值得到的，故进行了故进行了 6 次乘法和次乘法和 6 次加法次加法4已知已知 f(x)x52x33x2x1，应用秦九韶算法计算，应用秦九韶算法计算 x3 时的值时，时的值时，v3的值为的值为( )A27 B11C109 D36解析：解析：选选 D 将函数式化成如下形式将函数式化成如下形式f(x)(x0)x2)x3)x1)x1.由内向外依次计算：由内向外依次计算：v01，v11××303，v23××3211，v311××3336.二、填空题二、填空题5用秦九韶算法求函数用秦九韶算法求函数 f(x)12xx23x32x4，当，当 x1 时的值时，时的值时，v2的结果的结果是是_解析：解析：此题的此题的 n4，a42，a33，a21，a12，a01，由秦九韶算法的递推关系式由秦九韶算法的递推关系式Error!Error!(k1,2，n)，得，得 v1v0xa32××(1)35，v2v1xa25××(1)16.答案：答案：66378 与与 90 的最大公约数为的最大公约数为_解析：解析：辗转相除法：辗转相除法：37890××418，9018××50，所以所以 378 与与 90 的最大公约数是的最大公约数是 18.答案：答案：187已知多项式已知多项式 f(x)3x58x43x35x212x6，则，则 f(2)_.解析：解析：根据秦九韶算法，根据秦九韶算法，把多项式改写成如下形式：把多项式改写成如下形式：f(x)(3x8)x3)x5)x12)x6.按照从内到外的顺序，依次计算一次多项式当按照从内到外的顺序，依次计算一次多项式当 x2 时的值时的值v03，v13××2814，v214××2325，v325××2555，v455××212122，v5122××26238，所以当所以当 x2 时，多项式的值为时，多项式的值为 238.答案：答案：2388324,243,270 三个数的最大公约数为三个数的最大公约数为_解析：解析：324243××181,24381××3，所以，所以 324 与与 243 的最大公约数为的最大公约数为 81.27081××327,8127××3，所以，所以 81 与与 270 的最大公约数为的最大公约数为 27.综上可知，综上可知，324,243,270 三个数的最大公约数为三个数的最大公约数为 27.答案：答案：27三、解答题三、解答题9用辗转相除法求下面两组数的最大公约数用辗转相除法求下面两组数的最大公约数(1)80,36；(2)294,84.解：解：(1)8036××28，368××44，84××20，即即 80 与与 36 的最大公约数是的最大公约数是 4.(2)29484××342，8442××2.即即 294 与与 84 的最大公约数是的最大公约数是 42.10利用秦九韶算法计算多项式利用秦九韶算法计算多项式 f(x)3x42x39x211x1 当当 x4 时的值，写出每时的值，写出每一步的计算表达式一步的计算表达式解：解：根据秦九韶算法将多项式改写成根据秦九韶算法将多项式改写成f(x)(3x2)x9)x11)x1，按由内到外的顺序依次计算一次多项式当按由内到外的顺序依次计算一次多项式当 x4 时的值时的值v03；v13××4214；v214××4947；v347××411177；v4177××41709.x4 时，多项式的值时，多项式的值 f(4)709.1算法与程序框图算法与程序框图(1)算法和程序框图的核心是程序框图的三种基本逻辑结构，它与其他知识，如函数、算法和程序框图的核心是程序框图的三种基本逻辑结构，它与其他知识，如函数、方程方程 、不等式、数列等都有密切的联系，应用非常广泛、不等式、数列等都有密切的联系，应用非常广泛(2)从近几年高考题来看程序框图是考查的重点，主要考查算法基本结构以及读图、识从近几年高考题来看程序框图是考查的重点，主要考查算法基本结构以及读图、识图、利用框图解决简单算法问题的能力图、利用框图解决简单算法问题的能力2基本算法语句基本算法语句(1)基本算法语句是将程序框图转化为程序语句以实现算法的重要手段，是算法的主体基本算法语句是将程序框图转化为程序语句以实现算法的重要手段，是算法的主体内容内容(2)近两年高考题中基本算法语句均未考查，但仍不可忽视不排除以后对基本算法语近两年高考题中基本算法语句均未考查，但仍不可忽视不排除以后对基本算法语句的考查的可能性句的考查的可能性3算法案例算法案例通过阅读中国古代数学中的算法案例，体会算法思想以及中国古代数学对世界数学发通过阅读中国古代数学中的算法案例，体会算法思想以及中国古代数学对世界数学发展的贡献展的贡献程序框图的应用程序框图的应用写出求关于写出求关于 x 的方程的方程 ax2bxc0(a，b，c 为常数为常数)的解的算法步骤，并画的解的算法步骤，并画出程序框图出程序框图解解 算法如下：算法如下：S1：输入：输入 a，b，c；S2：若：若 a0，则执行，则执行 S3；若；若 a0，则执行，则执行 S7；S3：b24ac；S4：若：若 0 AND x 3；243第二次循环，第二次循环，8 不能被不能被 3 整除，整除，N817>3；第三次循环，第三次循环，7 不能被不能被 3 整除，整除，N716>3；第四次循环，第四次循环，6 能被能被 3 整除，整除，N 2<3，结束循环，结束循环，63故输出故输出 N 的值为的值为 2.6已知某算法的程序框图如图所示，若将输出的已知某算法的程序框图如图所示，若将输出的(x，y)值依次记为值依次记为(x1，y1)，(x2，y2)，(xn，yn)，(1)若程序运行中输出的一个数组是若程序运行中输出的一个数组是(9，t)，求，求 t 的值；的值；(2)程序结束时，共输出程序结束时，共输出(x，y)的组数为多少？的组数为多少？(3)写出程序框图的伪代码写出程序框图的伪代码解：解：(1)由程序框图知：当由程序框图知：当 x1 时，时，y0；当当 x3 时，时，y2；当当 x9 时，时，y4，所以所以 t4.(2)当当 n1 时，输出一对，当时，输出一对，当 n3 时，又输出一对，时，又输出一对，当，当 n2 019 时，输出最后时，输出最后一对，共输出一对，共输出(x，y)的组数为的组数为 1 010；(3)程序框图的伪代码如下：程序框图的伪代码如下：