2013河北工业大学算法实验报告

实验一 算法实现一

实验题

1. 【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。 源程序：

#include<iostream.h> #include<stdlib.h> #include<time.h>

int findTheCoin(int q[],int a,int b); int quantity(int q[],int a,int b); void main() {

time_t ts;

srand((unsigned) time(&ts)); const int Max=70; int n,k; while(true) {

cout << "请输入硬币的个数"<< endl; cin >> n; int q[Max]; int i;

for( i=1;i<=n;i++) { }

k=rand()%n; if(k==0)

k=n; q[i]=2;

q[k]=1;

}

for(i=1;i<=n;i++) { }

cout<<endl;

int p=findTheCoin(q,1,n);

cout<<"伪造硬币的位置："<<p<<endl; cout<<"======================="<<endl; }

cout<<q[i]<<" "; if(i%5==0)

cout<<endl;

int quantity(int q[],int a,int b) { }

int findTheCoin(int q[],int a,int b) {

if(a==b)

return a; int total=0; int i;

for( i=a;i<=b;i++)

total+=q[i];

return total;

int n=b-a+1; int c=n%3; int m=a+n/3-1; int d; switch(c) {

if (quantity(q,a,m)==quantity(q,m+1,m+n/3)) { }

else if (quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3))) { } else { } //break;

d=findTheCoin(q,a,m); return d;

d=findTheCoin(q,m+1,m+n/3); return d;

d=findTheCoin(q,m+n/3+1,m+2*(n/3)); return d;

case 1:

if( (quantity(q,a,m)==quantity(q,m+1,m+n/3)) &&

(quantity(q,m+n/3+1,m+2*(n/3))==quantity(q,m+1,m+n/3)) )

return m+2*(n/3)+1;

else {

if (quantity(q,a,m)==quantity(q,m+1,m+n/3)) { }

else if (quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3))) { } else

d=findTheCoin(q,m+1,m+n/3); return d;

d=findTheCoin(q,m+n/3+1,m+2*(n/3)); return d;

}

}

d=findTheCoin(q,a,m); return d;

//break;

case 2:

if(q[m+2*(n/3)+1]==q[m+2*(n/3)+2]) { } else { }

if(q[m+2*(n/3)+2]==q[1])

return m+2*(n/3)+1;

//cout<<"伪造硬币的号码是"<<3*m+1<<endl; if (quantity(q,a,m)==quantity(q,m+1,m+n/3)) { }

else if (quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3))) { } else { }

d=findTheCoin(q,a,m); return d;

d=findTheCoin(q,m+1,m+n/3); return d;

d=findTheCoin(q,m+n/3+1,m+2*(n/3)); return d;

else

return m+2*(n/3)+2;

//cout<<"伪造硬币的号码是"<<3*m+2<<endl;

}

//return true;

实验结果：

2. 【找零钱问题】一个小孩买了价值为33美分的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。 源程序：（java程序） public class zhaoling {

public static void main(String args[]) { int i=67;

int a25=0,a10=0,a5=0,a1=0;

System.out.println("要找的零钱:"+i+"美分"); a25=(i/25); a10=(i%25)/10;

a10=(i%25)%10/5; 1=(i%25)%10%5/1;

System.out.println("各面值张数为："); System.out.println("25美分的"+a25+"张"); System.out.println("10美分的"+a10+"张"); System.out.println("5美分的"+a5+"张"); System.out.println("1美分的"+a1+"张"); } }

实验结果：

实验二 算法实现二

实验题

1. "0-1"背包问题的贪心算法

源程序： #include"stdio.h" void main(void) {

//冒泡排序 for(i=0;i<4;i++) {

for(j=0;j<4-i;j++) {

if(x[j]<x[j+1]) {

//交换单位价值

int C=6;//背包容量6 int n=5;//5个物品

int w[]={3,2,1,4,5};//物品重量 int v[]={25,20,15,40,50};//物品价值 int x[]={0,0,0,0,0};//单位价值初始化 int q[5];

int m,i,j,p,vx,wx,k,ii; int V=0;//总价值初始化 //计算单位价值

printf("单位价值为：\n"); for(m=0;m<5;m++) { }

q[m]=m; x[m]=v[m]/w[m];

printf("x[%d]=%d\t",m,x[m]);

x[j]=x[j+1]; x[j+1]=p;

//交换价值对应位置

vx=v[j]; v[j]=v[j+1]; v[j+1]=vx;

//交换重量对应位置

} k=i;

}

V+=v[i]; C=C-w[i];

for(i=0;i<n&&w[i]<C;i++) {

if(w[i]<=C) { }

printf("\n单位价值降序为：\n"); for(i=0;i<5;i++)

printf("x[%d]=%d\t",i,x[i]); }

}

wx=w[j]; w[j]=w[j+1]; w[j+1]=wx; //交换商品编号 m=q[j]; q[j]=q[j+1]; q[j+1]=m;

//装入背包

{ }

for(ii=0;ii<=k;ii++) {

printf("\n放入第%d个物品：\n物品的重量为：%d\n物品的价值为：%d\n背包剩V+=v[i]*C/w[i]; C=0;

余容量为：%d\n",q[ii]+1,w[ii],v[ii],C); }

实验结果：

}

printf("\n总价值为：%d\t",V);

本次实验是以贪心算法解决背包问题，贪心算法要求出每个物品的单位价值，根据单位价值降排列，再依次装入背包。当最后一个物品不能完全装入时，装入部分使背包容量为0。在本次实验中，遇到的难题是：装入背包过程如何保证装入不完整物品，即背包剩余容量不能满足完全放入下一个物品。通过本次试验又熟悉了冒泡算法的 …… 此处隐藏：3483字，全部文档内容请下载后查看。喜欢就下载吧 ……