計算機算法設(shè)計與分析實驗報告專業(yè)：軟件工程（過程控制）學(xué)號：541213470163姓名：鄒錦程指導(dǎo)老師：孫海燕第第頁實驗一：棋盤覆蓋（遞歸與分治策略）一、實驗?zāi)康呐c要求1、明確棋盤覆蓋的概念2、明確遞歸與分治策略的設(shè)計思路。3、利用遞歸與分治策略解決棋盤覆蓋問題。二、實驗題：

問題描述：遞歸與分治策略算法，用4種不同形態(tài)的L型骨牌覆蓋一個給定的特殊棋盤上除特殊方格以外的所有方格,且任何2個L型骨牌不得重疊覆蓋。輸入數(shù)據(jù)由程序運行后的界面中的編輯框中輸入游戲規(guī)模,特殊方格的位置。將覆蓋的結(jié)果在窗口中顯示出來。 三、實驗代碼#include<iostream.h>inttile=1;intBoard[100][100];voidChessBoard(inttr,inttc,intdr,intdc,intsize) { if(size==1)return; intt=tile++;//L型骨牌號 ints=size/2;//分割棋盤 //覆蓋左上角子棋盤 if(dr<tr+s&&dc<tc+s) //特殊方格在此棋盤中 ChessBoard(tr,tc,dr,dc,s); else {//此棋盤中無特殊方格 //用t號L型骨牌覆蓋右下角 Board[tr+s-1][tc+s-1]=t; //覆蓋其余方格 ChessBoard(tr,tc,tr+s-1,tc+s-1,s); } //覆蓋右上角子棋盤 if(dr<tr+s&&dc>=tc+s) //特殊方格在此棋盤中 ChessBoard(tr,tc+s,dr,dc,s); else{//此棋盤中無特殊方格 //用t號L型骨牌覆蓋左下角 Board[tr+s-1][tc+s]=t; //覆蓋其余方格 ChessBoard(tr,tc+s,tr+s-1,tc+s,s); } //覆蓋左下角子棋盤 if(dr>=tr+s&&dc<tc+s) //特殊方格在此棋盤中 ChessBoard(tr+s,tc,dr,dc,s); else{//用t號L型骨牌覆蓋右上角 Board[tr+s][tc+s-1]=t; //覆蓋其余方格 ChessBoard(tr+s,tc,tr+s,tc+s-1,s);} //覆蓋右下角子棋盤 if(dr>=tr+s&&dc>=tc+s) //特殊方格在此棋盤中 ChessBoard(tr+s,tc+s,dr,dc,s); else{//用t號L型骨牌覆蓋左上角 Board[tr+s][tc+s]=t; //覆蓋其余方格 ChessBoard(tr+s,tc+s,tr+s,tc+s,s); } }voidmain(){ intsize; cout<<"輸入棋盤的size(大小必須是2的n次冪)："; cin>>size; intindex_x,index_y;cout<<"輸入特殊方格位置的坐標(biāo)："; cin>>index_x>>index_y; ChessBoard(0,0,index_x,index_y,size); for(inti=0;i<size;i++) { for(intj=0;j<size;j++) cout<<Board[i][j]<<"\t"; cout<<endl; }}

四、實驗結(jié)果輸入棋盤的size(大小必須是2的n次冪)：8輸入特殊方格位置的坐標(biāo)：333344889932248779526610107115560110111113131411181919131214141818171915121216201717211515161620202121Pressanykeytocontinue實驗二：矩陣連乘問題（動態(tài)規(guī)劃）實驗?zāi)康呐c要求1、明確矩陣連乘的概念。2、利用動態(tài)規(guī)劃解決矩陣連乘問題。二、實驗題：問題描述：給定n個矩陣｛A1,A2,...,An｝，其中Ai與Ai+1是可乘的，i=1，2...，n-1。確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。輸入數(shù)據(jù)為矩陣個數(shù)和每個矩陣規(guī)模，輸出結(jié)果為計算矩陣連乘積的計算次序和最少數(shù)乘次數(shù)。三、實驗代碼#include

"stdafx.h"

#include

<iostream>

using

namespace

std;

const

int

L

=

7;

int

RecurMatrixChain(int

i,int

j,int

**s,int

*p);//遞歸求最優(yōu)解

void

Traceback(int

i,int

j,int

**s);//構(gòu)造最優(yōu)解

int

main()

