1.3-算法案例知识点-试题及答案

一、知识要点及方法辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：1.若r是a÷b的余数，则gcd(a,b)=gcd(b,r)2.a和其倍数之最大公因子为a。另一种写法是：1.a÷b，令r为所得余数（0≤rb）若r=0，算法结束；b即为答案。2.互换：置a←b，b←r，并返回第一步秦九韶算法的特典在于，它通过一次式的反复计算，逐步得出高次多项式的值。具体地说，它将一个n次多项式的求解问题，归结为重复计算n个一次式avvknkkx1，k=1,2,…,n（1）来实现。这种化繁为简的处理方法在数值分析中是屡见不鲜的。现在考虑秦九韶算法的计算程序。按式（1）计算，每求出一个“新值”vk以后，“老值”vk1便失去继续保存的价值，因此可以将新值vk存放在老值vk1所占用的单元内。这样，我们只要设置一个单元v进行累算，而将式（1）表为下列动态形式vvxakn，k=1,2,…,n执行这组算式之前，应先送初值an到单元v中，van二、试题同步训练1．用更相减损术求294和84的最大公约数时，需做减法的次数是()A．2B．3C．4D．52．若用秦九韶算法求多项式f(x)＝4x5－x2＋2当x＝3时的值，则需要做乘法运算和加减法运算的次数分别为()A．4,2B．5,3C．5,2D．6,23．将二进制数10001(2)化为五进制数为()A．32(5)B．23(5)C．21(5)D．12(5)4．378与90的最大公约数为________．课时训练1．45和150的最大公约数和最小公倍数分别是()A．5,150B．15,450C．450,15D．15,1502．用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2当x＝4的值时，先算的是()A．4×4＝16B．7×4＝28C．4×4×4＝64D．7×4＋6＝343．二进制数算式1010(2)＋10(2)的值是()A．1011(2)B．1100(2)C．1101(2)D．1000(2)4．已知一个k进制的数132与十进制的数30相等，那么k等于()A．7或4B．－7C．4D．都不对5．已知f(x)＝x5＋2x3＋3x2＋x＋1，应用秦九韶算法计算x＝3时的值时，v3的值为()A．27B．11C．109D．366．由389化为的四进制数的末位为()A．3B．2C．1D．07．七进制数中各个数位上的数字只能是________中的一个．8．将八进制数127(8)化成二进制数为________．9．下列各数①111111(2)②210(6)③1000(4)④81(8)最大数为________，最小数为________．10．已知函数f(x)＝x3－2x2－5x＋6，试用秦九韶算法求f(10)的值．11．把110(5)转化为二进制数．12．利用秦九韶算法分别计算f(x)＝8x7＋5x6＋3x4＋2x＋1在x＝2与x＝－1时的值，并判断多项式f(x)在区间[－1,2]有没有零点．答案：1、解析：选C.294－84＝210,210－84＝126,126－84＝42,84－42＝42，故选C.2、解析：选C.f(x)＝4x5－x2＋2＝((((4x)x)x－1)x)x＋2，所以需要做5次乘法运算和2次加减运算．3、解析：选A.将10001(2)化为十进制数为：10001(2)＝1×24＋0×23＋0×22＋0×21＋1×20＝17，将17化为五进制数为32(5)，∴10001(2)＝32(5)．4、解析：辗转相除法：378＝90×4＋18，90＝18×5＋0，∴378与90的最大公约数是18.答案：18课时训练1、解析：选B.利用辗转相除法求45和150的最大公约数：150＝45×3＋15,45＝15×3，所以45和150的最大公约数为15.所以45和150的最小公倍数为15×(45÷15)×(150÷15)＝450，故选B.2、解析：选D.因为f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，所以用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2当x＝4的值时，先算的是7×4＋6＝34.3、解析：选B.1010(2)＋10(2)＝(1×23＋0×22＋1×21＋0×20)＋(1×21＋0×20)＝12＝1100(2)，故选B.4、解析：选C.132(k)＝1×k2＋3×k＋2＝k2＋3k＋2，∴k2＋3k＋2＝30，即k2＋3k－28＝0，解得k＝4或k＝－7(舍去)．5、解析：选D.将函数式化成如下形式．f(x)＝((((x＋0)x＋2)x＋3)x＋1)x＋1，由内向外依次计算：v0＝1，v1＝1×3＋0＝3，v2＝3×3＋2＝11，v3＝11×3＋3＝36.6、解析：选C.以4作除数，相应的除法算式为∴389＝12011(4)，故选C.7、解析：“满几进一”就是几进制．∵是七进制．∴满七进一，根本不可能出现7或比7大的数字，所以各个数位上的数字只能是0、1、2、3、4、5、6中的一个．答案：0、1、2、3、4、5、68、解析：先将八进制数127(8)化为十进制数：127(8)＝1×82＋2×81＋7×80＝64＋16＋7＝87，再将十进制数87化成二进制数：∴87＝1010111(2)，∴127(8)＝1010111(2)．答案：1010111(2)9、解析：可以考虑将①②③④中的数都转换成十进制，那么①中111111(2)＝63；②中210(6)＝78；③中1000(4)＝64；④中81(8)＝65.作比较，可知①的数最小，②的数最大．答案：②①10、解：根据秦九韶算法，把多项式改写成如下形式：f(x)＝x3－2x2－5x＋6＝(x2－2x－5)x＋6＝((x－2)x－5)x＋6.我们把x＝10代入函数式，得f(10)＝((10－2)×10－5)×10＋6＝756.11、解：110(5)＝1×52＋1×51＋0×50＝30，30＝1×24＋1×23＋1×22＋1×2＋0×20＝11110(2)，即110(5)＝11110(2)．12、解：∵f(x)＝8x7＋5x6＋3x4＋2x＋1＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1，且x＝2，∴v0＝8，v1＝8×2＋5＝21，v2＝21×2＋0＝42，v3＝42×2＋3＝87，v4＝87×2＋0＝174，v5＝174×2＋0＝348，v6＝348×2＋2＝698，v7＝698×2＋1＝1397.∴当x＝2时，f(x)＝1397.同理可求当x＝－1时，f(x)＝－1，又∵f(－1)f(2)＝－13970，则多项式f(x)在区间[－1,2]上有零点．