算法分析期末考試集答案

1、算法分析與設(shè)計(jì)?一、 解答題1. 機(jī)器調(diào)度問(wèn)題。問(wèn)題描述：現(xiàn)在有 n 件任務(wù)和無(wú)限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得到 處理。每件任務(wù)的開(kāi)始時(shí)間為Si，完成時(shí)間為f i, SiVfi。s i, fi為處理任 務(wù) i 的時(shí)間范圍。兩個(gè)任務(wù) i ， j 重疊指兩個(gè)任務(wù)的時(shí)間范圍區(qū)間有重疊， 而并非指 i, j 的起點(diǎn)或終點(diǎn)重合。例如：區(qū)間 1, 4與區(qū)間2, 4重疊, 而與4, 7不重疊。一個(gè)可行的任務(wù)分配是指在分配中沒(méi)有兩件重疊的任務(wù) 分配給同一臺(tái)機(jī)器。因此,在可行的分配中每臺(tái)機(jī)器在任何時(shí)刻最多只處理 一個(gè)任務(wù)。最優(yōu)分配是指使用的機(jī)器最少的可行分配方案。問(wèn)題實(shí)例：假設(shè)任務(wù)占用的時(shí)間范圍是 1 , 4

2、, 2, 5, 4, 5, 2, 6, 4, 7 ,那么按時(shí)完成所有任務(wù)最少需要幾臺(tái)機(jī)器？(提示：使用貪心 算法)畫出工作在對(duì)應(yīng)的機(jī)器上的分配情況。2. 非齊次遞歸方程：f(n) bf(n 1) g(n)，其中，b、c是常數(shù)，g(n)f (0) cn是 n 的某一個(gè)函數(shù)。那么 f(n) 的非遞歸表達(dá)式為： f(n) cbnbn ig(i) 。i1現(xiàn)有Hanoi塔問(wèn)題的遞歸方程為：h(n) 2h(n 1) 1，求h(n)的非遞歸表 h(1) 1達(dá)式。解：禾U用給出的關(guān)系式，此時(shí)有：b=2, c=1, g(n)=1,從n遞推到1，有：n1 h(n) cbn 1bn1 ig(i)i1n 1 n 22

3、2n 1 2n 2 . 22 2 1n2n 13. 單源最短路徑的求解。問(wèn)題的描述：給定帶權(quán)有向圖(如以下圖所示)G =(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它 各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單 源最短路徑問(wèn)題解法：現(xiàn)采用Dijkstra 算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請(qǐng)將 此過(guò)程填入下表中。迭代Sudist2dist3dist4dist5初始1-10maxi nt3010012344. 請(qǐng)寫出用回溯法解裝載問(wèn)題的函數(shù)。裝載問(wèn)題：有一批共n個(gè)集裝箱要裝上2艘載重量分別為cl和c2的輪船，n

4、Wi C1 C2其中集裝箱i的重量為wi，且i 1。裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這n個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。解: void backtrack (int i)用分支限界法解裝載問(wèn)題時(shí)，對(duì)算法進(jìn)行了一些改良，下面的程序段給出了 改良局部；試說(shuō)明斜線局部完成什么功能，以及這樣做的原因，即采用這樣的方 式，算法在執(zhí)行上有什么不同。/檢查左兒子結(jié)點(diǎn)Type wt = Ew + wi; /左兒子結(jié)點(diǎn)的重量if (wt bestw) bestw = wt;/參加活結(jié)點(diǎn)隊(duì)列if (i bestw & i 0故Ew+rbestw總是成立。也就 是說(shuō)，此時(shí)右子樹(shù)測(cè)試不起

5、作用。為了使上述右子樹(shù)測(cè)試盡早生效，應(yīng)提早更新bestw。又知算法最終找到的最優(yōu)值是所求問(wèn)題的子集樹(shù)中所有可行結(jié)點(diǎn)相應(yīng)重量的最大值。而結(jié)點(diǎn)所相應(yīng)得重量?jī)H在搜索進(jìn)入左子樹(shù)是增加，因此，可以在算法每一次進(jìn)入左子樹(shù)時(shí)更新 bestw的值。7.最長(zhǎng)公共子序列問(wèn)題：給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn ， 找出X和丫的最長(zhǎng)公共子序列。由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用cij記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi=x1,x2,xi ; Yj=y1,y2,yj。當(dāng) i=0 或 j=0 時(shí)，空序列是 Xi 和 Yj 的最長(zhǎng)公共子序列。故此時(shí)Cij

6、=0 。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立0i 0,j 0遞歸關(guān)系如下：ci jci 1j 1 1i, j 0;xi ymaxcij 1,ci1j i,j 0必 在程序中，bij 記錄Cij的值是由哪一個(gè)子問(wèn)題的解得到的。(1)請(qǐng)?zhí)顚懗绦蛑械目崭?，以使函?shù)LCSLe ngth完成計(jì)算最優(yōu)值的功能。void LCSLength(int m , int n , char *x , char *y , int *c, int *b)int i , j；for (i = 1; i = m; i+) ci0 = 0;for (i = 1; i = n; i+) c0i = 0;for (i = 1; i

7、 = m; i+)for (j = 1; j =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3;(2)函數(shù)LCS實(shí)現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長(zhǎng)公共子序列。請(qǐng)?zhí)?寫程序中的空格，以使函數(shù)LCS完成構(gòu)造最長(zhǎng)公共子序列的功能(請(qǐng) 將bij的取值與(1)中您填寫的取值對(duì)應(yīng)，否那么視為錯(cuò)誤)。void LCSint i，int j ，char *x，int *b)if (i =0 | j=0) retur n;if (bij= 1) LCS( i-1，j-1，x, b); cout0 ) printf(%dn ,k);f(k-1);f(k-1);、復(fù)雜

