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

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