目录
1 问题描述
（1）实验题目
在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。
（2）实验目的
1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别；
2）提高应用减治法设计算法的技能。
3）理解这样一个观点：建立正确的模型对于问题的求解是非常重要的。
（3）实验要求
1）设计减治算法实现8枚硬币问题；
2）设计实验程序，考察用减治技术设计的算法是否高效；
3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。
（4）实现提示
假设用一个数组B[n]表示硬币，元素B[i]中存放第i枚硬币的重量，其中n-1个元素的值都是相同的，只有一个元素与其他元素值不同，则当n=8时即代表8枚硬币问题。由于8枚硬币问题限制只允许使用天平比较轻重，所以，算法中只能出现元素相加和比较的语句。
2 解决方案
2.1 减治法原理叙述
在说减法法原理之前，我们先来简单看看分治法原理：分治法是把一个大问题划分为若干子问题，分别求解子问题，然后再把子问题的解进行合并得到原问题的解。
而减治法同样是把大问题分解成为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，也无需对子问题进行合并。换种说法，可以说减治法是退化的分治法。
减治法原理正式描述：减治法（reduce and conquer method）将原问题的解分解为若干个子问题，并且原问题的解与子问题的解之间存在某种确定关系，如果原问题的规模为n，则子问题的规模通常是n/2 或n-1。
2.2 8枚硬币规模解法
求解思路：
（1）首先输入8枚硬币重量，存放在一个长度为8的一维数组中。
（2）定义a,b,c,d,e,f,g,h八个变量，分别对应一枚硬币的重量。然后把这8枚硬币分成三组，分别为abc(abc = a+b+c)、def(def = d+e+f)、gh。
（3）比较adc和def的大小。如果abc = def，则假币必定是g或者h，然后把g和h分别与真币a进行比较大小，从而得到假币。如果abc > def，则g和h必定为真币，然后比较ae（ae = a+e）和bd（bd = b+d）大小（PS：此处意思为ae = abc - c并把b和e交换位置，bd = def - f并把e和b交换位置），如果ae = bd，则假币必定是c或者f，然后依次与g比较，从而得到假币；如果ae > bd，则假币必定是a或者d，然后依次与g比较，从而得到假币；如果ae < bd，则假币必定是e或者b，然后依次与g比较，从而得到假币。
（4）abc < def情况参照（3）中思想求解，最终得到假币。
具体程序流程图如图1所示：
图1 8枚硬币问题规模程序流程图
具体代码如下：
package com.liuzhen.coin;import java.util.*;public class EightCoins { public static void printFakeCoin(int [] A){ int a,b,c,d,e,f,g,h; //八枚硬币重量 a = A[0]; b = A[1]; c = A[2]; d = A[3]; e = A[4]; f = A[5]; g = A[6]; h = A[7]; int abc = a+b+c; int def = d+e+f; //当abc重量大于def重量时，找出其中假币，并打印输出 if(abc > def){ if(a+e > b+d){ //此时，假币必定为a或者d if(a > g) System.out.println("假币为第1枚硬币，较重，重量为："+a); else{ if(a < g) System.out.println("假币为第1枚硬币，较轻，重量为："+a); else{ int test = d-g; if(test > 0) System.out.println("假币为第4枚硬币，较重，重量为："+d); else System.out.println("假币为第4枚硬币，较轻，重量为："+d); } } } if(a+e == b+d){ //此时，假币必定为c或者f if(c > g) System.out.println("假币为第3枚硬币，较重，重量为："+c); else{ if(c < g) System.out.println("假币为第3枚硬币，较轻，重量为："+c); else{ int test = f-g; if(test > 0) System.out.println("假币为第6枚硬币，较重，重量为："+f); else System.out.println("假币为第6枚硬币，较轻，重量为："+f); } } } if(a+e < b+d){ //此时，假币必定为b或者e if(b > g) System.out.println("假币为第2枚硬币，较重，重量为："+b); else{ if(c < g) System.out.println("假币为第2枚硬币，较轻，重量为："+b); else{ int test = e-g; if(test > 0) System.out.println("假币为第5枚硬币，较重，重量为："+e); else System.out.println("假币为第5枚硬币，较轻，重量为："+e); } } } } //当abc重量等于def重量时，则假币必定为g或者h if(abc == def){ if(g > a) System.out.println("假币为第7枚硬币，较重，重量为："+g); else{ if(g < a) System.out.println("假币为第7枚硬币，较轻，重量为："+g); else{ int test = h-a; if(test > 0) System.out.println("假币为第8枚硬币，较重，重量为："+h); else System.out.println("假币为第8枚硬币，较轻，重量为："+h); } } } //当abc重量小于def重量时，找出其中假币，并打印输出 if(abc < def){ if(a+e > b+d){ //此时，假币必定为b或者e if(b > g) System.out.println("假币为第2枚硬币，较重，重量为："+b); else{ if(b < g) System.out.println("假币为第2枚硬币，较轻，重量为："+b); else{ int test = e-g; if(test > 0) System.out.println("假币为第5枚硬币，较重，重量为："+e); else System.out.println("假币为第5枚硬币，较轻，重量为："+e); } } } if(a+e == b+d){ //此时，假币必定为c或者f if(c > g) System.out.println("假币为第3枚硬币，较重，重量为："+c); else{ if(c < g) System.out.println("假币为第3枚硬币，较轻，重量为："+c); else{ int test = f-g; if(test > 0) System.out.println("假币为第6枚硬币，较重，重量为："+f); else System.out.println("假币为第6枚硬币，较轻，重量为："+f); } } } if(a+e < b+d){ //此时，假币必定为a或者d if(a > g) System.out.println("假币为第1枚硬币，较重，重量为："+a); else{ if(a < g) System.out.println("假币为第1枚硬币，较轻，重量为："+a); else{ int test = d-g; if(test > 0) System.out.println("假币为第4枚硬币，较重，重量为："+d); else System.out.println("假币为第4枚硬币，较轻，重量为："+d); } } } } } public static void main(String args[]){ Scanner scan = new Scanner(System.in); int[] weightCoin = new int[8]; System.out.println("请您输入8枚硬币的重量（其中有一枚假币，其它硬币重量均相同）："); for(int i = 0; i < 8; i++) weightCoin[i] = scan.nextInt(); printFakeCoin(weightCoin); } } 运行结果截图如图2所示：
图2 8枚硬币问题运行结果截图
2.3 n枚硬币规模解法
求解思路：
此处我写了两个方法：
方法1：
/*返回一个长度为3的一维数组,result[0]表示假币轻重,值为0表示偏轻,值为1表示偏重;result[1]表示一枚真币的重量; result[2]表示,当硬币个数为奇数且最后一枚为假币时,把这枚假币重量赋值给result[2],否则result[2]值为0*/ public static int[] getJudgeCoinArray(int[] A)；
方法2：
/*返回一个长度为3的一维数组,result[0]表示假币轻重,值为0表示偏轻,值为1表示偏重;result[1]表示假币的重量; result[2]表示假币在硬币数组中的具体位置*/ public static int[] getFakeCoin(int[] A,int min,int max,int judge,int real)；
具体程序流程图如图3所示（PS：此处图画的不完整，主要是表达程序的思想，不要纠结哟）：
图3 n枚硬币问题规模程序流程图
具体代码如下：
package com.liuzhen.coin;import java.util.Scanner;public class NCoins { /*返回一个长度为3的一维数组,result[0]表示假币轻重,值为0表示偏轻,值为1表示偏重;result[1]表示假币的重量; result[2]表示假币在硬币数组中的具体位置*/ public static int[] getFakeCoin(int[] A,int min,int max,int judge,int real){ int[] result = new int[3]; //定义一个长度为3的一维数组，初始化所有值为0 if((max-min)%2 == 1){ //当max-min为奇数时，不能完成二分，判断A[max-1]是否为假币，若是，则直接返回结果，否则执行max= max-1 if(A[max-1] != real){ result[0] = judge; result[1] = A[max-1]; result[2] = max; return result; } max = max-1; } if(max-min == 2){ //当max-min为2时，此时只剩下两枚硬币，可以直接比较，找出假币 int a = A[min]-real; int b = A[max-1]-real; if(a != 0){ result[0] = judge; result[1] = A[min]; result[2] = min+1; } if(b != 0){ result[0] = judge; result[1] = A[max-1]; result[2] = max; } return result; } int sum1 = 0,sum2 = 0; // System.out.println("max-min值为："+(max-min));// System.out.println("judge值为："+judge); for(int i = 0;i<(max-min)/2;i++){ sum1 += A[min+i]; //二分后的左半部分硬币总重量 sum2 += A[(max+min)/2+i]; //二分后的右半部分硬币总重量 }// System.out.println("sum1值为："+sum1);// System.out.println("sum2值为："+sum2); //假币较重 if(judge == 1){ if(sum1 > sum2) max = (max+min)/2; //此时假币在左半部分 else min = (max+min)/2; //此时假币在右半部分 } //假币较轻 if(judge == 0){ if(sum1 > sum2) min = (max+min)/2; //此时假币在右半部分 else max = (max+min)/2; //此时假币在左半部分 }// System.out.println("min值为："+min);// System.out.println("max值为："+max); result = getFakeCoin(A,min,max,judge,real); //递归求解最终假币结果 return result; } /*返回一个长度为3的一维数组,result[0]表示假币轻重,值为0表示偏轻,值为1表示偏重;result[1]表示一枚真币的重量; result[2]表示,当硬币个数为奇数且最后一枚为假币时,把这枚假币重量赋值给result[2],否则result[2]值为0*/ public static int[] getJudgeCoinArray(int[] A){ int[] result = new int[3]; //定义一个长度为3的一维数组，初始化所有值为0 int len = A.length; //获取数组A的长度，即硬币的总个数 int a = A[len-1]; //最后一枚硬币重量，用于判断当硬币个数为奇数时，最后一枚硬币时假币的情况 if(len%2 == 1){ //当硬币总个数为奇数时，将硬币总个数减1，变成偶数 len = len-1; } int[] Left1 = new int[len/2]; //二分左半部分 int[] Right1 = new int[len/2]; //二分右半部分 int sum1 = 0,sum2 = 0; for(int i = 0;i sum2){ if(sum3 == sum4){ if(b > Left1[0]){ //此时可判断b为假币，且较重 result[0] = 1; result[1] = Left1[0]; result[2] = b; return result; } if(b < Left1[0]){ //此时可判断b为假币，且较轻 result[0] = 0; result[1] = Left1[0]; result[2] = b; return result; } //否则，假币在Right1中，且较轻 result[0] = 0; result[1] = Left1[0]; } if(sum3 != sum4){ //假币在Left1中，且较重 result[0] = 1; result[1] = Right1[0]; } } //当左半部分硬币重量小于右半部分重量时 if(sum1 < sum2){ if(sum3 == sum4){ if(b > Left1[0]){ //此时可判断b为假币，且较重 result[0] = 1; result[1] = Left1[0]; result[2] = b; return result; } if(b < Left1[0]){ //此时可判断b为假币，且较轻 result[0] = 0; result[1] = Left1[0]; result[2] = b; return result; } //否则，假币在Right1中，且较重 result[0] = 1; result[1] = Left1[0]; } if(sum3 != sum4){ //假币在Left1中，且较轻 result[0] = 0; result[1] = Right1[0]; } } //当左半部分硬币重量等于右半部分重量时 if(sum1 == sum2){ if(a > Left1[0]){ //此时可判断a为假币，且较重 result[0] = 1; result[1] = Left1[0]; result[2] = a; return result; } if(a < Left1[0]){ //此时可判断a为假币，且较轻 result[0] = 0; result[1] = Left1[0]; result[2] = a; return result; } } // System.out.println("sum3值为："+sum3);// System.out.println("sum4值为："+sum4); return result; } public static void main(String args[]){ Scanner sc = new Scanner(System.in); System.out.println("请您输入n枚硬币的总个数："); int n = sc.nextInt(); int[] A = new int[n]; System.out.println("请您输入n枚硬币的重量（其中有一枚假币，其它硬币重量均相同）："); for(int i = 0; i < n; i++) A[i] = sc.nextInt(); int[] result1 = getJudgeCoinArray(A); int len = A.length; //数组A的长度 int judge = result1[0]; //假币轻重判断 int real = result1[1]; //真币重量 int fakeCoin = result1[2]; //假币重量 System.out.println("硬币总个数为："+len); System.out.println("judge值为："+judge+"(1表示假币较重,0表示假币较轻)"); System.out.println("真币重量为："+real); if(fakeCoin != 0) System.out.println("假币重量为："+fakeCoin); else{ int[] result = getFakeCoin(A,0,len,judge,real); if(result[0] == 1) System.out.print("假币较重,"); else System.out.print("假币较轻,"); System.out.print("且假币是第"+result[2]+"硬币,"); System.out.println("假币重量为："+result[1]); } }} 运行结果截图如图4所示：
图4 n枚硬币问题规模运行结果截图
参考资料：
1、
2、