1、算法案例_1理解算法案例的算法步骤和程序框图.2引导学生得出自己设计的算法程序.3. 体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.1求两个正整数最大公约数的算法(1)更相减损之术(等值算法)用两数中较大的数减去较小的数，再用差数和较小的数构成新的一对数，再用大数减小数，以同样的操作一直做下去，直到产生一对相等的数，这个数就是最大公约数(2)用“等值算法”求最大公约数的程序while aab bba end2割圆术用圆内接正多边形面积逐渐逼近圆的面积的算法是计算圆周率的一种方法3.秦九韶算法:把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式： f(x
2、)anxnan1xn1a1xa0 (anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0 (anxan1)xan2)xa1)xa0求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值这样通过一次式的反复运算，逐步得出高次多项式的值的方法称作秦九韶算法。观察上述秦九韶算法中的n个一次式可见，只要令其中就得到了一个递推关系。这个递推关系是一个反复执行的步骤，可用循环语句来实现。理解秦九韶算法的关键：一是弄清算法原理是加法对乘法的分配律，二是弄清算法设计中递推关系是一个反复执行的运算，故用循环语句来实现。（1）秦九韶算法过程分析：由于其中
3、k1,2，n.这样我们便可由v0依次求出v1，v2，vn：v1v0xan1，v2v1xan2，v3v2xan3，vnvn1xa0。于是我们用v来记录每次一次式计算的结果，最初赋值van，用vv*xani实现递推循环，i的初值为1，ii1记录循环次数，in控制何时结束循环输出v.f(x)的系数ak用一个循环语句实现输入。（2）f(x)anxnan1xn1a1xa0当xx0时，求函数值f(x0)的算法设计。程序框图：（3）用秦九韶算法将一个多项式(n次)的至多次乘法和n次加法运算减少为至多n次乘法和n次加法运算，大大提高了运算效率。类型一 用更相减损术求两个正整数的最大公约数 例1：求80和36的
4、最大公约数解析当大数减小数的差等于小数时停止减法，较小的数就是两数的最大公约数答案803644，44368，36828，28820，20812，1284，844.80和36的最大公约数是4.练习1：用更相减损之术分别求下列两组数的最大公约数：(1)78与36； (2)1 515与600.答案(1)(78,36)(42,36)(6,36)(6,30)(6,24)(6,18) (6,12)(6,6)，故78与36的最大公约数为6.(2)1 515600915,915600315,600315285,31528530,28530255,25530225,22530195,19530165,16530
5、135,13530105,1053075,753045,453015,301515，故1 515与600的最大公约数是15.类型二 用辗转相除法求两个正整数的最大公约数 例2：用辗转相除法求546与429的最大公约数.解析用辗转相除法求最大公约数步骤较少，而更相减损术虽然步骤较长，但运算简单答案5461429117，429311778，11717839，78239，故546与429的最大公约数为39.练习1：用辗转相除法求288和123的最大公约数答案288212342，12324239，421393，39133，故3就是288和123的最大公约数.练习2：用辗转相除法求355和60的最大公约
6、数答案35556055，601555，55115，故5就是355和60的最大公约数.类型三 用秦九韶算法求多项式的值 例3：用秦九韶算法求多项式f(x)x50.11x30.15x0.04当x0.3时的值解析(1)用秦九韶算法求多项式的值，首先要将多项式改写，然后由内向外逐次计算. 由于下一次计算要用到上一次的结果，故应认真、细心，确保每个中间结果的准确性(2)当多项式中有几项不存在时，可将这几项的系数看成是0，即0xn.答案将f(x)写为：f(x)x50x40.11x30x20.15x0.04.由秦九韶算法的递推公式，得v01，v1v00.300.3，v2v10.30.110.2，v3v20.
7、300.06，v4v30.30.150.132，v5v40.30.040.079 6，所以当x0.3时，多项式的值为0.079 6.练习1：已知函数f(x)x32x25x6，用秦九韶算法求f(10)的值答案由秦九韶法，得f(x)x32x25x6(x22x5)x6(x2)x5)x6，当x10时，f(10)(102)105)106(8105)10675106756.练习2：已知函数f(x)x32x25x6，用秦九韶算法求f(10)的值答案由秦九韶法，得f(x)x32x25x6(x22x5)x6(x2)x5)x6，当x10时，f(10)(102)105)106(8105)10685106856.练习
8、3：已知多项式f(x)3x52x25x43x3x，则f(2)_.答案34f(x)3x52x25x43x3x3x55x43x32x2x(3x5)x3)x2)x1)x，v03，v13251，v21235，v35228，v482117，v517234.当x2时，多项式的值为34.类型四 求三个正整数的最大公约数 例4：求三个数324、243、270的最大公约数解析求三个数的最大公约数，可先求两数的最大公约数a，然后求a与第三个数的最大公约数b，则b为所求的三数的最大公约数该题解法可推广到求多个数的最大公约数答案324243181,2438130，则324与243的最大公约数为a81.又2708132
9、7,812730，则324,243,270的最大公约数为27.练习1：求324,243和135的最大公约数答案(324,243)(81,243)(81,162)(81,81)则324与243最大公约数为81.又(81,135)(81,54)(27,54)(27,27)，则81与135的最大公约数为27，324、243、135的最大公约数为27.类型五 求两个正整数的最小公倍数 例5：求375、85的最小公倍数解析求两个正整数的最小公倍数，即利用它们的积除以它们的最大公约数本题求法可推广到求多个数的情况答案先求最大公约数，37585435,8535215,351525,15530.375与85的
10、最大公约数是5，375与85的最小公倍数是(37585)56 375.练习1：求80与36的最小公倍数答案先求最大公约数80362836844842080与36的最大公约数为4.80与36的最小公倍数是(8036)4720.1秦九韶算法与直接计算相比较，下列说法错误的是()A秦九韶算法与直接计算相比，大大节省乘法的次数，使计算量减少，并且逻辑结构简单B秦九韶算法减少做乘法的次数，在计算机上也就加快了计算的速度C秦九韶算法减少做乘法的次数，在计算机上也就降低了计算的速度D秦九韶算法避免对自变量x单独做幂的计算，而是与系数一起逐次增长幂次，从而可提高计算的精度答案C2用圆内接正多边形逼近圆，因而得
11、到的圆周率总是_的实际值()A大于等于B小于等于C等于 D小于答案D3用更相减损之术求88与24的最大公约数为()A2 B7C8 D12答案C4三个数72,120,168的最大公约数是_答案245用秦九韶算法计算f(x)9x63x54x46x3x28x1，当x3时的值，需要进行_次乘法和_次加法运算答案666已知f(x)x5x3x2x1，求f(3)的值答案f(x)(x0)x1)x1)x1)x1，v11303，v233110，v3103131，v4313194，v59431283，f(3)(30)31)31)31)31283._基础巩固一、选择题1在秦九韶算法中用到的一种方法是()A消元 B递推
12、C回代 D迭代答案B解析秦九韶算法中用到的是递推法2用更相减损术求294和84的最大公约数时，需要做减法的次数为()A2 B3C4 D5答案C解析(84,294)(84,210)(84,126)(84,42)(42,42)，一共做了4次减法3用秦九韶算法求多项式f(x)x33x22x11的值时，应把f(x)变形为()Ax3(3x2)x11B(x3)x2(2x11)C(x1)(x2)x11D(x3)x2)x11答案D解析f(x)x33x22x11(x3)x2)x11，故选D.4用“等值算法”可求得204与85的最大公约数是()A15 B17C51 D85答案B解析20485119,1198534
13、,853451,513417,341717，204和85的最大公约数是17，故选B.5根据递推公式，其中k1,2，n，可得当k2时，v2的值为()Av2anxan1Bv2(anxan1)xan2Cv2(anxan1)xDv2anxan1x答案B解析根据秦九韶算法知，v2v1xan2，v1anxan1，故选B.6用秦九韶算法求多项式f(x)0.5x54x43x2x1，当x3时的值时，先算的是()A33 B0.535C0.534 D(0.534)3答案C解析把多项式表示成如下形式：f(x)(0.5x4)x0)x3)x1)x1，按递推方法，由内往外，先算0.5x4的值，故选C.二、填空题7117与1
14、82的最大公约数等于_答案13解析(117,182)(117,65)(52,65)(52,13)(39,13)(26,13)(13,13)，所以其最大公约数为13. 8245与75两数的最小公倍数为_答案3 675解析先求245与75的最大公约数(245,75)(170,75)(95,75)(20,75)(55,20) (35,20)(15,20)(5,15)(10,5)(5,5)故245与75的最大公约数为5，245与75的最小公倍数为2457553 675.三、解答题9利用更相减损之术求319和261的最大公约数解析31926158,26158203,20358145,1455887,87
15、5829,582929.即(319,261)(261,58)(203,58)(145,58)(87,58)(58,29)(29,29)故319与261的最大公约数是29.能力提升一、选择题1用秦九韶算法求多项式f(x)1235x8x279x36x45x53x6在x4的值时，v4的值为()A57 B220C845 D3 392答案B解析由秦九韶算法，得v03，v13(4)57，v27(4)634，v334(4)7957，v457(4)8220.2三个数390、455、546的最大公约数是()A65 B91C26 D13答案D解析对于三个数求最大公约数时，先求其中两个数的最大公约数，再用此公约数与
16、第三个数求出最大公约数，此时就是三个数的最大公约数. 3已知f(x)4x53x42x3x2x，用秦九韶算法求f(2)等于()A BC D答案A解析f(x)(4x3)x2)x1)x1)x，f(2)(4(2)3)(2)2)(2)1)(2)1)(2).4用“更相减损之术”求120与75的最大公约数时，需要做减法运算的次数为()A6 B5C4 D3答案C解析(120,75)(45,75)(45,30)(15,30)(15,15)，120与75的最大公约数是15，共进行4次减法运算二、填空题54 830与3 289的最大公约数为_答案23解析(4 830,3 289)(1 541,3 289)(1 54
17、1，1 748)(1 541,207)(1 334,207)(1 127,207)(920,207)(713,207)(506,207)(299,207)(92,207)(92,115)(92,23)(69,23)(46,23)(23,23)6用秦九韶算法求多项式f(x)7x55x410x310x25x1当x2时的值的算法：第一步，x2.第二步，f(x)7x55x410x310x25x1.第三步，输出f(x)第一步，x2.第二步：f(x)(7x5)x10)x10)x5)x1.第三步，输出f(x)需要计算5次乘法、5次加法需要计算9次乘法、5次加法以上说法中正确的是_(填序号)答案解析是直接求解
18、，并不是秦九韶算法，故错对于一元n次多项式，应用秦九韶算法需要运用n次乘法和n次加法，故正确三、解答题7求1 356和2 400的最小公倍数解析(1 356,2 400)(1 356,1 044)(312，1 044)(312,732)(321,420)(312，108)(204,108)(96,108)(96,12)(12,12)1 356和2 400的最大公约数为12.1 356和2 400的最小公倍数为(2 4001 356)12271 200.8用秦九韶算法求多项式f(x)20.35x1.8x23x36x45x5x6在x1时的值时，令v0a6，v1v0xa5，vtv5xa0，求v3的值
19、解析f(x)(x5)x6)x3)x1.8)x0.35)x2，v01，v1v0x56，v2v1x66(1)612，v3v2x315.9有甲、乙、丙三种溶液，质量分别为147 g,343 g,133 g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，则每个小瓶最多装多少溶液？解析每个小瓶内溶液的质量应是147,343,133三种溶液质量的公约数，最大质量即是其最大公约数. 先求147和343的最大公约数343147196,19614749,1474998,984949，所以147和343的最大公约数是49.再求49和133的最大公约数1334984,844935,493514，351421,21147,1477，所以49和133的最大公约数是7.所以147,343,133的最大公约数是7，即每个小瓶最多装7 g溶液
