《中国矿业大学计算机学院算法设计与分析实验报告.doc》由会员分享，可在线阅读，更多相关《中国矿业大学计算机学院算法设计与分析实验报告.doc（13页珍藏版）》请在金锄头文库上搜索。
1、算法实验报告实验一 用分治法实现元素选择实验代码：#includeusing namespace std;int main()int a100,n,x;int BinarySearch(int a,const int&x,int n);cout请输入n(nn;cout请输入n个整数:endl;for(int i=0;iai;coutx;if(BinarySearch(a,x,n)!=-1)coutx是数组中第BinarySearch(a,x,n)+1个数。endl;elsecoutx不是数组中的数。endl;return 0;int BinarySearch(int a,const int &
2、x,int n)int left=0,right=n-1;while(leftamiddle)left=middle+1;elseright=middle-1;return -1;实验效果图：实验二 用动态规划法求解0/1背包问题实验代码：#include using namespace std;int main()void Knapsack(int *v,int *w,int c,int n,int *m);void Traceback(int *m,int *w,int c,int n,int *x);int v100,w100,n,c,*m,x100,i;m=new int *100;f
3、or(i=0;i100;i+)mi=new int100;coutn;coutc;cout请分别输入每个物品的价值:endl;for(i=1;ivi;cout请分别输入每个物品的重量:endl;for(i=1;iwi;Knapsack(v,w,c,n,m);Traceback(m,w,c,n,x);cout最优解为：endl;for(i=1;i=n;i+)coutxi ;coutb)return b;elsereturn a;int max(int a,int b)if(ab)return a;elsereturn b;void Knapsack(int *v,int *w,int c,int
4、 n,int *m)int i,j;int jMax=min(wn-1,c);for(j=0;j=jMax;j+)mnj=0;for(j=wn;j1;i-)jMax=min(wi-1,c);for(j=0;j=jMax;j+)mij=mi+1j;for(j=wi;j=w1)m1c=max(m1c,m2c-w1+v1);void Traceback(int *m,int *w,int c,int n,int *x)for(int i=1;in;i+)if(mic=mi+1c)xi=0;elsexi=1;c-=wi;xn=(mnc)?1:0;实验效果图：实验三 用贪心算法求解最小生成树实验代码：#
5、include #define inf 10000 #define max 50 void prim(int gmaxmax,int n) int lowcostmax,closestmax; int i,j,k,min; bool smax;s1=true;for(i=2;i=n;i+) lowcosti=g1i; closesti=1; si=false; for(i=1;in;i+) min=inf; j=1; for(k=2;k=n;k+) if(lowcostkmin)&(!sk) min=lowcostk; j=k; printf(%d, %d), %dt,closestj,j,m
6、in); sj=true; for(k=2;k=n;k+) if(gjklowcostk)&(!sk) lowcostk=gjk; closestk=j; printf(n); void main() int gmaxmax; int n,i,j; printf(结点数为:);scanf(%d,&n);printf(请输入点之间权重：n); for(i=1;i=n;i+) for(j=i+1;j=1;i-) for(j=i-1;j=1;j-) gij=gji;printf(最小生成树为:n); prim(g,n); 实验效果图：实验四 用回溯法求解跳马问题实验代码：/起始位置：0,0#incl
7、ude using namespace std;int M,N;int map100100;int count=0;/记录马共跳的步数int countnum=0;/用于统计走法种数int direction82=1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2;/马可能前进的8个方向int flag=0;void print_map()int t=0;for(int i=0;iM;i+)for(int j=0;jN;j+)coutmapijt;t+;if(t=M)coutendl;t=0;countnum=countnum+1;coutcountnum:endl
8、;void go(int i,int j)/改变标志位，环境变量等等：这些改变就相当于完成一步动作，在跳马问题中就是马向前跳一步count+;/计数器mapij=count;/棋盘置当前步数/如果找到匹配的，则输出结果if(count=M*N)/如果已经遍历棋盘则打印一次走法print_map();flag=1;/否则，找到当前步可能的路径即进行下一步动作；这里可能有多个分支，如跳马问题中马可以往八个方向跳，每个分支都要列举出来，以便回溯时使用else if(flag=0)int m,n;for (int k=0;k=0 & m=0 & nN)if(mapmn=0)go(m,n);/回退：还原
9、标志位，环境变量等mapij=0;/回退，置零count-;/计数器减int main()coutN;M=N;for(int k=0;kM;k+)for(int l=0;lN;l+)mapkl=0;go(0,0);return 0;实验效果图：附加题：1、棋盘覆盖问题实验代码：#include#include#includeint tile=0; /定义全局变量tile表示L型骨牌编号int *chessarr; /定义全局变量chessarr表示棋盘数组void chessboard(int row0,int col0,int size,int sprow,int spcol);/ 棋盘覆盖函数/ row0,col0为棋盘左上角位置，sprow,spcol为特殊方格位置/ size为棋盘规模void chessboard(int row0,int col0,int size,int sprow,int spcol) /棋盘覆盖函数 if(size=1) return; /如果棋盘规模=1，返回 int s=size/2; /分割棋盘 int t=+tile;
