算法所有實驗

1、一：棋盤覆蓋(分治法)#include #include #define max 100int tile = 1;using namespace std;void chessBoard(int tr,int tc,int dr,int dc,int size,int boardmaxmax)/* (tr,tc)左上角方格的位置(dr,dc)特殊方格的位置size :2Ak棋盤規(guī)模大小board:棋盤,board棋盤的左上角方格*/ if(size = 1) return;int t = tile+; /L 型骨牌號int s = size/2; / 分割棋盤覆蓋左上角棋盤if(dr tr+s

2、& dc tc+s)chessBoard(tr,tc,dr,dc,s,board); /特殊方格在這個棋盤中elseboardtr+s-1tc+s-1 = t;/用t號覆蓋右下角棋盤chessBoard(tr,tc,tr+s-1,tc+s-1,s,board);/ 覆蓋其余方格覆蓋右上角棋盤if(dr=tc+s)chessBoard(tr,tc+s,dr,dc,s,board); 特殊方格在棋盤中elseboardtr+s-1tc+s = t;chessBoard(tr,tc+s,tr+s-1,tc+s,s,board); / 覆蓋其余方格覆蓋左下角棋盤if(dr=tr+s & dc=tr+s

3、 & dc=tc+s)chessBoard(tr+s,tc+s,dr,dc,s,board); / 特殊方格在棋盤中elseboardtr+stc+s = t;chessBoard(tr+s,tc+s,tr+s,tc+s,s,board); / 覆蓋其余方格int main()int size=0;cout size dr dc;size=pow(2,size);boarddrdc = 99; /99表示是特殊方格cout vv endl;while(size!=-1)tile=1;chessBoard(tr,tc,dr,dc,size,board);for(int i=0;ivsize;i+

4、)for(int j=0;jvsize;j+)cout.width(2);coutvvboardijvv;coutvvendlvvendl;coutvv2Ak * 2Ak的棋盤、特殊方格的位置(dr,dc):請輸入k和dr dc#該操作以-1 結(jié)束vvendlvvendl;cin size dr dc;size=pow(2,size);boarddrdc = 99;cout vv endl;return 0;二：回溯法標(biāo)題：0-1背包問題時限：1000 ms內(nèi)存限制：10000 K總時限：3000 ms描述：需對容量為c的背包進行裝載。從n個物品中選取裝入背包的物品，每件物 品i的重量為wi

5、,價值為pi。對于可行的背包裝載，背包中物品的總重量 不能超過背包的容量，最佳裝載是指所裝入的物品價值最高。多個測例，每個測例的輸入占三行。第一行兩個整數(shù)：n（n=10）和c，第二 輸入：行n個整數(shù)分別是w1到wn，第三行n個整數(shù)分別是pl到pn。n和c都等于零標(biāo)志輸入結(jié)束。輸出：每個測例的輸出占一行，輸出一個整數(shù)，即最佳裝載的總價值。 TOC o 1-5 h z 211輸入樣例：2 3240 0輸出樣例:#include #define MAX 10using namespace std;typedef struct(float w;/物品的重量float p;/物品的價值float d;/

