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

实验名称减治法在组合问题中的应用8枚硬币问题 实验室实验目的或要求1. 实验题目 在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。2.实验目的1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别；2）提高应用减治法设计算法的技能。3）理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。3. 实验要求1）设计减治算法实现8枚硬币问题；2）设计实验程序，考察用减治技术设计的算法是否高效；3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。4. 实现提示假设用一个数组Bn表示硬币，元素Bi中存放第i枚硬币的重量，其中n-1个元素的值都是相同的，只有一个元素与其他元素值不同，则当n=8时即代表8枚硬币问题。由于8枚硬币问题限制只允许使用天平比较轻重，所以，算法中只能出现元素相加和比较的语句实验原理（算法基本思想） 利用三分法if (p = q)else if (q - p = 1)if (p 0)if (arrp = arr0)coin(arr, n, p + 1, q);else coin(arr, n, p, q - 1);else if (q n - 1)if (arrp = arrn - 1)coin(arr, n, p + 1, q);elsecoin(arr, n, p, q - 1);else if (p q)int temp = (q - p + 1) / 3;int sum1 = 0, sum2 = 0;for(int i = 0; i temp; i+)sum1 += arrp + i;sum2 += arrq - i;if (sum1 = sum2)/在中间coin(arr, n, p + temp, q - temp);else/在两边,不在中间if (sum1 = arrp + temp * temp)/左边的和中间的相等,在右边coin(arr, n, q - temp + 1, q);elsecoin(arr, n, p, p + temp - 1);程序代码 /*/* *n枚硬币问题* */* *通用减治算法* */* *算法分析与设计* */*#include #include #include using namespace std;void coin(int arr, int n, int p, int q)if (n = 2)cout无法判断n;return;if (p = q)cout假币的序号为:p+1endl;cout假币的重量为:arrp 0)if (arrp = arr0)coin(arr, n, p + 1, q);else coin(arr, n, p, q - 1);else if (q n - 1)if (arrp = arrn - 1)coin(arr, n, p + 1, q);elsecoin(arr, n, p, q - 1);else if (p q)int temp = (q - p + 1) / 3;int sum1 = 0, sum2 = 0;for(int i = 0; i temp; i+)sum1 += arrp + i;sum2 += arrq - i;if (sum1 = sum2)/在中间coin(arr, n, p + temp, q - temp);else/在两边,不在中间if (sum1 = arrp + temp * temp)/左边的和中间的相等,在右边coin(arr, n, q - temp + 1, q);elsecoin(arr, n, p, p + temp - 1);void ShowCoin()while(1)int i,n;cout请输入几枚硬币：n;if(n=0) break;int *arr=new intn;cout请输入各硬币的重量：endl;for(i=0;iarri; coin(arr, n, 0, n - 1);