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

算法实验报告

实验一 用分治法实现元素选择

实验代码：

#include using namespace std; int main() { }

int a[100],n,x;

int BinarySearch(int a[],const int&x,int n); cout<<\请输入n(n<=100):\cin>>n;

cout<<\请输入n个整数:\for(int i=0;i

cin>>a[i];

cout<<\请输入要查找的整数x:\cin>>x;

if(BinarySearch(a,x,n)!=-1) cout<<\是数组中第\个数。\else cout<<\不是数组中的数。\return 0;

int BinarySearch(int a[],const int &x,int n) { }

int left=0,right=n-1; while(left<=right) { }

int middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) 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 v[100],w[100],n,c,**m,x[100],i; m=new int *[100]; for(i=0;i<100;i++) m[i]=new int[100]; cout<<\请输入物品个数n:\ cin>>n;

cout<<\请输入背包容量c:\ cin>>c;

cout<<\请分别输入每个物品的价值:\ for(i=1;i<=n;i++) cin>>v[i];

cout<<\请分别输入每个物品的重量:\ for(i=1;i<=n;i++) cin>>w[i];

Knapsack(v,w,c,n,m); Traceback(m,w,c,n,x); cout<<\最优解为：\ for(i=1;i<=n;i++) cout<

int min(int a,int b) {

if(a>b) return b; else return a; }

int max(int a,int b) {

if(a>b) return a; else }

return b;

void Knapsack(int *v,int *w,int c,int n,int **m) {

int i,j;

int jMax=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]); }

void Traceback(int **m,int *w,int c,int n,int *x) {

for(int i=1;i

if(m[i][c]==m[i+1][c]) else { }

x[i]=1; c-=w[i]; x[i]=0;

x[n]=(m[n][c])?1:0;

实验效果图：

实验三 用贪心算法求解最小生成树

实验代码：

#include #define inf 10000 #define max 50

void prim(int g[max][max],int n) {

int lowcost[max],closest[max]; int i,j,k,min; bool s[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

for(k=2;k<=n;k++) if((lowcost[k]

{ min=lowcost[k]; j=k;

}

printf(\ %d), %d\\t\ s[j]=true;

for(k=2;k<=n;k++)

if((g[j][k]

printf(\

}

void main()