有一堆硬币，里面有一个假币，如何通过称重的方式尽快找出这个假币呢。
这个问题有两种不同难度的版本
已经假币质量比真币轻（重）
常规的解题思路是将硬币分成两队，然后称重，那么假币就在较轻的那一堆，接下来只要继续对较轻的那一堆再继续分成两堆进行称重，知道找出假币。当然，有一个需要额处理的情况就是如果硬币数量是奇数的话，分成两堆后，会多出一个硬币，如果分出的两堆重量，一样，那么多出的那个硬币就是假币了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public int findByDivide2WhenForgeLighter(Coin[] coins) {
if (coins.length == 1) {
return 0;
}
if (coins.length == 0) {
return -1;
}
int divide = divide2(coins.length);
int end = coins.length - 1;
if (coins.length % 2 != 0) {
end = coins.length - 2;
}
int total = total(0, divide - 1, coins);//total方法是对指定的硬币进行称重，当然在代码的实现里面就是将所有硬币的数量加起来，这里不再赘述
int total1 = total(divide, end, coins);
if (total < total1) {
return findByDivide2WhenForgeLighter(Arrays.copyOfRange(coins, 0, divide));//递归
} else if (total > total1) {
return findByDivide2WhenForgeLighter(Arrays.copyOfRange(coins, divide, end));//递归
} else if (coins.length % 2 != 0) {
//如果硬币的个数是奇数的话，那么分堆后肯定会多出来一个硬币，如果分出来的两堆硬币重量一样，这个多出来的就肯定是假币
return coins.length - 1;
} else {
//如果
return -1;
}
}
|
其中分堆的方法可以定义成如下
1
2
3
4
5
6
7
8
| private int divide2(int length) {
if (length % 2 == 0) {
//如果是偶数的话直接分成等量的两堆
return length / 2;
} else {//如果是奇数的话，取掉最后一个硬币后再进行分（其实就是分成了三堆，其中一堆只有一个）
return (length - 1) / 2;
}
}
|
当然我们还可以使用另外一种进阶的方式，就是分成三堆，分成三堆可以实现，称重一次排除掉两堆，平均的情况下可以实现每次称重后都将硬币的规模缩减为原来的1/3。这样可以大幅度的减少称重的次数，特别是硬币比较多的时候。代码实现如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public int findByDivide3WhenFakeLighter(Coin[] conins) {
if (conins.length <= 1) {
return conins.length - 1;
}
int[] divides = divide3(conins.length);
int total1 = total(0, divides[0] - 1, conins);
int total2 = total(divides[0], divides[1] - 1, conins);
if (total1 < total2) {//假币在第一堆（比较轻）
return findByDivide3WhenFakeLighter(Arrays.copyOfRange(conins, 0, divides[0]));
} else if (total1 > total2) {//假币在第二堆
return findByDivide3WhenFakeLighter(Arrays.copyOfRange(conins, divides[0], divides[1]));
} else {//假币在第三堆
return findByDivide3WhenFakeLighter(Arrays.copyOfRange(conins, divides[1], conins.length));
}
}
|
其中分堆的算法实现如下：
1
2
3
4
5
6
7
8
9
| //返回的数组[0]是第一堆的结束位置，[1]是第二堆的结束位置
//特别处理当硬币个数只有两个的时候，只分成两堆
private int[] divide3(int length) {
if (length < 3) {
return new int[]{1, 2};
}
int size = length / 3;
return new int[]{size, 2 * size};
}
|
上面提到的都是用减量递归的方式查找假币，下面尝试使用迭代的算法来实现一个分两堆的代码（分成三堆的实现模式差不多，不再赘述）。算法重只需要根据重量来改变指示剩余硬币的数量，基本的实现基础是剩下的硬币在代码中使用的存储是连续的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int findByDivide2WhenForgeLighterIteration(Coin[] coins) {
int newStart = 0, newEnd = coins.length -1;
//两个指针之间的硬币就是剩余的硬币
while (newStart != newEnd) {
int divide = divide2(newEnd - newStart + 1);
int total1 = total(newStart, newStart + divide, coins);
int total2 = total(newStart + divide, newEnd, coins);
if(total1 == total2){
return -1;
}else if(total1 > total2){
//将第一个指针往后移动到划分的位置
newStart += divide;
}else{
//将第二个指针往前移动
newEnd = newStart + divide;
}
}
return newStart;
}
|
不知道假币是比较轻还是比较重
分两堆
如果不知道假币重量的情况下，分两堆的算法也是可以做到的：
- 等分两堆
- 如果刚刚好分成两堆（偶数），随机选择一堆再进行等分，然后进行称重，如果一样的话，那么假币肯定在第二堆，就可以舍弃第一堆后再对余下的硬币重复以上步骤。
- 如果是奇数，对分好的两堆称重，如果相等，那么多出来的那个就是假币，否则随机选择一堆再进行等分，然后进行称重分析（参考前面步骤）。
分三堆
在这里实现一个分三堆的算法（感觉逼格比较高）。实现思路是，分三堆，其中第一堆和第二堆个数相同，第三堆是分完两堆后余下的硬币。然后对第一堆和第二堆的重量进行比较，如果相同，那么假币肯定在第三堆，如果不相同，那么排除第三堆，混合第一堆和第二堆后重新分成三堆进行称重分析。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int findByDivide3WithUnknownWeight(Coin[] coins) {
if (coins.length <= 1) {
return coins.length - 1;
}
int[] divides = divide3(coins.length);
int total1 = total(0, divides[0] - 1, coins);
int total2 = total(divides[0], divides[1] - 1, coins);
if (total1 == total2) {
return findByDivide3WithUnknownWeight(Arrays.copyOfRange(coins, divides[1], coins.length));
} else {
return findByDivide3WithUnknownWeight(Arrays.copyOfRange(coins, 0, divides[1]));
}
}
|
分堆用到的算法和之前的一样，可以应付个数不是三的倍数时候的情况。
这个算法的效率其实可以通过挑战第一堆和第二堆硬币数量的个数来进一步优化。在此不再赘述。
迭代算法
当然还是要弄个非递归的算法来炫耀一下技术滴（分三堆）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public int findByDivide3WithUnknownWeightIteration(Coin[] coins) {
int start = 0;
int end = coins.length - 1;
while (start != end) {
int[] divides = divide3(end + 1 - start);
int total1 = total(0, divides[0] - 1, coins);
int total2 = total(divides[0], divides[1] - 1, coins);
if (total1 == total2) {
//舍弃前面的（选择第三堆进行接下来的分析）
start = divides[1];
} else {
//排除第三堆里的硬币，并且将前两堆重新划分成三堆
end = divides[1];
}
}
return start;
}
|
