中国矿业大学计算机学院算法设计与分析实验报告

算法实验报告 实验一 用分治法实现元素选择 实验代码： #include using namespace std; int main() int a100,n,x; int BinarySearch(int a,const int coutn; coutai; coutx; if(BinarySearch(a,x,n)!=-1) coutamiddle) left=middle+1; else right=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; for(i=0;in; coutc; coutvi; coutwi; Knapsack(v,w,c,n,m); Traceback(m,w,c,n,x); coutb) return b; else return a; int max(int a,int b) if(ab) return a; else return b; void Knapsack(int *v,int *w,int c,int n,int *m) int i,j; int jMax=min(wn-1,c); for(j=0;j1;i-) jMax=min(wi-1,c); for(j=0;j=w1) m1c=max(m1c,m2c-w1+v1); void Traceback(int *m,int *w,int c,int n,int *x) for(int i=1;i #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=1;i-) for(j=i-1;j=1;j-) gij=gji; printf(“最小生成树为:n“); prim(g,n); 实验效果图： 实验四 用回溯法求解跳马问题 实验代码： /起始位置：0,0 #include 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;i=0 M=N; for(int k=0;k #include #include int 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; /L 型骨牌编号加 1 /处理左上角子棋盘 if(sprow = col0+s) chessboard(row0,col0+s,s,sprow,spcol); else chessarrrow0+s-1col0+s=t; chessboard(row0,col0+s,s,row0+s-1,col0+s); /处理左下角子棋盘 if(sprow = row0+s else chessarrrow0+scol0+s=t; chessboard(row0+s,col0+s,s,row0+s,col0+s); void main() int k,x,y; /阶数及特殊点位置 int i,j,n; /棋盘规模为 n*n coutk; coutxy; for (i=0,n=1;i using namespace std; int main() void hanoi(int,char,char,char); int m;cinm;hanoi(m,A,B,C); return 0; void hanoi(int n,char a,char b,char c) void move(int,char,char); if(n=1)mov