《15-16高中数学必修3课件：1.3算法案例第1课时.ppt

鸡兔同笼问题是中国古代数学名著《孙子算法》中的一道名题，题目是这样的：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”书中给出的解法是：鸡有两只脚，兔有四只脚，把脚数除以2，共有47对脚．由于鸡有1对脚，兔有2对脚，所以从47中减去25，得12即为兔子数．因为如要笼子里的动物每只都只有1对脚，就会多出12对脚来，把这12对脚分别加到有2对脚的动物身上，就有12只脚动物，即兔子数．整个解题过程可以简单地写作： 1．辗转相除法与更相减损术 (1)辗转相除法． ①算法步骤： 第一步，给定两个正整数m，n. 第二步，计算m除以n所得的余数r. 第三步，m＝n，n＝r. 第四步，若r＝___，则m，n的最大公约数等于m；否则返回 第___步． ②程序框图如图所示． ③程序： INPUT　m，n DO 　r＝m　MOD　n 　m＝n 　n＝r LOOP UNTIL _______ PRINT　___ END (2)更相减损术． 算法步骤： 第一步，任意给定两个正整数，判断它们是否都是______．若是，用___约简；若不是，执行第二步． 第二步，以较大的数___去较小的数，接着把所得的差与较小的数比较，并以___数减___数．继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． 2．秦九韶算法 (1)概念：求多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求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＝____________， v2＝v1x＋an－2， v3＝v2x＋an－3， …， vn＝___________. (2)算法步骤： 第一步，输入多项式的次数n、最高次项的系数an和x的值． 第二步，将v的值初始化为an，将i的值初始化为n－1. 第三步，输入i次项的系数ai. 第四步，v＝vx＋ai，i＝________. 第五步，判断i是否大于或等于___.若是，则返回第三步；否则，输出多项式的值___. (3)程序框图如图所示． (4)程序： INPUT　“n＝”；n INPUT　“an＝”；a INPUT　“x＝”；x v＝a i＝n－1 WHILE　___________ 　PRINT　“i＝”；i 　INPUT　“ai＝”；a 　v＝_________ 　i＝i－1 WEND PRINT ___ END 1．用辗转相除法求36与134的最大公约数，第一步是(　　) A．134－36＝98　　　 B．134＝36×3＋26 C．先除以2，得到18与67 D．36＝26×1＋10 [答案]　B [解析]　求36与134的最大公约数，第一步是134＝36×3＋26，第二步是36＝26×1＋10，故选D. 2．(2015·河北省廊坊一中月考)用辗转相除法求294和84的最大公约数时，需要做除法的次数是(　　) A．1 B．2 C．3 D．4 [答案]　B [解析]　本题考查辗转相除法的过程.294＝84×3＋42,84＝42×2，故选B. 3．设计程序框图，用秦九韶算法求多项式的值，所选用的结构是(　　) A．顺序结构　 B．条件结构 C．循环结构 D．以上都有 [答案]　D 4．用更相减损术求294和84的最大公约数时，第一步是________． [答案]　用2约简 [解析]　由于294和84都是偶数，先用2约简． 5．(2015·云南省景洪一中月考)用秦九韶算法计算多项式f(x)＝3x6＋2x5＋4x4＋5x3＋7x2＋8x＋1在x＝0.5时的值，需做乘法和加法的次数分别是________． [答案]　6次乘法，6次加法 [解析]　将多项式改写为f(x)＝(((((3x＋2)x＋4)x＋5)x＋7)x＋8)x＋1，化为6个一次因式求解，故只做了6次乘法和6次加法． 用辗转相除法求80和36的最大公约数，并用更相减损术检验所得结果． [探究]　1.辗转相除法与更相减损术的主要区别是什么？ 2．将80作为大数，36作为小数，执行辗转相除法和更相减损术的步骤即可． [解析]　用辗转相除法： 80＝36×2＋8， 36＝8×4＋4， 8＝4×2＋0. 故80和36的最大公约数是4. 用更相减损术检验： 80－36＝44， 44－36＝8， 36－8＝28，