8、性分析1、MERGESORT(lo，w high) if lowhigh ；then midJ (low , high)/2 ;MERGESORT(low ， mid) ；MERGESORT(mid+1 ， high) ；MERGE(low ， mid， high) ； endifend MERGESORT 答: 1 、 遞歸方程T(n)設(shè) n=2k 解遞歸方程：2T(n/2) cn n 1T(n) 2(2T(n/4) cn/2)4T(n/4) 2cncn2k T(1) kcn an cnlogn2、procedure S1(P ， W， M， X， n)i J 1; a J 0while i

9、 M then return endifaJ a+iiJ i+1 ;repeatend解： i J 1 ;s J 0 時(shí)間為： O(1) while i v repeatloop p j p-1 until A(p)w v repeatif ipthen call INTERCHANGE(A(i),A(p)else exitendifrepeatA(m)jA(p);A(p)jvEnd PARTITION 解：最多的查找次數(shù)是 p-m+1 次F1(n)if n1 時(shí) F1(n) 的時(shí)間復(fù)雜度與 F2(2,n,1,1) 的時(shí)間復(fù)雜度相同即為為MAX(A,n,j)xmax jA(1);j j1jA(

10、i); j ji;endif時(shí)間為： O(1)循環(huán)最多 n-1 次for ij 2 to n doif A(i)xmax then xmax repeat end MAX解：xmaxJ A(1);j j 1 for ij 2 to n do所以 總時(shí)間為 :T(n)=O(1)+ (n-1)O(1)= O(n)BINSRCH(A,n,x,j)integer low,high,mid,j,n;low j1;high jnwhile loww high domidj|_(low+high)/2 _|case:xA(mid):low J mid+1:else:j j mid; returnendcas

11、e repeat j J 0 end BINSRCH解: log n+1三、算法理解1、寫出多段圖最短路經(jīng)動(dòng)態(tài)規(guī)劃算法求解以下實(shí)例的過(guò)程，并求出最優(yōu)值。C(1,2)=3， C(1,3)=5C(2,6)=8，C(2,7)=4C(5,8)=4， C(6,8)=5 解：Cost(4,8)=0Cost(3,7)= C(7,8)+0=6Cost(3,6)= C(6，C(1,4)=2，C(3,5)=5，C(3,6)=4，C(7,8)=6,C(4,5)=2 ，C(4,6)=1，D5=88)+0=5, D6=8Cost(3,5)= C(5，8)+0=4 D7=8，5)+ Cost(3,5)，7)+ Cost(

12、3,7)Cost(2,4)= minC(4， 6)+ Cost(3,6), C(4=mi n1+ 5, 2+4=6 D4=6Cost(2,3)= minC(3，6)+ Cost(3,6) =mi n4+5=9 D3=5Cost(2,2)= minC(2，6)+ Cost(3,6), C(2=min 8+5, 4+6=10 D2=7Cost(1,1)= mi nC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)=min 3+10, 5+9,2+6= 8D1=41 t82、寫出maxmin算法對(duì)以下實(shí)例中找最大數(shù)和最小數(shù)的過(guò)程。 數(shù)組 A

13、=(48,12,61,3,5,19,32,7)解：寫出maxmin算法對(duì)以下實(shí)例中找最大數(shù)和最小數(shù)的過(guò)程。 數(shù)組A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48 61, 123 1932, 574、61 32355、61 3次被分割的過(guò)程。3、快速排序算法對(duì)以下實(shí)例排序，算法執(zhí)行過(guò)程中，寫出數(shù)組A第A=(65,70,75,80,85,55,50,2)解：第一個(gè)分割元素為65(1) (2) (3) (4)(6)(8) i p65707580855550228652758085555070376525080855575704665250558580

14、7570465570758085655024、 歸并排序算法對(duì)以下實(shí)例排序，寫出算法執(zhí)行過(guò)程。A=(48,12,61,3,5,19,32,7)解: 48,12,61,35,19,32,748,1261,35,1932,712,483,615,197,323, 12, 48, 615,7,19，323,5, 7,12，19，32，48,615、 寫出圖著色問(wèn)題的回溯算法的判斷Xk是否合理的過(guò)程。解：i 0while i P(i+1)/W(i+1) 的順序。CU 25,X 0W1 CU: x1 1; CU CU-W1=13;W2CU: x3 CU/ W3=3/8;實(shí)例的解為：(1 , 1, 3/8

15、 , 0)11、有一個(gè)有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當(dāng)使用二分 查找值為82的結(jié)點(diǎn)時(shí)，經(jīng)過(guò)多少次比擬后查找成功并給出過(guò)程。解：有一個(gè)有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當(dāng)使用二分 查找值為82的結(jié)點(diǎn)時(shí)，經(jīng)過(guò)多少次比擬后查找成功并給出過(guò)程。一共要要執(zhí)行四次才能找到值為82的數(shù)。12、使用prim算法構(gòu)造出如以下圖 G的一棵最小生成樹(shù)。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=

16、5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6 解：使用普里姆算法構(gòu)造出如以下圖G的一棵最小生成樹(shù)。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=613、有如下函數(shù)說(shuō)明int f(int x,i nt y)f=x Mod y +1;后，k的值是多少并寫出詳細(xì)過(guò)程。后，k的值是多少并寫出詳細(xì)過(guò)程。 a=10,b=4,c=5 那么執(zhí)行

17、 k=f(f(a+c,b),f(b,c)解：有如下函數(shù)說(shuō)明int f(int x,i nt y)f=x Mod y +1; a=10,b=4,c=5 那么執(zhí)行 k=f(f(a+c,b),f(b,c) K的值是5 14、McCathy函數(shù)定義如下： 當(dāng) x100 時(shí) m(x)=x-10;當(dāng) x100 時(shí) m(x)=x-10;當(dāng) x100) return(x-IOO);elsey=m(x+11);return (m(y); 15、設(shè)計(jì)一個(gè)算法在一個(gè)向量A中找出最大數(shù)和最小數(shù)的元素。解：設(shè)計(jì)一個(gè)算法在一個(gè)向量A中找出最大數(shù)和最小數(shù)的元素。Void maxmi n(A,n)Vector A;int n

18、;int max,mi n,i;max=A1;mi n=A1;for(i=2;imax)max=Ai; else if(Ai t2 tn排序2) S1:m清零j - 0設(shè)有n種面值為：d1 d2 dn的錢幣，需要找零錢M,如何選擇錢幣dk，的數(shù)目兀，滿足d1X X +dnX % M，使得X +最小請(qǐng)選擇貪心策略，并設(shè)計(jì)貪心算法。 解：貪心原那么：每次選擇最大面值硬幣。CU- M;i - 1;X- 0有 n 個(gè)物品，n=7,利潤(rùn)為 P=(10,5,15,7,6,18,3) ，重量W=(2,3,5,7,1,4,1)，背包容積 M=15,物品只能選擇全部裝入背包或不裝入背包，設(shè)計(jì)貪心 算法，并討論是

19、否可獲最優(yōu)解。解：定義結(jié)構(gòu)體數(shù)組 G,將物品編號(hào)、利潤(rùn)、重量作為一個(gè)結(jié)構(gòu)體：例如 Gk=1,10,2 求最優(yōu)解，按利潤(rùn)/重量的遞減序，有5,6,1,6 1,10,2,56,18,4,9/2 3,15,5,3 7,3,1,32,5,3,5/3 4,7,7,1算法procedure KNAPSACK(P , W M X n)設(shè)計(jì)只求一個(gè)哈密頓環(huán)的回溯算法。解： Hamiltonian(n)k 1; xk 0;While k0 doxk xk+1;while B(k)=false and xk n doxk xk+1; repeatIf xk n thenif k=n then print x; r

20、eturnelse k k+1; xk 0; endifelse k k-1endifrepeatendprocedure B(k) Gxk-1,xk 豐 1 then return false;for i 1 to k-1 doif xi=xk then return false;endifrepeatreturn true;5利用對(duì)稱性設(shè)計(jì)算法，求n 為偶數(shù)的皇后問(wèn)題所有解。解：利用對(duì)稱性設(shè)計(jì)算法，求 n 為偶數(shù)的皇后問(wèn)題所有解。procedure NQUEENS1(n)0log n 5;(100n2)a2f(n) (g(n) f (n) (g(n) f(n) log n2;g(n) f(

21、n) 2n;g(n) 100n2; f(n) 2n;g(n) 3n; logn2(log n 5) 2n2n(3n) R r1,r2,.,rn) n r1,r2,.,rn R(4 分)coutendl;else for(int i=k;i=m;i+)if(ok(list,k,i)swap(listk,listi);Perm(list,k+1,m);swap(listk,listi); .( 8 分);其中 ok 用于判別重復(fù)元素。Templateint ok(Type list,int k,int i)if(ik)for(int t=k;tI;t+)if(listt= =listi) retu

22、rn 0;return 1; .( 13 分)3、試用分治法對(duì)一個(gè)有序表實(shí)現(xiàn)二分搜索算法。 (12 分)解：解答如下：Templateint BinarySearch(Type a,const Type& x,int n) (4 分)if(x= =amiddle) return middle+1;if(xamiddle) left=middle+1; . ( 8 分)else right=middle-1;return -1; .( 12 分)4、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn) 0-1 閉包問(wèn)題。(15 分)解：解答如下：Templatevoid Knapsack(Type v,int w,int c,

23、int n,Type *m)Int jMax=min(wn-1,c);for(int j=0;j=jMax;j+) mnj=0;for(int j=wn;j1;i-)jMax=min(wi-1,c);for(int j=0;j=jMax;j+) mij=mi+1j;for(intj=wi;j=w1) m1c=max(m1c,m2c-w1+v1); ( 10 分)TemplateVoid Traceback(Type *m,int w,int c,int n,int x)for(int i=1;in;i+)ifmic= =mi+1c xi=0; 12 分else xi=1,c-=wi;xn=mn

24、c?1:0; .15 分5、試用貪心算法求解以下問(wèn)題：將正整數(shù) n 分解為假設(shè)干個(gè)互不相同的自然數(shù)之 和，使這些自然數(shù)的乘積最大。 15 分解：解答如下：void dicomp(int n,int a)k=1;if(n3) a1=0;return;if(nak)k+;ak=ak-1+1;n-=ak; .( 10 分)if(n= =ak) ak+;n-;for(int i=0;in;i+) ak-i+; .( 15 分)6試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)最大子矩陣和問(wèn)題：求m n矩陣A的一個(gè)子矩陣，使其各元素之各為最大。 (15 分)解：解答如下：int MaxSum2(int m,int n,int *a

25、)int sum=0;int *b=new intn+1;for(int i=1;i=m;i+)for(int k=1;k=n;k+) bk=O; . ( 5分)for(int j=i;j=m;j+)for(int k=1;ksum) sum=max;return sum; .( 10 分)int MaxSum(int n,int *a)int sum=0,b=0;for(int i=1;i0) b+=ai;else b=ai;if(bsum) sum=b;Return sum; . ( 15 分)7、試用回溯法解決以下整數(shù)變換問(wèn)題：關(guān)于整數(shù)i 的變換 f 和 g 定義如下：f(i) 3i;g

26、(i)i/2。對(duì)于給定的兩個(gè)整數(shù)n和m,要求用最少的變換f和g變換次數(shù)將 n 變?yōu)?m 。(18 分)解：解答如下：void compute。k=1;while(!search(1,n)k+;if(kmaxdep) break;init();； .( 6 分)if(found) output();else coutNo Solution! k) return false；12分)for(int i=0；i2；i+)int n1=f(n,i)；tdep=i；if(n1= =m|search(dep+1,n1)Found=true；Out()；return true；return false; .

27、( 18 分)一、排序和查找是經(jīng)常遇到的問(wèn)題。按照要求完成以下各題：(20 分)(1) 對(duì)數(shù)組 A=15, 29, 135, 18, 32, 1 , 27, 25, 5，用快速排序方法將其排成遞減序。2) 請(qǐng)描述遞減數(shù)組進(jìn)行二分搜索的根本思想，并給出非遞歸算法。3) 給出上述算法的遞歸算法。4) 使用上述算法對(duì)( 1)所得到的結(jié)果搜索如下元素，并給出搜索過(guò)程：18，31，答案：( 1 )第一步： 15 29 135 18 32 1 27 25 5第二步： 29 135 18 32 272515 1 5【 1分】第三步： 135 32 29 18 272515 5 1【 1分】第四步： 135