{

int

p[L]={30,35,15,5,10,20,25};

int

**s

=

new

int

*[L];

for(int

i=0;i<L;i++)

{

s[i]

=

new

int[L];

}

cout<<"矩陣的最少計算次數(shù)為："<<RecurMatrixChain(1,6,s,p)<<endl;

cout<<"矩陣最優(yōu)計算次序為："<<endl;

Traceback(1,6,s);

return

0;

}

int

RecurMatrixChain(int

i,int

j,int

**s,int

*p)

{

if(i==j)

return

0;

int

u

=

RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+p[i-1]*p[i]*p[j];

s[i][j]

=

i;

for(int

k=i+1;

k<j;

k++)

{

int

t

=

RecurMatrixChain(i,k,s,p)

+

RecurMatrixChain(k+1,j,s,p)

+

p[i-1]*p[k]*p[j];

if(t<u)

{

u=t;

s[i][j]=k;

}

}

return

u;

}

void

Traceback(int

i,int

j,int

**s)

{

if(i==j)

return;

Traceback(i,s[i][j],s);

Traceback(s[i][j]+1,j,s);

cout<<"Multiply

A"<<i<<","<<s[i][j];

cout<<"

and

A"<<(s[i][j]+1)<<","<<j<<endl;

}

四、實驗結(jié)果矩陣的最少計算次數(shù)為：15125矩陣最優(yōu)計算次序為：MultiplyA2,2andA3,3MultiplyA1,1andA2,3MultiplyA4,4andA5,5MultiplyA4,5andA6,6MultiplyA1,3andA4,6Pressanykeytocontinue\實驗三：背包問題（貪心算法）一、實驗?zāi)康呐c要求1、掌握背包問題的算法2、初步掌握貪心算法二、實驗題：

問題描述：有一個背包容量為Ｃ，輸入個物品，每個物品有重量，以及物品放入背包中所得的收益Ｐ。問選擇放入的物品，不超過背包的容量，且得到的收益最好。三、實驗代碼#include<iostream>usingnamespacestd;struct_Object//物品結(jié)構(gòu)體{ intValue;//物品價值 intWeight;//物品重量 intAveValue;//物品單位價值 floatNum;//物品可以放入的數(shù)量};voidknaspsack(intn,floatM,_Objectobject[]){//n為物品個數(shù)，M為背包容量 inti;floatC=M;for(i=0;i<n;i++){ object[i].Num=0;//初始化放入背包的物品為0 if(object[i].Weight>C)break;//當(dāng)物品重量大于背包容量時 else//小于時 { object[i].Num=1;//物品i放入一件 C-=object[i].Weight;//背包容量減小 } }if(i<=n)//當(dāng)不能放入整個物品時，選取物品一部分放入 object[i].Num=C/object[i].Weight; for(i=0;i<n;i++){ if(object[i].Num>0) cout<<"重量為:"<<object[i].Weight<<"價值為:"<<object[i].Value<<"的物品放入"<<object[i].Num<<"件"<<endl;}}voidSortObject(_Objectobject[],intn)//將各個物品按單位價值進行排序{ intj; _Objecttemp; inti; for(i=0;i<n;i++) object[i].AveValue=object[i].Value/object[i].Weight;//各個物品的單位價值 for(i=0;i<n-1;i++)//根據(jù)物品的單位價值對物品進行從大到小的冒泡排序 { for(j=0;j<n-i-1;j++) { if(object[j].AveValue<object[j+1].AveValue) { temp=object[j]; object[j]=object[j+1]; object[j+1]=temp; } } }}intmain(){_Objectobject[4];//4個物品intM=9;//背包容量為15object[0].Weight=2;object[0].Value=3;object[1].Weight=3;object[1].Value=4;object[2].Weight=4;object[2].Value=5;object[3].Weight=5;object[3].Value=7;SortObject(object,4);knaspsack(4,M,object);}

