算法案例知識點-試題及答案

1、精品文檔3歡迎下載 。一、知識要點及方法輾轉(zhuǎn)相除法是利用以下性質(zhì)來確定兩個正整數(shù)a和b的最大公因子的：1 .若r是a + b的余數(shù)，則gcd(a,b) = gcd(b,r)2 . a和其倍數(shù)之最大公因子為a。另一種寫法是：1 . a + b ,令r為所得余數(shù)(0w rb)若r = 0 ，算法結(jié)束；b即為答案。2 .互換：置a-b, br,并返回第一步秦九韶算法的特典在于，它通過一次式的反復(fù)計算，逐步得出高次多項式的值。具體地說，它將一個n次多項式的求解問題，歸結(jié)為重復(fù)計算n個一次式、九 Xk . a-VkVk 1 an kk=1,2,n(1) 來實現(xiàn)。這種化繁為簡的處理方法在數(shù)值分析中是屢見不

2、鮮的?，F(xiàn)在考慮秦九韶算法的計算程序。按式(1)計算，每求出一個“新值”、九以后，“老值”一便失去繼續(xù)保存的價值，v kv k 1因此可以將新值 Vk存放在老值 Vk 1所占用的單元內(nèi)。這樣，我們只要設(shè)置一個單元V進行累算，而將式(1)表為下列動態(tài)形式x?van kV , k=1,2,n執(zhí)行這組算式之前,應(yīng)先送初值an到單元v中，anv二、試題同步訓(xùn)練1 .用更相減損術(shù)求294和84的最大公約數(shù)時，需做減法的次數(shù)是()A. 2B. 3C. 4D. 52 .若用秦九韶算法求多項式f (x) =4x5X2+2當(dāng)x=3時的值，則需要做乘法運算和加減法運算的次數(shù)分別為()A.4,2B.5,3C.5,2D

3、.6,23 .將二進制數(shù)10001(2)化為五進制數(shù)為()A.32(5)B.23(5)C.21(5)D.12(5)4 378 與 90 的最大公約數(shù)為 課時訓(xùn)練1 45 和 150 的最大公約數(shù)和最小公倍數(shù)分別是()A 5,150B 15,450C 450,15D 15,1502 .用秦九韶算法求多項式f(x) = 7x6+6x5+3x2+2當(dāng)x=4的值時，先算的是()B. 7X 4=28A. 4X4=16C. 4X4X4=64D. 7X 4+6 = 343二進制數(shù)算式1010(2) 10(2) 的值是 ()B 1100(2)D 1000(2)A 1011(2)C 1101(2)4已知一個k

4、進制的數(shù) 132 與十進制的數(shù)30 相等，那么 k 等于 ()A 7 或 4B 7C. 4D.都不對5.已知f(x) = x5+2x3+3x2+x+ 1,應(yīng)用秦九韶算法計算 x=3時的值時，V3的值為(A27B11C109D366由 389 化為的四進制數(shù)的末位為 ()A3B2C1D07七進制數(shù)中各個數(shù)位上的數(shù)字只能是中的一個8將八進制數(shù)127(8)化成二進制數(shù)為 9下列各數(shù) 111111(2) 210(6) 1000(4) 81(8)最大數(shù)為 ，最小數(shù)為 10.已知函數(shù)f(x) =x32x25x+6,試用秦九韶算法求f (10)的值.11把 110(5)轉(zhuǎn)化為二進制數(shù)12.利用秦九韶算法分別

5、計算f(x) = 8x7+5x6+3x4+2x+1在x=2與x= 1時的值,并判斷多項式f ( x) 在區(qū)間 1,2 有沒有零點答案：1、解析：選 C.294 84 = 210,210 84= 126,126 84=42,84 42 = 42,故選 C.2、解析：選 C.f (x) =4x5x2+2=(4 x)x)x1)x)x+2,所以需要做 5次乘法運算 和 2 次加減運算3、解析：選A. 將 10001(2) 化為十進制數(shù)為：10001(2)= 1X 24 + 0 X 23 + 0 X 22 + 0 X 21+ 1 X 2= 17,將 17 化為五進制數(shù)為32(5) ，10001(2) =

6、32(5)4、解析：輾轉(zhuǎn)相除法：378=90X4+ 18,90= 18X 5+0,378與90的最大公約數(shù)是18.答案： 18課時訓(xùn)練1、解析：選B.利用輾轉(zhuǎn)相除法求 45和150的最大公約數(shù)：150=45X 3+15,45 = 15X 3, 所以45和150的最大公約數(shù)為15.所以45和150的最小公倍數(shù)為15 X (45勺5) X (150 +15) = 450,故選 B.2、解析：選 D.因為 f (x) = anxn+anixnT + a1x + a0=(&x+ an)x+an-2) x+ + a1)x+a。，所以用秦九韶算法求多項式 f(x) =7x6+6x5+3x2+2當(dāng)x=4的值

7、時，先算的是 7X4+6=34.3、解析：選 B.101 0(2) + 10(2) =(1 X 23 + 0 X 22+ 1X 21+ 0 X 20) + (1 X 21+ 0 X 20) = 12 = 1100(2) ，故選 B .4、解析：選 C.132(k)=1Xk2+3X k+2=k2+3k+2,.k2+3k+2=30,即 k2+3k 28=0,解得k=4或k= 7(舍去).5、解析：選D.將函數(shù)式化成如下形式.f(x) = ( x+0)x+2)x+3)x+ 1)x+ 1,由內(nèi)向外依次計算：v0= 1,V 1= 1X 3+0=3,V 2= 3X 3+2=11,V 3= 11X3+ 3=

8、36.V 、解析：選C.以4作除數(shù)，相應(yīng)的除法算式為精品文檔4| 389余數(shù)扉SI4| 24I4|fr04120I .389= 12011(4),故選 C.7、解析：“滿幾進一 ”就是幾進制.二是七進制.，滿七進一，根本不可能出現(xiàn)7或比7大的數(shù)字，所以各個數(shù)位上的數(shù)字只能是0、1、2、3、4、5、6中的一個.答案：0、1、2、3、4、5、68、解析：先將八進制數(shù)127(8)化為十進制數(shù)：127(8)= 1 X 82 + 2X 81 + 7X 8= 64 + 16+7=87,再將十進制數(shù)87化成二進制數(shù):2|R7 條數(shù)2|4310 1 87=1010111(2),127(8)= 1010111(

9、2)答案：1010111(2)9、解析：可以考慮將中的數(shù)都轉(zhuǎn)換成十進制，那么中111111(2) = 63;中210(6)=78；中1000(4) = 64;中81(8)= 65.作比較，可知的數(shù)最小，的數(shù)最大.答案：10、解：根據(jù)秦九韶算法，把多項式改寫成如下形式：f (x) =x3- 2x2- 5x + 6=(x2 2x 5) x+6=(x- 2)x5)x+6.我們把x=10代入函數(shù)式，得 f (10) =(10 2) X 10-5) X 10 + 6=756.11、解：110(5) = 1 X 52 + 1 X 51+ 0X 50= 30,30= 1X 24+ 1 X 23+ 1 X 22+ 1 X 2+ 0X 20= 11110(2),即 110(5) = 11110(2)12、解：. f(x) =8x7+5x6+3x4+2x+1 = (8 x+5)x+0) x+3) x+0)x+0) x+2) x + 1,且 x = 2, - V0= 8,Vi=8X2+5=21,V 2= 21 X 2+ 0=42,V 3= 42X2+ 3= 87,v4= 87X2