28、32 29 27 251815 5 1【 1分】(2) 根本思想：首先將待搜索元素v與數(shù)組的中間元素A n進(jìn)行比擬，如果v A -,2 2那么在前半局部元素中搜索v ;假設(shè)v A n，那么搜索成功；否那么在后半局部數(shù)組中搜索v?！?2分】非遞歸算法：輸入：遞減數(shù)組 Aleft:right，待搜索元素V?！?分】輸出：v在A中的位置pos，或者不在A中的消息(-1 )?！?分】步驟：【3分】int Bin arySearch(i nt A,i nt left,i nt right, int v)int mid;while (leftAmid) right=mid-1;else left=mid+

29、1;return -1;(3) 遞歸算法：輸入：遞減數(shù)組 Aleft:right，待搜索元素V?！?分】輸出：v在A中的位置pos，或者不在A中的消息(-1 )?！?分】步驟：【3分】int Bin arySearch(i nt A,i nt left,i nt right, int v)int mid;if (leftAmid) retur n Bin arySearch(A,left,mid-1,v);else return Bin arySearch(A,mid+1,right,v);elsereturn -1;(4) 搜索18：首先與27比擬，1827,在前半局部搜索；再次 32比擬，

30、3129，此時(shí)只有一個(gè)元素，未找到，返回-1?！?分】搜索135:首先與27比擬，13527,在前半局部搜索；再次 32比擬，13532，在前 半局部搜索；與135比擬，相同，返回 0?！?分】二、對(duì)于以下圖使用 Dijkstra 算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑。20分。答案：用Vi表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與Vi中某個(gè)頂點(diǎn)相鄰接且不在 V中的頂點(diǎn)；E表示參加到最短路徑中的邊，E2為與Vi中的頂點(diǎn)相鄰接且距離最短的路徑?！?分】步驟V 1V2 E1E21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,fea

