算法实验报告(8枚硬币)

实验名称减治法在组合问题中的应用——8枚硬币问题实验室实验目的或要求1.实验题目在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。2.实验目的1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别；2）提高应用减治法设计算法的技能。3）理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。3.实验要求1）设计减治算法实现8枚硬币问题；2）设计实验程序，考察用减治技术设计的算法是否高效；3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。4.实现提示假设用一个数组B[n]表示硬币，元素B[i]中存放第i枚硬币的重量，其中n-1个元素的值都是相同的，只有一个元素与其他元素值不同，则当n=8时即代表8枚硬币问题。由于8枚硬币问题限制只允许使用天平比较轻重，所以，算法中只能出现元素相加和比较的语句实验原理（算法基本思想）利用三分法if(p==q){}elseif(q-p==1){if(p0){if(arr[p]==arr[0])coin(arr,n,p+1,q);elsecoin(arr,n,p,q-1);}elseif(qn-1){if(arr[p]==arr[n-1])coin(arr,n,p+1,q);elsecoin(arr,n,p,q-1);}}elseif(pq){inttemp=(q-p+1)/3;intsum1=0,sum2=0;for(inti=0;itemp;i++){sum1+=arr[p+i];sum2+=arr[q-i];}if(sum1==sum2)//在中间{coin(arr,n,p+temp,q-temp);}else//在两边,不在中间{if(sum1==arr[p+temp]*temp)//左边的和中间的相等,在右边{coin(arr,n,q-temp+1,q);}else{coin(arr,n,p,p+temp-1);}程序代码//******************************************************//**n枚硬币问题**//**通用减治算法**//**算法分析与设计**//******************************************************#includestdio.h#includeiostream#includestdlib.husingnamespacestd;voidcoin(intarr[],intn,intp,intq){if(n==2){cout无法判断\n;return;}if(p==q){cout假币的序号为:p+1endl;cout假币的重量为:arr[p]endl;}elseif(q-p==1){if(p0){if(arr[p]==arr[0])coin(arr,n,p+1,q);elsecoin(arr,n,p,q-1);}elseif(qn-1){if(arr[p]==arr[n-1])coin(arr,n,p+1,q);elsecoin(arr,n,p,q-1);}}elseif(pq){inttemp=(q-p+1)/3;intsum1=0,sum2=0;for(inti=0;itemp;i++){sum1+=arr[p+i];sum2+=arr[q-i];}if(sum1==sum2)//在中间{coin(arr,n,p+temp,q-temp);}else//在两边,不在中间{if(sum1==arr[p+temp]*temp)//左边的和中间的相等,在右边{coin(arr,n,q-temp+1,q);}else{coin(arr,n,p,p+temp-1);}}}}voidShowCoin(){while(1){inti,n;cout请输入几枚硬币：endl;cinn;if(n==0)break;int*arr=newint[n];cout请输入各硬币的重量：endl;for(i=0;in;i++)cinarr[i];coin(arr,n,0,n-1);}}（写不完时，可另加附页。）实验结果及分析实验名称实验室实验目的或要求实验原理（算法基本思想）程序代码（写不完时，可另加附页。）实验结果及分析心得体会成绩评定教师签名：年月日