算法設(shè)計(jì)復(fù)習(xí)題2010

1、1給出遞推公式x(n)=x(n-1)+n,x(0)=0對(duì)應(yīng)的通項(xiàng)公式計(jì)算過程？解： X(n)-X(n-1)=n X(n-1)-X(n-2)=n-1 X(1)-X(0)=1 X(n)-X(0)=(n+1)n2 X(n)= (n+1)n22O、Q、W之間的區(qū)別與聯(lián)系是什么？ 答：O描述增長率的上限 上限值越低，結(jié)果越有價(jià)值。Q用來表示算法的精確階W描述增長率的下限 下限值越高越有價(jià)值。聯(lián)系： 只要當(dāng)考察問題規(guī)模充分大時(shí)，算法中基本語句的執(zhí)行次數(shù)在漸近意義下的階，通常使用3種等漸近符號(hào)。3什么是數(shù)據(jù)結(jié)構(gòu)，什么是算法，兩者有什么關(guān)系？答：數(shù)據(jù)結(jié)構(gòu)：是指相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。算法：是對(duì)特

2、定問題求解步驟的一種描述是指令的有限序列。程序=算法+數(shù)據(jù)結(jié)構(gòu)5舉例說明分治法、動(dòng)態(tài)規(guī)劃法和貪心法適用范圍，及三者之間的區(qū)別。 答：分治法：適用于原問題可劃分為子問題時(shí)如漢諾塔問題（循環(huán)賽，最近對(duì)，棋盤覆蓋等）動(dòng)態(tài)規(guī)劃：當(dāng)原問題可分解為子問題并且問題重疊并且具有最優(yōu)子結(jié)構(gòu)時(shí)可用動(dòng)態(tài)規(guī)劃法，如TSP問題（多端最短路徑問題，0/1背包問題等）貪心：當(dāng)一個(gè)問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)且具有貪心選擇性時(shí)可用貪心算法，如最小生成樹問題（背包問題，活動(dòng)安排問題等）在分治法的基礎(chǔ)上，滿足最優(yōu)子結(jié)構(gòu)性質(zhì)才能用動(dòng)態(tài)規(guī)劃，在動(dòng)態(tài)規(guī)劃可行的基礎(chǔ)上滿足貪心選擇性才能用貪心。6簡述分治法、貪心法、蠻力法、回溯法、減治法的設(shè)計(jì)

3、思想。 答：分治：建一個(gè)難以直接解決的大問題劃分成一些規(guī)模較小的子問題，以便各個(gè)擊破，分而治之。貪心：把一個(gè)問題分解為一系列較為簡單的局部最優(yōu)選擇，每一步選擇都是對(duì)當(dāng)前解的一個(gè)擴(kuò)展，直到獲得問題的完整解。（指根據(jù)當(dāng)前已有信息做出選擇，不從整體最優(yōu)考慮，只選擇局部最優(yōu)）蠻力：采用一定的策略將待求解問題的所有元素依次處理一次，從而找出問題的解?；厮荩褐粯?gòu)造可能解的一部分，然后評(píng)估這個(gè)部分解，如果這個(gè)部分解有可能導(dǎo)致一個(gè)完全解，則對(duì)其進(jìn)一步構(gòu)造，否則，就不必繼續(xù)構(gòu)造這個(gè)解了。減治：把一個(gè)大問題劃分為若干子問題，但些子問題不需要分別求解，只需求解其中那個(gè)一個(gè)子問題。7舉例說明分治法和減治法的在設(shè)計(jì)上區(qū)

4、別與聯(lián)系。 答：分治法是將一個(gè)大問題分解為若干子問題分別求解，而減治法是只求解部分子問題。在排序問題中，分治法用用快速排序，以軸值為基準(zhǔn)劃分序列，再求每個(gè)子集遞歸序列，最后合并并操作。減治法則用選擇問題算法，先選定軸值并劃分，比軸值小的在左側(cè)，比軸值大的在右側(cè)，選擇問題的查找區(qū)間減少一半，劃分后只需處理一個(gè)子序列。8簡述什么是歐拉回路，TSP問題，哈密頓回路問題。 答： 歐拉回路：圖G的一個(gè)回路，若它恰它通過G 中每條邊一次，則稱該回路為歐拉回路。 TSP：從圖的一個(gè)頂點(diǎn)出發(fā)，各個(gè)定點(diǎn)只能經(jīng)歷并訪問一次，最后回到原點(diǎn)且使路徑最短。哈密頓回路：從一個(gè)城市出發(fā)，經(jīng)過每一個(gè)城市恰好一次，然后回到出發(fā)

