計(jì)算機(jī)算法基礎(chǔ)課后答案-資料下載頁
2025-06-23 17:33本頁面
【正文】 次計(jì)算得到T(0,1)=1，T(2,4)=3，T(3,4)=4總體成本是4+2*（2+1）+2*（4+2+4）+3*（1+1+1）=39②Procedure CreateTree(m, n, root, w)integer r, k, root(n, n), w(n, n)real ww, min←∞if m=n then root(m, n)←0else if m=n1 then root(m,n)←nelsefor k←m+1 to n doww←|w(m, k1)w(k, n)|if ww min then min←ww, r←kendifrepeatroot(m, n)←rCall CreateTree(m, r1)Call CreateTree(r, n)endifEnd BuildTree時(shí)間復(fù)雜性最好和平均的情況應(yīng)該是O(nlogn)，但最壞的情況是O(n2)P1516設(shè)(w1,w2,w3,w4)=(10,15,6,9), (p1,p2,p3,p4)=(2,5,8,1)。生成每個(gè)fi階躍點(diǎn)的序偶集合Si，0≤i≤4。P1518??給出一個(gè)使得DKNAP()出現(xiàn)最壞情況的例子，它使得| Si|=2i, 0≤in。還要求對(duì)n的任意取值都適用。取(P1,P2,…,Pi,…)=(W1,W2,…,Wi,…)=(20,21,…,2i1,…)P和W取值相同，使支配原則成立，也就是說不會(huì)因?yàn)橹湓瓌t而刪除元素；只要說明不會(huì)出現(xiàn)相同元素被刪除一個(gè)的情形，即可知是最壞的情況?？捎脷w納法證明此結(jié)論。P15213??假定兩個(gè)倉庫W1和W2都存有同一種貨物，其庫存量分別為r1和r2。想要將其全部發(fā)往n個(gè)目的地D1,D2,…,Dn. 設(shè)發(fā)往Dj的貨物為dj，因此r1+r2=，那么倉庫問題就是求各個(gè)倉庫應(yīng)給每個(gè)目的地發(fā)多少貨才使總的花費(fèi)最小。即要求出這些非負(fù)整數(shù)xij，1≤i≤2,1≤j≤n，它使得x1j+x2j=dj, 1≤j≤n，并且使Σijcij(xij)取最小值。假設(shè)當(dāng)W1有x的庫存且按最優(yōu)方式全部發(fā)往目的地D1,D2,…,Di時(shí)所需的花費(fèi)為gi(x)(W2的庫存為Σdjx)。于是此倉庫問題的最優(yōu)總花費(fèi)是gn(r1).P12813①求gi(x)的遞推關(guān)系式②寫一個(gè)算法求解這個(gè)遞推關(guān)系式并要能得到xij的決策值得最優(yōu)序列，1≤i≤2,1≤j≤n.1112110min{,}(){()()()} miniiiiiiiiixxdiigxcxcdxgxdxd?≤=+?+?1121()()() iiiiiiigxcxcdxxd=+?≤P15217??最優(yōu)性原理并不總是對(duì)可以將其解看成是一系列決策結(jié)果的所有問題成立。找兩個(gè)最優(yōu)性原理不成立的例子，并說明對(duì)這兩個(gè)問題最優(yōu)性原理為什么不成立。??多段圖問題：路徑和改為路徑乘積并允許出現(xiàn)負(fù)數(shù)計(jì)算機(jī)算法分析—習(xí)題課第八章：9P2151，使它們只求出問題的一個(gè)解而不是問題的全部解procedure BACKTRACK(n)integerk,n。 localX(1: n)k ←1whilek0 doif還剩有沒檢驗(yàn)過的X(k)使得X(k) ∈T ( X(1), …,X(k1)) and Bk ( X(1), …,X(k)) =truethen if ( X(1), …,X(k) ) 是一條抵達(dá)一答案節(jié)點(diǎn)的路徑then print ( X(1), …,X(k))returnendifk ←k ＋1elsek ←k －1endifrepeatend BACKTRACKprocedure RBACKTRACK(k)global n, X(1:n)for滿足下式的每個(gè)X(k)X(k) ∈T ( X(1), …,X(k1)) and Bk( X(1), …,X(k))=truedoif( X(1), …,X(k))是一條抵達(dá)一答案結(jié)點(diǎn)的路徑then print( X(1), …,X(k))returnendifcall RBACKTRACK(k+1)repeatend RBACKTRACKP2153重新定義過程PLACE(k)，使它的返回值或者是第k個(gè)皇后可以放置于其上的合法列號(hào)，或者是一個(gè)非法值，這樣可以提高一些NQUEENS的效率，按以上策略重寫這兩個(gè)過程。procedure PLACE(k)global X(1:K) 。 integer i, kj ←1while X(k)≤n doi ←1while ik doif X(i) = X(k) or ABS( X(i)－X(k)) = ABS(i－k)then exitendifi ←i + 1repeatif i=k then j←X(k) exit endifX(k) ←X(k)+1repeatreturn( j )end PLACEprocedure NQUEENS(k)integer k，n，X(1:n)X(1) ←0。 k←1while k0 doX(k) ←X(k)+1if PLACE(k) ≠1 //找到一個(gè)位置then if k＝nthen print（X）else k ←k＋1；X(k) ←0endifelse k ←k－1endifrepeatend NQUEENSP2158??設(shè)W=(5,7,10,12,15,18,20) 和M=35，使用過程SUMOFSUB找出W中使得和數(shù)等于M的全部子集并畫出所生成的部分狀態(tài)空間樹。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1