【正文】 inmax。 digui_search(min, max, r, 0, 5)。 coutendl。}4. 求兩個(gè)正整數(shù)m和n的最小公倍數(shù)。（提示：m和n的最小公倍數(shù)lcm(m, n)與m和n的最大公約數(shù)gcd(m, n)之間有如下關(guān)系：lcm(m, n)=mn/gcd(m, n)）//求兩個(gè)數(shù)的最小公倍數(shù)includeiostreamusing namespace std。int main (void){ int a,b。 int i=1。 cinab。 while((i%a!=0)||(i%b!=0)) ++i。 couta,b最小公倍數(shù)為：iendl。return 0。}(該算法比較直接，要使其改進(jìn)，可用歐幾里得算法求得兩個(gè)數(shù)的最大公約數(shù)，然后套用上面的公式再求最小公倍數(shù))5. 插入法調(diào)整堆。已知（k1, k2, …, kn）是堆，設(shè)計(jì)算法將（k1, k2, …, kn, kn+1）調(diào)整為堆（假設(shè)調(diào)整為大根堆）。參照： void SiftHeap(int r[ ], int k, int n){int i, j, temp。i = k。 j = 2 * i + 1。 //置i為要篩的結(jié)點(diǎn)，j為i的左孩子while (j n) //篩選還沒有進(jìn)行到葉子{if (j n1 amp。amp。 r[j] r[j+1]) j++。 //比較i的左右孩子，j為較大者 if (r[i] r[j]) //根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者 break。 else { temp = r[i]。 r[i] = r[j]。 r[j] = temp。 //將被篩結(jié)點(diǎn)與結(jié)點(diǎn)j交換 i = j。 j = 2 * i + 1。 //被篩結(jié)點(diǎn)位于原來(lái)結(jié)點(diǎn)j的位置 }}}進(jìn)行調(diào)堆！6. 設(shè)計(jì)算法實(shí)現(xiàn)在大根堆中刪除一個(gè)元素，要求算法的時(shí)間復(fù)雜性為O(log2n)。//將要?jiǎng)h除的a[k]與最后一個(gè)元素a[n1]交換//然后進(jìn)行調(diào)堆void de_SiftHeap(int r[ ], int k, int n){int i, j, temp,temp1。i = k。 j = 2 * i + 1。 if(i0||in1)return error。else if(i==n1)free(a[i])。else //置i為要篩的結(jié)點(diǎn)，j為i的左孩子while (j n) //篩選還沒有進(jìn)行到葉子{temp1=a[i]。 //將a[n1]與a[k]交換；a[i]=a[n1]。a[n1]= temp1。if (j n1 amp。amp。 r[j] r[j+1]) j++。 //比較i的左右孩子，j為較大者 if (r[i] r[j]) //根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者 break。 else { temp = r[i]。 r[i] = r[j]。 r[j] = temp。 //將被篩結(jié)點(diǎn)與結(jié)點(diǎn)j交換 i = j。 j = 2 * i + 1。 //被篩結(jié)點(diǎn)位于原來(lái)結(jié)點(diǎn)j的位置 }}}n m50 6525 130 13012 260 6 5203 1040 10401 2080 2080 3250 俄式乘法+7. 計(jì)算兩個(gè)正整數(shù)n和m的乘積有一個(gè)很有名的算法稱為俄式乘法，其思想是利用了一個(gè)規(guī)模是n的解和一個(gè)規(guī)模是n/2的解之間的關(guān)系：nm＝n/22m（當(dāng)n是偶數(shù)）或：nm＝(n1)/22m＋m（當(dāng)n是奇數(shù)），并以1m＝m作為算法結(jié)束的條件。例如，65的例子。據(jù)說(shuō)十九世紀(jì)的俄國(guó)農(nóng)夫使用該算法并因此得名，這個(gè)算法也使得乘法的硬件實(shí)現(xiàn)速度非?？?，因?yàn)橹皇褂靡莆痪涂梢酝瓿啥M(jìn)制數(shù)的折半和加倍。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)俄式乘法。//俄式乘法includeiostreamusing namespace std。int fun(int m,int n){ int sum=0。 int temp=n。 while(m!=1) { if(m%2==0)//如果n是偶數(shù) { n=n*2。 m=m/2。 } else//如果n是奇數(shù) { n=n*2。 sum+=temp。 m=(m1)/2。 } temp=n。//記錄倒數(shù)第二個(gè)n的值 } return sum+n。}int main(){ int a,b。 while(cinab) { coutfun(a,b)endl。 }}8. 拿子游戲?？紤]下面這個(gè)游戲：桌子上有一堆火柴，游戲開始時(shí)共有n根火柴，兩個(gè)玩家輪流拿走1，2，3或4根火柴，拿走最后一根火柴的玩家為獲勝方。請(qǐng)為先走的玩家設(shè)計(jì)一個(gè)制勝的策略（如果該策略存在）。 如果桌上有小于4根的火柴，先手必勝，如果是5根，先手必輸；依次類推，同理125…….都是必輸狀態(tài)；所有每次把對(duì)手逼到125…….等必輸狀態(tài)，就可以獲勝。9. 競(jìng)賽樹是一棵完全二叉樹，它反映了一系列“淘汰賽”的結(jié)果：葉子代表參加比賽的n個(gè)選手，每個(gè)內(nèi)部結(jié)點(diǎn)代表由該結(jié)點(diǎn)的孩子結(jié)點(diǎn)所代表的選手中的勝者，顯然，樹的根結(jié)點(diǎn)就代表了淘汰賽的冠軍。請(qǐng)回答下列問(wèn)題：（1）這一系列的淘汰賽中比賽的總場(chǎng)數(shù)是多少？（2）設(shè)計(jì)一個(gè)高效的算法，它能夠利用比賽中產(chǎn)生的信息確定亞軍。（1）因?yàn)閚人進(jìn)行淘汰賽，要淘汰n1人，所有要進(jìn)行n1場(chǎng)比賽。（2）10. 在120枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣與真幣的重量不同，但不知道假幣與真幣相比較輕還是較重?？梢酝ㄟ^(guò)一架天平來(lái)任意比較兩組硬幣，最壞情況下，能不能只比較5次就檢測(cè)出這枚假幣？將120枚平均分為三組，記為：A，B，C；先將A,B比較，如果A,B重量不同（假如B比A重），再將B與C比較，如果B，C相同，則A有假幣；如果B,C不同，再將A,C比較，如果A,C相同，則B有假幣；如果A,C不同，則B有假幣；如果A,B相同，則C有假幣；習(xí)題61. 動(dòng)態(tài)規(guī)劃法為什么都需要填表？如何設(shè)計(jì)表格的結(jié)構(gòu)？在填寫表格過(guò)程中，不僅可以使問(wèn)題更加清晰，更重要的是可以確定問(wèn)題的存儲(chǔ)結(jié)構(gòu)； 設(shè)計(jì)表格，以自底向上的方式計(jì)算各個(gè)子問(wèn)題的解并填表。2. ，用動(dòng)態(tài)規(guī)劃法求從頂點(diǎn)0到頂點(diǎn)12的最短路徑，寫出求解過(guò)程。883510234101112 第2題圖567891367683533463552643 將該多段圖分為四段；首先求解初始子問(wèn)題，可直接獲得：d(0, 1)=c01＝5(0→1)d(0, 2)=c02＝3(0→1)再求解下一個(gè)階段的子問(wèn)題，有：d(0,3)= d(0, 1)+ c13 =6(1→3)d(0,4)=min{d(0,1)+ c14 ,d(0,2)+ c24}=8(1→4)。（以此類推）最短路徑為：0→1→3→8→11→123．用動(dòng)態(tài)規(guī)劃法求如下0/1背包問(wèn)題的最優(yōu)解：有5個(gè)物品，其重量分別為(3, 2, 1, 4,5)，價(jià)值分別為(25, 20, 15, 40, 50)，背包容量為6。寫出求解過(guò)程。(x1, x2,x3,x4,x5) →(1,1,1,0,0)(過(guò)程略)4. 用動(dòng)態(tài)規(guī)劃法求兩個(gè)字符串A=xzyzzyx和B=zxyyzxz的最長(zhǎng)公共子序列。寫出求解過(guò)程。 略5. 給定模式grammer和文本grameer，寫出動(dòng)態(tài)規(guī)劃法求解K近似匹配的過(guò)程。 略6. 對(duì)于最優(yōu)二叉查找樹的動(dòng)態(tài)規(guī)劃算法，設(shè)計(jì)一個(gè)線性時(shí)間算法，從二維表R中生成最優(yōu)二叉查找樹。7. Ackermann函數(shù)A(m, n)的遞歸定義如下：設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法計(jì)算A(m, n)，要求算法的空間復(fù)雜性為O(m)。//求ackman函數(shù)//使用棧include iostream using namespace std。 long ackman(long m, long n) { long stack[10000]。 int pos=1。 stack[0]=m。stack[1]=n。 while(pos) { n=stack[pos]。 m=stack[pos]。 if(m==0) stack[pos]=n+1。 if(m!=0amp。amp。n==0) { stack[pos++]=m1。 stack[pos]=1。 } if(m!=0amp。amp。n!=0) { stack[pos++]=m1。 stack[pos++]=m。 stack[pos]=n1。 } } return stack[0]。 }int main(int argc, char *argv[]) { long m,n。 cinmn。 coutackman(m,n)。 coutendl。 return 0。 } 8. 考慮下面的貨幣兌付問(wèn)題：在面值為(v1, v2, …, vn)的n種貨幣中，需要支付y值的貨幣，應(yīng)如何支付才能使貨幣支付的張數(shù)最少，即滿足，且使最?。▁i是非負(fù)整數(shù)）。設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法求解貨幣兌付問(wèn)題，并分析時(shí)間性能和空間性能。includeiostreamdefine N 100000define M 20int a[N][M]。int value[M]。using namespace std。int main(){ while(true) { int i,j,k。 int x,y,z。 cout輸入貨幣種類的個(gè)數(shù)：endl。 cinx。 cout從小到大輸入貨幣的價(jià)值，其中第一個(gè)必須為一：endl。 for(i=1。i=x。i++)//x為貨幣種類的個(gè)數(shù) { coutvalue[i]=。 ciny。 value[i]=y。 } cout輸入要兌換的錢的價(jià)值：endl。 cinz。//z為錢 for(j=0。j=z。j++) a[j][0]=0。 for(k=0。k=x。k++) a[0][k]=0。 for(i=1。i=z。i++) { for(j=1。j=x。j++) { if(value[j]==i) a[i][j]=1。 else if(value[j]i) a[i][j]=a[i][j1]。 else a[i][j]=a[ivalue[j]][j]+1。//相當(dāng)于把乘法換成加法，即碰到一個(gè)錢數(shù)于兌換貨幣自身價(jià)值時(shí)，返回到 錢數(shù)減去該貨幣值的地方，其值再加1// }//for } cout兌換的最小貨幣個(gè)數(shù)是：a[z][x]endl。 }//whilereturn 0。 }9. 多邊形游戲。多邊形游戲是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形，每個(gè)頂點(diǎn)具有一個(gè)整數(shù)值，每條邊具有一個(gè)運(yùn)算符“＋”或“”。游戲規(guī)則是每次選擇一條邊e以及和e相關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j，用一個(gè)新的頂點(diǎn)k取代邊e、頂點(diǎn)i和j，頂點(diǎn)k的整數(shù)值是頂點(diǎn)i和j的整數(shù)值通過(guò)邊e上的運(yùn)算符計(jì)算得到的結(jié)果。當(dāng)所有邊都刪除時(shí)，游戲結(jié)束，游戲的得分就是所剩頂點(diǎn)的整數(shù)值。設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法，對(duì)于給定的多邊形計(jì)算最高得分。