31、b,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 【以上每步2分】結(jié)果:從a到h的最短路徑為a b d f e gh ,權(quán)值為18?！?分】三假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。假設(shè)這些物品均不能被分割，且背包容量 W 150，使用回溯方法求解此背包問(wèn)題。請(qǐng)寫出狀態(tài)空間搜索樹(shù)20分。物品ABC重量353060價(jià)值104030DEFG5040102550354030答案：求所有頂點(diǎn)對(duì)之間的最短路徑可以使用Di

32、jkstra 算法，使其起始節(jié)點(diǎn)從a循環(huán)到h，每次求起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對(duì)之間的最短路徑?！?分】三、按照單位效益從大到小依次排列這 7個(gè)物品為：FBGDECA將它們的序號(hào)分別記為 17。 那么可生產(chǎn)如下的狀態(tài)空間搜索樹(shù)。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過(guò)如下方式求得：【排序1分】X7X21X2X41aX4xiQidgX3X,0【狀態(tài)空間搜索樹(shù)及其計(jì)算過(guò)程17分，每個(gè)節(jié)點(diǎn)1分】a.404030503540190.625(1,1,1,1-,0,0)8150 11574040305030177.5 (1,1,1,1,0,0)60124040305010170(1,1,1,

33、1,0,0,1)150 10534040303530167.5(1,1,1,0,1,_,0)604150 13014040503530175(1,1,0,1,10)60315013040405035 1035170.71(1,1,0,1,1,0石)150115b.c.d.e.f.(1,1,0,1,0,1,0)g.4040 50 30160h.4040 35 30 10 150 140146.8535(1,1,0,0,1,1,|)i.150 125u40 30 50 35 30 167.5(何乙詩(shī),。)60j.15014540 30 50 35 30157.5(0,1,111丄,0)1260在Q