四、實驗結(jié)果重量為:2價值為:3的物品放入1件重量為:3價值為:4的物品放入1件重量為:4價值為:5的物品放入1件Pressanykeytocontinue實驗四：N后問題（回溯法）一、實驗?zāi)康呐c要求1、明確回溯算法的設(shè)計策略。2、利用回溯法解決N后問題。二、實驗題：問題描述：要求在一個n×n格的棋盤上放置n個皇后，使得他們彼此不攻擊。按照國際象棋的規(guī)則，一個皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子。因此，n后問題等價于要求在一個n×n格的棋盤上放置n個皇后，使得任何2個皇后不能被放在同一行或同一列或同一斜線上。求出問題的所有解。三、實驗代碼#include<iostream>#include<vector>#include<cmath>usingnamespacestd;structPoint{Point(int_x,int_y):x(_x),y(_y){}intx;inty;};classQueenProblem{public:QueenProblem(int_n):n(_n){}~QueenProblem(){}boolcheck(vector<Point>&vp,Point&p);voidsolve();voidprint();private:intn;vector<vector<Point>>vvp;};boolQueenProblem::check(vector<Point>&vp,Point&p){for(inti=0;i<vp.size();++i){if(vp[i].x==p.x||vp[i].y==p.y||abs(vp[i].y-p.y)==abs(vp[i].x-p.x))returnfalse;}returntrue;}voidQueenProblem::solve(){vector<Point>vp;intx=0;inty=0;while(x>=0){Pointpoint(x,y);while(point.y<n&&!check(vp,point)){point.y++;}if(point.y<n){vp.push_back(point);if(x==n-1){vvp.push_back(vp);vp.pop_back();y=point.y+1;}else{x++;y=0;}}else{x=x-1;if(vp.size()>0){y=vp.back().y+1;vp.pop_back();}}}}voidQueenProblem::print(){for(inti=0;i<vvp.size();++i){cout<<"[solution"<<i+1<<"]"<<endl;for(intj=0;j<vvp[i].size();++j){for(intk=0;k<n;++k){if(vvp[i][j].y==k){cout<<"Q";}else{cout<<"*";}}cout<<endl;}}}voidnQueen(intn){QueenProblemproblem(n);problem.solve();problem.print();}intmain(){nQueen(4);//四皇后return0;}

四、實驗結(jié)果實驗五：0-1背包問題（分支限界法）一、實驗?zāi)康呐c要求1、掌握0-1背包問題的算法；2、初步掌握分支限界法。二、實驗題：

問題描述： 利用分支限界法設(shè)計0/1背包問題的算法三、實驗代碼#include<stdio.h>#include<malloc.h>#defineMaxSize100//最多結(jié)點數(shù)typedefstructQNode{ floatweight; floatvalue; intceng; structQNode*parent; boolleftChild;}QNode,*qnode;//存放每個結(jié)點typedefstruct{ qnodeQ[MaxSize]; intfront,rear;}SqQueue;//存放結(jié)點的隊列 SqQueuesq; floatbestv=0;//最優(yōu)解 intn=0;//實際物品數(shù) floatw[MaxSize];//物品的重量 floatv[MaxSize];//物品的價值 intbestx[MaxSize];//存放最優(yōu)解 qnodebestE; voidInitQueue(SqQueue&sq)//隊列初始化 { sq.front=1; sq.rear=1; } boolQueueEmpty(SqQueuesq)//隊列是否為空 { if(sq.front==sq.rear) returntrue; else returnfalse; }voidEnQueue(SqQueue&sq,qnodeb)//入隊{if(sq.front==(sq.rear+1)%MaxSize) { printf("隊列已滿！"); }sq.Q[sq.rear]=b;sq.rear=(sq.rear+1)%MaxSize;}qnodeDeQueue(SqQueue&sq)//出隊{qnodee; if(sq.front==sq.rear) { printf("隊列已空"); return0; } e=sq.Q[sq.front]; sq.front=(sq.front+1)%MaxSize; returne;}voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild){ qnodeb; if(i==n)//可行葉子結(jié)點 { if(vt==bestv) { bestE=parent; bestx[n]=(leftchild)?1:0; } return; } b=(qnode)malloc(sizeof(QNode));//非葉子結(jié)點 b->weight=wt; b->value=vt; b->ceng=i; b->parent=parent; b->leftChild=leftchild;EnQueue(sq,b);}voidmaxLoading(floatw[],floatv[],intc){floatwt=0;floatvt=0;inti=1;//當(dāng)前的擴展結(jié)點所在的層floatew=0;//擴展結(jié)點所相應(yīng)的當(dāng)前載重量floatev=0;//擴展結(jié)點所相應(yīng)的價值 qnodee=NULL; qnodet=NULL;InitQueue(sq);EnQueue(sq,t);//空標(biāo)志隊列while(!QueueEmpty(sq)){ wt=ew+w[i]; vt=ev+v[i]; if(wt<=c) { if(vt>bestv)bestv=vt; EnQueue1(wt,vt,i,e,true);//左兒子結(jié)點進隊列}EnQueue1(ew,ev,i,e,false);//左兒子總是可行