算法分析与设计实验报告

算法分析与设计

实验报告

班级： 学号： 姓名：

实验一 算法实现一

一、 实验目的与要求

熟悉C/C++语言的集成开发环境；

通过本实验加深对分治法、贪心算法的理解。

二、 实验内容:

掌握分治法、贪心算法的概念和基本思想，并结合具体的问题学习如何用相应策略进行求解的方法。

三、 实验题

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

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 << \请输入硬币的个数\

}

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;

cout<<\随机产生的硬币排列顺序\for(i=1;i<=n;i++) { }

cout<

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

cout<<\伪造硬币的位置：\cout<<\}

cout<

cout<

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

int total=0; int i;

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

}

total+=q[i];

return total;

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

if(a==b)

return a;

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

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;

} //break;

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 { } //break;

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;

case 2:

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

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