6、物品的單位價值int id;/物品的編號Part;typedef struct(Part rMAX+1;int length;Parts;int n;/包個數(shù)float c;/背包的容量float cw;/當(dāng)前重量float bestp=0;/當(dāng)前最優(yōu)價值float cp;/當(dāng)前價值Parts L;/背包集int Partition(Parts &L,int low,int high)int pivotkey;L.r0=L.rlow;pivotkey=L.rlow.d;while(lowhigh)while(low=pivotkey) -high;L.rlow=L.rhigh;while(lo

7、whigh & L.rlow.d=pivotkey) +low;L.rhigh=L.rlow;L.rlow=L.r0;return low;void QuickSort(Parts &L,int low,int high)int pivotloc;if(lowhigh)pivotloc=Partition(L,low,high);QuickSort(L,low,(pivotloc-1);QuickSort(L,(pivotloc+1),high);double bound(int i)double cleft=c-cw;double bound=cp;while(i=n & L.ri.w=cl

8、eft)cleft-=L.ri.w;bound+=L.ri.p;i+;if(in)bestp=cp;return;if(cw+L.ri.wbestp) backtrack(i+1); void knapsack(double cc)QuickSort(L,1,L.length);backtrack(1); int main()cin n c;L.length=n;while(n!=0 | c!=0)for(int i=1;i L.ri.w;for(int i=1;i L.ri.p;for(int i=1;i=n;i+)L.ri.d=L.ri.p/L.ri.w;L.ri.id=i;knapsac

9、k(c);coutbestp n c;return 0;三：分支限界法 實驗題目供1 題，第1題）標(biāo)題:旅行售貨員時限：1000 ms內(nèi)存限制:10000 K總時限:3000 ms描述:某售貨員要到若干城市去推銷商品，已知各城市之間的路程（或旅費）。他要 選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的路程 （或旅費）最小。各個城市之間可能是有向連通的、無向連通的、以及存在 某個城市不連通的情況，你的程序應(yīng)該能夠處理所有可能的情況。如下圖表示描述:各個城市間無向連通。各個城市間無向連通。第一行為一個整數(shù)n(n0表示從i至Uj的路程長度為len。對于上面圖示的問題 我們可以按照下

10、面方式輸入：輸入:4輸入:-1 30 6 430 -15106 5 -1 204 10 20 -1輸出:輸出占一行，對于給定的問題，如果找到了最小路程(花費)，輸出該最小花 費，如果沒有通路可以到達(dá)每個城市，則輸出-1。輸出:4-1 30 6 4輸入樣例:30 -1510輸入樣例:6 5 -1 2010 20 -1輸出樣例:25#include #include #define N 10#define MAX 1000第一次錯是對于有向圖來的情況，可能不是通路。using namespace std;int pathN+1N+1;int n;class HeapNode(public:floa

11、t lcost;/子樹費用的下界float cc;/當(dāng)前費用float rcost;/xs： n-1中頂點最小的出邊費用和int s;/根節(jié)點到當(dāng)前節(jié)點的路徑為x0： sint xN;/需要進一步搜索的頂點是xs+1： n-1HeapNode()(HeapNode(float lc,float ccc,float rc,int ss,int xx)( lcost=lc;cc=ccc;rcost=rc;s=ss;for(int i=0;in;i+) xi=xxi;運算符重載：比較的是結(jié)點的子集樹的最小花費bool operatornode.lcost;/if(lcost=node.lcost)

12、return 0;/else if(lcostnode.lcost) return -1;/else return 1;float bbTSP(int v)int flag=0;int minOutn+1;/最小出邊費用int minSum=0;/最小出邊費用和 priority_queue heap; for(int i=1;i=n;i+)計算最小出邊費用和minSum和minOutfloat min = MAX;for(int j=1;j=n;j+)if(pathijMAX & pathijmin) min=pathij;if(min=MAX) return MAX;minOuti=min

13、;minSum+=min;int xn;for(int i=0;in;i+) xi=i+1;HeapNode enode(0,0,minSum,0,x);float bestc=MAX;while(!flag & enode.sn-1)for(int i=0;in;i+) xi=enode.xi;if(enode.s=n-2)if(pathxn-2xn-1MAX & pathxn-11MAX& enode.cc+pathxn-2xn-1+pathxn-11bestc) /找出費用更小的回路bestc=enode.cc+pathxn-2xn-1+pathxn-11;enode.cc=bestc;

14、enode.lcost=bestc;enode.s+;heap.push(enode);elsefor(int i=enode.s+1;in;i+)if(pathxenode.sxiMAX)float cc=enode.cc+pathxenode.sxi;float rcost=enode.rcost-minOutxenode.s;float b=cc+rcost;if(bbestc)int xxN;for(int j=0;jn;j+) xxj=xj;xxenode.s+1=xi;xxi=xenode.s+1;HeapNode node(b,cc,rcost,enode.s+1,xx);hea

15、p.push(node);if(heap.empty() flag=1;elseenode=heap.top();heap.pop();for(int i=0;i n;for(int i=1;i=n;i+)for(int j=1;jpathij;if(pathij=-1)pathij=MAX;int vn+1;int best=bbTSP(v);if(best!=MAX)cout bestendl;elsecout -1endl;return 0;標(biāo)題:時限： 內(nèi)存限制:標(biāo)題:時限： 內(nèi)存限制:總時限:多邊形游戲1000 ms10000 K3000 ms多邊形游戲是一個單人玩的游戲，開始時有一

16、個由n個頂點構(gòu)成的多邊形。每 個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“+”或“*”。所有邊依次用 整數(shù)從1到n編號。游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：選擇一條邊E以及由E連接著的2個頂點V1和V2；(2)用一個新的頂點取代邊E以及由E連接著的2個頂點V1和V2。將由頂點V1 和V2的整數(shù)值通過邊E上的運算得到的結(jié)果賦予新頂點。描述:最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點上的整數(shù)值。描述:10輸入：輸入：輸出:輸入樣例:輸入共兩行，第一行一個整數(shù)n表示頂點個數(shù)，第二行共2*n個數(shù)，分別為數(shù) 字和字符。例如:對于上圖中的問題，我們可以這樣按輸入樣例中的例

17、子輸入，數(shù)學(xué)中的“+” 號代表加法，小寫字母“x ”代表乘法。一個整數(shù)，計算最高得分。510 + -1 x -2 x 3 + -8 x486輸出樣例:#include #define N 1000 using namespace std;int mNNH2;/從第n個點開始，計算m個點的最小值char opN;/各邊的操作，是“ + ”，或是“*”int vN;/各個頂點的值int minf;/在一定范圍內(nèi)的最小值int maxf;/在一定范圍內(nèi)的最大值void minMax(int n,int i,int s,int j)(int e5;int a=mis0,b=mis1;int r=(i+

18、s-1)%n+1;/斷開的位置：i+s-1，后面開始位置：r=(i+s-1)%5+1，繞回繼續(xù) int c=mrj-s0,d=mrj-s1;if(opr-1=+)/操作的數(shù)與前一個符號進行操作minf=a+c;maxf=b+d;elsee1=a*c;e2=a*d;e3=b*c;e4=b*d;minf=e1;maxf=e1;for(int k=2;kek) minf=ek;if(maxfek) maxf=ek;int ployMax(int n)for(int j=2;j=n;j+)/j是控制斷開的位置的for(int i=1;i=n;i+)/for(int s=1;sminf) mij0=mi

19、nf;if(mij1maxf) mij1=maxf;int temp=m1n1;for(int i=2;i=n;i+)if(tempn;for(int i=1;iviopi;for(int i=1;i=n;i+)_mi10=mi11=vi;/每一個剛開始的元素賦初值cout ployMax(n) endl;return 0;五：貪心算法標(biāo)題:單元最短路徑時限：1000 ms內(nèi)存限制:10000 K總時限:描述:3000 標(biāo)題:單元最短路徑時限：1000 ms內(nèi)存限制:10000 K總時限:描述:3000 ms給定一個帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是一個整數(shù)。另外， 還給定V中的一個頂

20、點，稱為源?，F(xiàn)在我們要計算從源到所有其他 各頂點的最短路徑長度。這里的長度是指路上各邊權(quán)之和。這個問 題通常稱為單源最短路徑問題.輸入：第一行為一個整數(shù)，表示包含源在內(nèi)的頂點的個數(shù)，接下來是一個n*n的矩 陣，矩陣中-表示此路不通，否則表示從該頂點到另一頂點的距離。例如對于 上圖所示的問題我們可以按輸入樣例中的方式輸入。50301010060 420輸出:輸出為一行共n-1個數(shù)，按序輸出從一號50301010060 420輸出:輸出為一行共n-1個數(shù)，按序輸出從一號（源）頂點到其它各頂點的最短路徑。-1 10 -1 30 100輸入樣例:-1 -1 50 -1 -1-1 -1 -1 -1 10

21、-1 -1 20 -1 60-1 -1 -1 -1 -1輸出樣例:10 50 30 60輸出樣例:10 50 30 60#include #define N 10#define Max 100000using namespace std;int aNN;/i和j之間的權(quán)重void dijkstra(int v,int n,int aNN,int distN-1,int prevN-1,bool sN)( int m=n-1;for(int i=1;i=m;i+)disti=avi;si=false;if(disti=Max)previ=0;else previ=v;distv=0;sv=tru

22、e;for(int i=1;i=m;i+)int temp=Max;int u=v;for(int j=1;j=m;j+)if(!sj&distjtemp)u=j； temp=distj;su=true;for(int j=1;j=m;j+)if(!sj&aujMax)(int newdist=distu+auj;if(newdist n;for(int i=0;in;i+)for(int j=0;j aij;if(aij=-1) aij=Max;int v=0,prevn-1,distn-1;bool sn;dijkstra(v,n,a,dist,prev,s);for(int i=1;in

23、-1;i+)cout disti;cout distn-1 endl;return 0;標(biāo)題：最小生成樹時限：1000 ms內(nèi)存限制：10000 K總時限：3000 ms描述:輸入:輸出:有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連 通關(guān)系，邊上的權(quán)為在這兩個城市之間修建高速公路的造價，研究 后發(fā)現(xiàn)，這個地圖有一個特點，即任一對城市都是連通的?，F(xiàn)在的 問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計可 使得工程的總造價最少。假定所有輸入的根節(jié)點或者源為第一個城 市或第一組數(shù)據(jù)。描述:輸入:輸出:請使用prim算法求解。n （城市數(shù)，1=n=100）；e （邊數(shù)）；以下e行

24、，每行3個數(shù)i,j,wij，表示在城市i,j之間修建高速公路 的造價。輸入樣例:輸出樣例:5811122輸入樣例:輸出樣例:581112233423435455212108963712332354#include #define N 10#define MAX 1000 using namespace std;int wN+1N+1;int n;void prim()/ int lowcostn+1;/到 j 的最小花費int closetn+1;/鄰接點，第j個點與到達(dá)點的最小權(quán)重 bool sn+1;s1=true;for(int i=2;i=n;i+)lowcosti=w1i;close

25、ti=1;si=false;for(int i=1;in;i+)/控 制次數(shù)的int min=MAX;int j=1;for(int k=2;k=n;k+)/第 k 個頂點 if(lowcostkmin)&(!sk)/k 還未放到 s 集合中 min=lowcostk;j=k;coutclosetj jendl;sj=true;for(int k=2;k=n;k+)/第 k 個頂點 if(wjk n e;for(i=1;i=n;i+)for(j=1;j=n;j+) wij=MAX;/賦初值for(int k=1;k i j c;wji=wij=c;/重新定義邊的值prim();return 0

26、;六：近似算法標(biāo)題：近似算法求解旅行售貨員問題時限：1000 ms內(nèi)存限制：10000 K總時限：3000 ms有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關(guān)系，邊 上的權(quán)為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一 描述：個特點，即任一對城市都是連通的。現(xiàn)在的問題是，要修建若干高速公路把所 有城市聯(lián)系起來，問如何設(shè)計可使得工程的總造價最少。假定所有輸入的根節(jié) 點或者源為第一個城市或第一組數(shù)據(jù)。n （城市數(shù)，1=n=100）；輸入：e （邊數(shù)）；以下e行，每行3個數(shù)i,j,wij,表示在城市i,j之間修建高速公路的造價。輸出：n-1行，每行為兩個城市的序號，表

27、明這兩個城市間建一條高速公路。582 23 12輸入樣例: TOC o 1-5 h z 4 10輸入樣例:3 85 94 65 3輸出樣例:305 7輸出樣例:30etn+1;/etn+1;/鄰接點，第j個點與到達(dá)點的最小權(quán)重#include #define N 10#define MAX 1000 using namespace std;int n;int wNN;int startN+1;int endN+1;void prim()int lowcostn+1;/到 j 的最小花費int closetn+1;/鄰接點，第j個點與到達(dá)點的最小權(quán)重 bool sn+1;s1=true;for(

28、int i=2;i=n;i+)lowcosti=w1i;closeti=1;si=false;for(int i=1;in;i+)/控 制次數(shù)的int min=MAX;int j=1;for(int k=2;k=n;k+)/第 k 個頂點 if(lowcostkmin)&(!sk)/k 還未放到 s 集合中 min=lowcostk;j=k;starti=closetj;endi=j;/將邊兩邊的定點記錄下來/coutclosetj jendl;sj=true;for(int k=2;k=n;k+)/第 k 個頂點 if(wjklowcostk)&(!sk)/k 還未放到 s 集合中 lowc

29、ostk=wjk;closetk=j;void approxTSP()從第一個頂點開始訪問，如果兩個點的父節(jié)點一致，根據(jù)先序遍歷，左孩子過度到右孩子。int minsum=0;for(int i=1;in;i+)for(int j=i+1;jn;j+)if(starti=startj)startj=endj-1;/for(int i=1;in;i+)minsum+=wstartiendi;minsum+=w1endn-1;coutminsum n e;for(i=1;i=n;i+)for(j=1;j=n;j+)wij=MAX;/賦初值for(int k=1;k i j c;wji=wij=c;

30、/重新定義邊的值prim();approxTSP();return 0;實驗考核標(biāo)題：3n+1問題時限：1000 ms內(nèi)存限制：10000 K總時限：3000 ms給出以下算法：input nprint nif n = 1 then STOPif n is odd then n 3n+1描述：5. else n - n/26. GOTO 2輸入 n=22，產(chǎn)生序列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1對于一個數(shù)n它的長度這樣定義，即為運行上述算法輸出的數(shù)的總個數(shù)。22 的長度就是16。對于輸入的兩個數(shù)i,j，你需要計算從i到j(luò)這些數(shù)的長度的最大值。輸入：輸入共一行，兩個數(shù)i,j.輸出：輸出共一行，即