34、處獲得該問(wèn)題的最優(yōu)解為1,1,1,1,0,0,1,背包效益為170。即在背包中裝入物品G D、A時(shí)到達(dá)最大效益，為170,重量為150?！窘Y(jié)論2分】 Ak(aij(k)n*r11，k=1， 2， 3， 4， 5， 6，1=5，2=10，3=3，r4=12， r5=5, r6=50，7=6，求矩陣鏈積 AX A.X AX AX A5X A的最正確求積順序。要求：給出計(jì)算步驟20分 答案：使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：【每個(gè)矩陣18分】123456101503304051655202120360330243019503018093017704030001860501500601234561

35、012420222230p4440445060因此，最正確乘積序歹y 為(AA2)(氏A (AA6),共執(zhí)行乘法2021次。【結(jié)論2分】七、算法設(shè)計(jì)題(此題10分)通過(guò)鍵盤輸入一個(gè)高精度的正整數(shù)n(n的有效位數(shù)w 240)，去掉其中任意s個(gè)數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。【樣例輸入】178543S=4【樣例輸出】13六、算法設(shè)計(jì)題(此題15分)(1) 貪心算法 O (nlog (n)首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。假設(shè)將這種物品全部裝入

36、背包后，背包內(nèi)的物品 總重量未超過(guò) C,那么選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策 略一直地進(jìn)行下去，直到背包裝滿為止。具體算法可描述如下：void Knapsack(int n,float M,float v,float w,float x)Sort( n,v,w);int i;for (i=1;i=n ;i+) xi=0;float c=M;for (i=1;ic) break;xi=1; c-=wi;if (i=n) xi=c/wi;(2) 動(dòng)態(tài)規(guī)劃法 0( nc)m(i , j)是背包容量為j，可選擇物品為i , i+1 ,，n時(shí)0-1背包問(wèn)題的最優(yōu)值。由 0-1背包問(wèn)

37、題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i , j)的遞歸式如下。m()maxm(i 1，j)，m(i 1，j w Vij Wim(i 1,j)0 j Wim(n, j)VnWnWnvoid KnapSack(int v,int w,int c,int n,int m11) int jMax=mi n(w n-1,c);for (j=O;j=jMax;j+) /*m(n,j)=0 0=jwn*/ m nj=O;for (j=w n ;j=w n*/ m nj=v n ;for (i=n-1;i1;i-) int jMax=mi n(wi-1,c);for (j=0;j=jMax;j+) /*m(i,j)=m(i+1,j) 0=jwi*/ mij=mi+1j;for (j=wi;j=w n*/ mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c=w1) m1c=max(m1c,m2c-w1+v1