5、城市。三應(yīng)用題1給出應(yīng)用動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法的一般步驟，并用動(dòng)態(tài)規(guī)劃法求下面多段圖中從頂點(diǎn)0到頂點(diǎn)15的最短路徑，寫出求解過程。解：d(0,9)=minc01 +d(1,9) , c02+d(2,9) , c03 +d(3,9) d(1,9)=minc14 +d(4,9) , c15+d(5,9) 2120345678949387684756866537d(2,9)=minc24 +d(4,9) , c25+d(5,9) , c26 +d(6,9) d(3,9)=minc35 +d(5,9) , c36+d(6,9) d(4,9)=minc47 +d(7,9) , c48+d(8,9) d(5,

6、9)=minc57 +d(7,9) , c58+d(8,9) d(0,9)=minc67 +d(7,9) , c68+d(8,9) d(7,9)= c79 =7 (79)d(8,9)= c89 =3(89)d(6,9)=min6+7,5+3=8(68)d(5,9)= min8+7,6+3=9(58)d(4,9)= min5+7,6+3=9(48)d(3,9)=min4+9,7+8=13(35)d(2,9)=min6+9,7+9,8+8=15(24)d(1,9)=min9+9,8+9=17(15)d(0,9)=min4+17,2+15,3+13=16(03)最后得最短路徑為03589 長度為16

7、。 2有4個(gè)物品，其重量分別為(4, 7, 5, 3)，物品的價(jià)值分別為(40, 42, 25, 12)，背包容量為10。試設(shè)計(jì)3種貪心策略,并給出在每種貪心策略下背包問題的解。 解：重量最輕：裝入1，4，3.總價(jià)值：40+12+25*3/5=67 價(jià)值最大：裝入1，2?？們r(jià)值：*3/4+42=72 性價(jià)比最小：裝入1，2.總價(jià)值：40+6/7*42=763給出23 13 49 6 31 19 28采用快速排序思想進(jìn)行排序時(shí)一次劃分的過程示意圖。19 13 49 6 31 23 2819 13 23 6 31 49 2819 13 6 23 31 49 281給定數(shù)組An，存儲(chǔ)n個(gè)實(shí)數(shù)，試設(shè)計(jì)

8、一個(gè)算法，在最壞情況下用最少比較次數(shù)找出該數(shù)組中元素的最大值和最小值，并說明采用了何種算法設(shè)計(jì)思想，其最壞比較多少次。答：求數(shù)組的最大值和最小值a)問題求給定數(shù)組a0:n-1的最大值和最小值。要求：最壞情況下用3n/2-2次比較b)分析采用分治法，把數(shù)組分成n/2組，每組2個(gè)數(shù)。然后每組的兩個(gè)數(shù)進(jìn)行一次比較，確定出每組的最大數(shù)和最小數(shù)保存在數(shù)組MAXi和MINi中，這樣總共進(jìn)行了n/2次比較。最后從MAXi中找出最大的數(shù)MAX，從MINi中找出最小的數(shù)MIN，需要2*（n/2-1）次比較。MAX和MIN就是原來問題的解?？偙容^次數(shù)為3n/2 2次該算法在任何情況下進(jìn)行的比較次數(shù)都是3n/2 2

9、,固最差情況也是3n/2 2.c)編程實(shí)現(xiàn)Quoted from 求數(shù)組的最大值和最小值:/two15.java/該算法在任何情況下的比較次數(shù)都是3N/2 -2。所以在最差情況下也是3N/2 -2import javax.swing.JOptionPane;public class two15  public static void main(String args)      int a=new int50;/    int min=new int25;/ 

10、60;  int max=new int25;/    int n=0,i=0,k=1;    String num;    String aa=new String50;        num=JOptionPane.showInputDialog("enter the total num of the array");   

11、     n=Integer.parseInt(num);        /單個(gè)數(shù)不進(jìn)行比較    if(n!=1)        for(i=0;i<n;i+)          aai=JOptionPane.showInputDialog

