中國礦業(yè)大學計算機學院算法設計與分析實驗報告-2

算法實驗報告實驗一用分治法實現(xiàn)元素選擇實驗代碼：#include<iostream>usingnamespacestd;intmain(){ inta[100],n,x; intBinarySearch(inta[],constint&x,intn); cout<<"請輸入n(n<=100):"; cin>>n; cout<<"請輸入n個整數(shù):"<<endl; for(inti=0;i<n;i++) { cin>>a[i]; } cout<<"請輸入要查找的整數(shù)x:"; cin>>x; if(BinarySearch(a,x,n)!=-1) cout<<"x是數(shù)組中第"<<BinarySearch(a,x,n)+1<<"個數(shù)。"<<endl; else cout<<"x不是數(shù)組中的數(shù)。"<<endl; return0;}intBinarySearch(inta[],constint&x,intn){ intleft=0,right=n-1; while(left<=right) { intmiddle=(left+right)/2; if(x==a[middle]) returnmiddle; if(x>a[middle]) left=middle+1; else right=middle-1; } return-1;}實驗效果圖：實驗二用動態(tài)規(guī)劃法求解0/1背包問題實驗代碼：#include<iostream>usingnamespacestd;intmain(){ voidKnapsack(int*v,int*w,intc,intn,int**m); voidTraceback(int**m,int*w,intc,intn,int*x); intv[100],w[100],n,c,**m,x[100],i; m=newint*[100]; for(i=0;i<100;i++) m[i]=newint[100]; cout<<"請輸入物品個數(shù)n:"; cin>>n; cout<<"請輸入背包容量c:"; cin>>c; cout<<"請分別輸入每個物品的價值:"<<endl; for(i=1;i<=n;i++) cin>>v[i]; cout<<"請分別輸入每個物品的重量:"<<endl; for(i=1;i<=n;i++) cin>>w[i]; Knapsack(v,w,c,n,m); Traceback(m,w,c,n,x); cout<<"最優(yōu)解為："<<endl; for(i=1;i<=n;i++) cout<<x[i]<<''; cout<<endl; return0;}intmin(inta,intb){ if(a>b) returnb; else returna;}intmax(inta,intb){ if(a>b) returna; else returnb;}voidKnapsack(int*v,int*w,intc,intn,int**m){ inti,j; intjMax=min(w[n]-1,c); for(j=0;j<=jMax;j++) m[n][j]=0; for(j=w[n];j<=c;j++) m[n][j]=v[n]; for(i=n-1;i>1;i--) { jMax=min(w[i]-1,c); for(j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}voidTraceback(int**m,int*w,intc,intn,int*x){ for(inti=1;i<n;i++) { if(m[i][c]==m[i+1][c]) x[i]=0; else { x[i]=1; c-=w[i]; } x[n]=(m[n][c])?1:0; }}實驗效果圖：實驗三用貪心算法求解最小生成樹實驗代碼：#include<iostream>#defineinf10000#definemax50voidprim(intg[max][max],intn){ intlowcost[max],closest[max]; inti,j,k,min; bools[max]; s[1]=true; for(i=2;i<=n;i++) { lowcost[i]=g[1][i]; closest[i]=1; s[i]=false; } for(i=1;i<n;i++) { min=inf; j=1; for(k=2;k<=n;k++) if((lowcost[k]<min)&&(!s[k])) { min=lowcost[k]; j=k; }printf("(%d,%d),%d\t",closest[j],j,min);s[j]=true;for(k=2;k<=n;k++)if((g[j][k]<lowcost[k])&&(!s[k])) {lowcost[k]=g[j][k];closest[k]=j; } printf("\n"); }}voidmain(){ intg[max][max]; intn,i,j; printf("結點數(shù)為:"); scanf("%d",&n); printf("請輸入點之間權重：\n"); for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) { printf("%d%d:",i,j); scanf("%d",&g[i][j]); } for(i=n;i>=1;i--) for(j=i-1;j>=1;j--) g[i][j]=g[j][i]; printf("最小生成樹為:\n"); prim(g,n);}實驗效果圖：實驗四用回溯法求解跳馬問題實驗代碼：//起始位置：0,0#include<iostream>usingnamespacestd;intM,N;intmap[100][100];intcount=0; //記錄馬共跳的步數(shù)intcountnum=0; //用于統(tǒng)計走法種數(shù)intdirection[8][2]={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};//馬可能前進的8個方向intflag=0;voidprint_map(){ intt=0; for(inti=0;i<M;i++) { for(intj=0;j<N;j++) { cout<<map[i][j]<<"\t"; t++; if(t==M) {cout<<endl;t=0;} } }; countnum=countnum+1; cout<<countnum<<":"<<endl;}voidgo(inti,intj){ //改變標志位，環(huán)境變量等等：這些改變就相當于完成一步動作，在跳馬問題中就是馬向前跳一步 count++; //計數(shù)器 map[i][j]=count; //棋盤置當前步數(shù) //如果找到匹配的，則輸出結果 if(count==M*N) //如果已經遍歷棋盤則打印一次走法 { print_map(); flag=1; }//否則，找到當前步可能的路徑即進行下一步動作；這里可能有多個分支，如跳馬問題中馬可以往八個方向跳，每個分支都要列舉出來，以便回溯時使用 elseif(flag==0) { intm,n; for(intk=0;k<8;k++) { m=i+direction[k][0]; n=j+direction[k][1]; if(m>=0&&m<M&&n>=0&&n<N) if(map[m][n]==0) { go(m,n); } } } //回退：還原標志位，環(huán)境變量等 map[i][j]=0;//回退，置零 count--;//計數(shù)器減}intmain(){ cout<<"請輸入棋盤大小N:"; cin>>N; M=N; for(intk=0;k<M;k++) for(intl=0;l<N;l++) map[k][l]=0; go(0,0); return0;}實驗效果圖：附加題：1、棋盤覆蓋問題實驗代碼：#include<iomanip.h>#include<iostream.h>#include<stdlib.h>inttile=0;//定義全局變量tile表示L型骨牌編號int**chessarr;//定義全局變量chessarr表示棋盤數(shù)組voidchessboard(introw0,intcol0,intsize,intsprow,intspcol);//棋盤覆蓋函數(shù)//row0,col0為棋盤左上角位置，sprow,spcol為特殊方格位置//size為棋盤規(guī)模voidchessboard(introw0,intcol0,intsize,intsprow,intspcol)//棋盤覆蓋函數(shù){if(size==1)return;//如果棋盤規(guī)模=1，返回ints=size/2;//分割棋盤intt=++tile;//L型骨牌編號加1//處理左上角子棋盤if(sprow<row0+s&&spcol<col0+s)chessboard(row0,col0,s,sprow,spcol);else{chessarr[row0+s-1][col0+s-1]=t;chessboard(row0,col0,s,row0+s-1,col0+s-1);}//處理右上角子棋盤if(sprow<row0+s&&spcol>=col0+s)chessboard(row0,col0+s,s,sprow,spcol);else{chessarr[row0+s-1][col0+s]=t;chessboard(row0,col0+s,s,row0+s-1,col0+s);}//處理左下角子棋盤if(sprow>=row0+s&&spcol<col0+s)chessboard(row0+s,col0,s,sprow,spcol);else{chessarr[row0+s][col0+s-1]=t;chessboard(row0+s,col0,s,row0+s,col0+s-1);}//處理右下角子棋盤if(sprow>=row0+s&&spcol>=col0+s)chessboard(row0+s,col0+s,s,sprow,spcol);else{chessarr[row0+s][col0+s]=t;chessboard(row0+s,col0+s,s,row0+s,col0+s);}}voidmain(){intk,x,y;//階數(shù)及特殊點位置inti,j,n;//棋盤規(guī)模為n*ncout<<"請輸入棋盤的階數(shù)：";cin>>k;cout<<"請輸入特殊點的位置(從1開始)：";cin>>x>>y;for(i=0,n=1;i<k;i++)n*=2;//在堆內存中建立棋盤數(shù)組，填充特殊方格if((chessarr=newint*[n])==NULL){cout<<"Can'tallocatemorememory,terminating."<<endl;exit(1);}for(i=0;i<n;i++){if((chessarr[i]=newint[n])==NULL){cout<<"Can'tallocatemorememory,terminating."<<endl;exit(1);}}chessarr[x-1][y-1]=0;//填寫特殊方格tile=0;