算法設(shè)計(jì)試題（2019A答）

第1頁(yè)（共3頁(yè)）考試科目：算法設(shè)計(jì)與分析試題（A）參考答案選擇題（每題2分，共10分）1-5CCCBD二、填空題（每空2分，共16分）1、X=7321568，X刪除4位數(shù)字后的最大值為_(kāi)__768_，7/16的埃及分?jǐn)?shù)表達(dá)式為_(kāi)_1/3+1/10+1/240。2、算法描述方式有（至少3個(gè)）_流程圖_、__盒圖__、__偽代碼_。3、設(shè)計(jì)遞歸算法的步驟__找出大規(guī)模問(wèn)題與小規(guī)模問(wèn)題的關(guān)系，找出停止條件，_設(shè)計(jì)函數(shù)、確定參數(shù)_。得分三、簡(jiǎn)答題（每題8分，共24分）1、算法的五個(gè)基本特征。1)有窮性2)確定性3)可行性4)算法有零個(gè)或多個(gè)的輸入5)算法有一個(gè)或多個(gè)的輸出2、簡(jiǎn)述什么是算法的時(shí)間復(fù)雜度及“O”的含義。一個(gè)特定算法的“運(yùn)行工作量”的大小,依賴(lài)于問(wèn)題的規(guī)模(通常用整數(shù)量n表示),或者說(shuō),算法的時(shí)間效率是問(wèn)題規(guī)模的函數(shù)。假如,隨著問(wèn)題規(guī)模n的增長(zhǎng),算法執(zhí)行時(shí)間的增長(zhǎng)率和函數(shù)f(n)的增長(zhǎng)率相同,則可記作:T(n)=O(f(n))稱(chēng)T(n)為算法的漸近時(shí)間復(fù)雜度(asymptotictimecomplexity),簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。O是數(shù)量級(jí)的符號(hào),標(biāo)準(zhǔn)數(shù)量級(jí)通常有Ο(1)稱(chēng)為常數(shù)級(jí)；Ο(logn)稱(chēng)為對(duì)數(shù)級(jí)；Ο(n)稱(chēng)為線性級(jí)；Ο(nc)稱(chēng)為多項(xiàng)式級(jí)；Ο(cn)稱(chēng)為指數(shù)級(jí)；Ο(n！)稱(chēng)為階乘級(jí)。3、比較用循環(huán)和遞歸實(shí)現(xiàn)求n!算法的優(yōu)劣。用遞歸計(jì)算n!比循環(huán)更加消耗資源,前者空間上時(shí)間上都有消耗，每次調(diào)用過(guò)程都使得調(diào)用鏈條不斷加長(zhǎng)，系統(tǒng)不得不使用棧進(jìn)行數(shù)據(jù)保存和恢復(fù)。而循環(huán)就不需要這樣的消耗。四、綜合題（共20分）：1.（10分）現(xiàn)有四個(gè)矩陣，其中各矩陣維數(shù)分別為：A1A2A3A440′3030′2020′1010′5p0′p1p1′p2p2′p3p3′p4計(jì)算出矩陣連乘積A2A3A4所需要的最少乘法次數(shù)及組合方案。1）所有連續(xù)2個(gè)矩陣乘法次數(shù)T（A1A2）=40*30*20=24000T（A2A3）=30*20*10=6000T（A3A4）=20*10*5=10002）所有連續(xù)3個(gè)矩陣最少乘法次數(shù)T（A1A2A3）=min{A1（A2A3）,（A1A2）A3}=min{24000+40*20*10,6000+40*30*10}=18000T（A2A3A4）=min{A2（A3A4）,（A2A3）A4}=min{1000+30*20*5,6000+30*10*5}=40003）T（A1A2A3A4）=min{A1（A2A3A4）,（A1A2）(A3A4）,（A1A2A3）A4}=min{4000+40*30*5,24000+1000+40*20*5.18000+40*10*5}=10000組合方案A1（A2（A3A4））2（10分）資源分配問(wèn)題：現(xiàn)有n=7萬(wàn)元投資到A，B，C，D四個(gè)項(xiàng)目，利潤(rùn)見(jiàn)下表1234567A0.130.160.180.200.250.290.35B0.110.140.200.230.250.280.32C0.100.130.200.230.260.320.33D0.120.150.180.210.230.260.30求總利潤(rùn)最大的資源分配方案。1）只考慮A項(xiàng)目各種投資利潤(rùn)表A01234567利潤(rùn)00.130.160.180.200.250.290.352）考慮A，B兩項(xiàng)目各種投資利潤(rùn)表BA+B012345670010.13*0.1120.160.24*0.1430.180.27*0.27*0.2040.200.290.300.33*0.2350.250.310.320.36*0.36*0.2560.290.360.340.380.39*0.380.2870.350.400.390.400.41*0.41*0.41*0.323）考慮A，B,C三個(gè)項(xiàng)目各種投資利潤(rùn)表CA+B+C012345670010.13*0.1020.24*0.230.1330.270.34*0.260.2040.330.37*0.37*0.330.2350.360.430.400.44*0.360.2660.390.460.460.47*0.47*0.390.3270.410.490.490.53*0.500.500.450.334）四個(gè)項(xiàng)目總投資7萬(wàn)，第四個(gè)項(xiàng)目各種投資利潤(rùn)表D01234567D利潤(rùn)00.120.150.180.210.230.260.30A+B+C利潤(rùn)0.530.470.440.370.340.240.130總利潤(rùn)0．530.590.590.550.550.470.390.30最大利潤(rùn)為0.59，投資方案如下：1）A1萬(wàn)B1萬(wàn)C3萬(wàn)D2萬(wàn)2）A2萬(wàn)B1萬(wàn)C3萬(wàn)D1萬(wàn)3）A1萬(wàn)B2萬(wàn)C3萬(wàn)D1萬(wàn)4）A1萬(wàn)B1萬(wàn)C4萬(wàn)D1萬(wàn)五、算法設(shè)計(jì)題（每題15分，共30分）1、一個(gè)數(shù)如果恰好等于它的因子之和(包括1,但不包括這個(gè)數(shù)本身),這個(gè)數(shù)就稱(chēng)為“完數(shù)”，設(shè)計(jì)算法求所有四位數(shù)中的“完數(shù)”。main(){inti,k,j,s,a［20］;for(i=1000;i<10000;i=i+1){s=1;k=0;for(j=2;ji;j=j+1)if(imodj)=0){s=s+j;a［k］=j;k=k+1;}if(i==s){print(s,"it'sfactorsare:",1);for(j=0;jk;j=j+1)print(",",a［j］);}}}2、設(shè)計(jì)算法輸出(a+b)n二項(xiàng)式系數(shù)。coeff(inta［］,intn){if(n==1){a［1］=1;a［2］=1;}else{coeff(a,n-1)a［n+1］=1for