12、("請(qǐng)輸入數(shù)組的每個(gè)元素");            ai=Integer.parseInt(aai);            /用分治法把N個(gè)數(shù)分成2/N組 每組兩個(gè)進(jìn)行比較，把小的放在MIN，大的放在MAX     /最差情況下比較N/2次    

13、0; for(i=1;i<(n/2)*2;i=i+2)       if(ai-1<=ai)              mink-1=ai-1;maxk-1=ai;k+;            else    

14、;          mink-1=ai;maxk-1=ai-1;k+;                 /*在MAX中找出最大的，在MIN中找出最小的     *最差情況下比較2*（N/2-1）次     */   &

15、#160;int maxm=max0,minm=min0;        for(k=1;k<n/2;k+)          if(maxk>maxm) maxm=maxk;      if(mink<minm) minm=mink;         

16、;   if(n%2!=0)/N為奇數(shù)時(shí)，還要和最后一個(gè)數(shù)比較          if(an-1>maxm) maxm=an-1;      if(an-1<minm) minm=an-1;  JOptionPane.showMessageDialog(null,    "最大的數(shù)是"+maxm+"最小的數(shù)

17、是"+minm,    "result",JOptionPane.INFORMATION_MESSAGE);  else JOptionPane.showMessageDialog(null,    "一個(gè)數(shù)無須查找","警告！"    ,JOptionPane.INFORMATION_MESSAGE); 2描述貪心法的求解過程，給出基于最近鄰點(diǎn)策略采用貪心法求解TSP問題偽代

18、碼，并分析該算法的時(shí)間性能。偽代碼：1.P=; 2.V=V-u0;u=u0;/從頂點(diǎn)u0出發(fā)； 3循環(huán)直到集合P中包含n-1條邊 3.1查找與頂點(diǎn)u鄰接的最小代價(jià)邊（u，v）并且v 屬于集合V ；3.2 P=P+（u， v）；3.3 V=Vv； 3.4 u=v； /從頂點(diǎn)v出發(fā)繼續(xù)求解3設(shè)計(jì)算法實(shí)現(xiàn)求數(shù)組中相差最小的兩個(gè)元素（稱為最接近數(shù)）的差。算法 MinDistance(A0.n-1)/輸入:數(shù)組A0.n-1/輸出:the smallest distance d between two of its elements算法4.10最近對(duì)問題int ClosestPoints(S) /S為平面

19、上n個(gè)點(diǎn)的坐標(biāo)組成的集合 1if (n<2) return ; 2m=S中各點(diǎn)x坐標(biāo)的中位數(shù)； 3構(gòu)造S1和S2，使得S1中點(diǎn)的x坐標(biāo)小于m，S2中點(diǎn)的x坐標(biāo)大于m； 4d1=ClosestPoints(S1); d2=ClosestPoints(S2); 5d=min(d1, d2); 6構(gòu)造P1和P2，使得P1是S1中點(diǎn)的x坐標(biāo)與m的距離小于d的點(diǎn)集， P2是S2中點(diǎn)的x坐標(biāo)與m的距離小于d的點(diǎn)集; 7將P1和P2中的點(diǎn)按y坐標(biāo)升序排列； 8對(duì)P1中的每一個(gè)點(diǎn)p，在P2中查找與點(diǎn)p的y坐標(biāo)小于d的點(diǎn)，并求出其中的最小距離d'； 9return min(d, d' )；

20、4有n枚硬幣，其中有一枚硬幣是假幣，且假幣的重量較輕，通過一架天平找出假幣，。比較次數(shù)最少。答：減治算法。 先把n枚硬幣分成兩組，每組有2/n枚硬幣，如果n為奇數(shù)就留下一枚硬幣，然后把兩組硬幣分別放到天平的兩端。如果兩組硬幣重量相同，那么留下的硬幣就是假幣；否則，用同樣的方法對(duì)較輕的那組硬幣進(jìn)行同樣處理，應(yīng)為假幣一定在較輕的那組里.#include <iostream>#include <cstdlib> using namespace std;int Check_out(int B,int n);int main() int n,n1; cout<<&qu

21、ot;*n" cout<<"注意：n"<<" 真硬幣用1表示，假硬幣用0或2表示.n" cout<<" 0表示假硬幣比真硬幣輕，2表示假硬幣比真硬幣重。n"cout<<"*n" cout<<"請(qǐng)輸入硬幣的總個(gè)數(shù)：（請(qǐng)確定你輸入的總個(gè)數(shù)大于2，否則不能判斷出假的硬幣。）n" cin>>n; int *B=new intn; cout<<"請(qǐng)輸入硬幣：" for(int i=0;i<

22、;n;i+) cin>>n1; while(n1!=0&&n1!=2&&n1!=1) cout<<"對(duì)不起，你的輸入有誤，請(qǐng)重新輸入：" cin>>n1; Bi=n1; if (B0 + B1 +B2) = (B3 +B4 + B5) if (B0 = B6) cout<<"第8枚是假幣"/鏁扮粍涓槸con7 elsecout<<"第7枚是假幣" elseif (B0 + B1) = (B2 + B6) if (B3 + B4) = (B7 +

23、 B6) cout<<"第6枚是假幣" else if (B3 = B6) cout<<"第5枚是假幣" else cout<<"第4枚是假幣" else if (B0 + B1) = (B7 + B6) cout<<"第3枚是假幣" else if (B0 = B6) cout<<"第2枚是假幣" else cout<<"第1枚是假幣" system("PAUSE"); return

24、 EXIT_SUCCESS 5一個(gè)農(nóng)夫帶著一條狼、一只羊和一筐菜。并設(shè)計(jì)算法求解。解：帶羊到對(duì)岸,空手回本岸,帶狼到對(duì)岸, 帶羊回本岸, 帶菜到對(duì)岸, 空手回本岸 ,帶羊到對(duì)岸 #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_STEP 20 /index: 0 - 狼，1羊，2菜，3農(nóng)夫，value：0本岸，1對(duì)岸 int aMAX_STEP4; int bMAX_STEP; char *name = "空手", "帶狼",

25、"帶羊", "帶菜" ; void search(int iStep) int i; if (aiStep0 + aiStep1 + aiStep2 + aiStep3 = 4) for (i = 0; i < iStep; i+) if (ai3 = 0) printf("%s到對(duì)岸n", namebi + 1); else printf("%s回本岸n", namebi + 1); printf("n"); return; for (i = 0; i < iStep; i+) i

26、f (memcmp(ai, aiStep, sizeof(ai) = 0) return; if (aiStep1 != aiStep3 && (aiStep2 = aiStep1 | aiStep0 = aiStep1) return; for (i = -1; i <= 2; i+) biStep = i; memcpy(aiStep + 1, aiStep, sizeof(aiStep + 1); aiStep + 13 = 1 - aiStep + 13; if (i = -1) search(iStep + 1); else if (aiStepi = aiSt

27、ep3) aiStep + 1i = aiStep + 13; search(iStep + 1); int main() search(0); return 0; 6已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)其哈夫曼編碼，并請(qǐng)畫出其圖形，說明其設(shè)計(jì)思想。#include <stdio.h>#include <string.h>#define N 50 /*葉子結(jié)點(diǎn)數(shù)*/#define M 2*N-1 /*樹中結(jié)點(diǎn)總數(shù)*/typedef struct char data5;

28、 /*結(jié)點(diǎn)值*/ int weight; /*權(quán)重*/ int parent; /*雙親結(jié)點(diǎn)*/ int lchild; /*左孩子結(jié)點(diǎn)*/ int rchild; /*右孩子結(jié)點(diǎn)*/ HTNode;typedef struct char cdN; /*存放哈夫曼碼*/ int start; HCode;void CreateHT(HTNode ht,int n) int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) /*所有結(jié)點(diǎn)的相關(guān)域置初值-1*/hti.parent=hti.lchild=hti.rchild=-1; fo

29、r (i=n;i<2*n-1;i+) /*構(gòu)造哈夫曼樹*/ min1=min2=32767; /*lnode和rnode為最小權(quán)重的兩個(gè)結(jié)點(diǎn)位置*/ lnode=rnode=-1; for (k=0;k<=i-1;k+) if (htk.parent=-1) /*只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找*/ if (htk.weight<min1) min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode;hti.rchild=rnode; void CreateHCode(HTNode ht,HCode hcd,int n)int i,f,c; HCode hc; for (i=0;i<n;i+) /*根據(jù)哈夫曼樹求哈夫曼編碼*/ hc.start=n;c=i; f=hti.parent; while (f!=-1) /*循序直到樹根結(jié)點(diǎn)*/ if (htf.lchild=c) /*處理左孩子結(jié)點(diǎn)*