小球称重问题
最近在知乎看到一个有关香农信息论的问题回答，其中写道：
还有经典的称球问题，在13个球中有一个球质量与其他球不同，求设计出一种称量方案，使用一个不带砝码的天平在三次称量内找出该坏球。如果学过信息论，就知道上限为3^3/2=13.5，这种构造通常是依赖记忆信息的（记忆熵）。
这勾起了不懂信息论的我的好奇：对于这种小球称重问题的一般解法是什么？
小球称重问题：
有一组小球，其中有一个小球与其他所有小球的重量不同。使用天平进行称重，然后根据称重结果找出不同重的小球。
问题的下界
最少需要称多少次才能确保找到那个小球？
-
假设存在 N 个小球
- 只需要找到那个重量不同的小球，使用天平次数：
ceil(log3(2N+1)) - 找到那个重量不同的小球并且知道它比其他小球更轻还是更重，使用天平次数：
ceil(log3(2N+3)) - 如果提前已知那个重量不同的小球是更轻/更重，使用天平次数：
ceil(log3N)
- 只需要找到那个重量不同的小球，使用天平次数：
-
严格证明可以去看「小球称重问题」完整版解答汇总
经典问题
考虑一个经典的具体问题：
小球总数为12,使用天平称三次找出那个不同的小球并指出它是轻了还是重了.
套用上面的公式ceil(log3(2*N+3))可知我们确实能在 3 次称量中找到那个小球并指出它的轻重，理解这一点的关键是明白从称量 3 次中可以获得多少信息？我们知道每次称量将有三种情况：左倾(L)、平衡(N)、右倾(R)，进而可以将整个过程看成一个满的三层三叉树:
N
/ | \
1. L N R
/ | \ / | \ / | \
2. L N R L N R L N R
画不下了...
在最后一层我们有3^3也就是27种结果。
这个问题不借助计算机的非通用解法比较考验思维：
先将小球分成3组：
- A[
1,2,3,4] - B[
5,6,7,8] - C[
9,10,11,12]
这样在第一次称量结束后我们至少可以区分1/3的正常小球
- A[
1,2,3,4] vs B[5,6,7,8]- 如果平衡，说明问题球在C组中
[
1,2,3] vs [9,10,11]- 如果平衡，说明问题球是
12，将它单独拿出来与任意球称一次即可 - 如果不平衡，假设左边重（右边同理），说明问题球偏轻
[
9] vs [10]- 如果平衡，说明那个问题球是
11 - 如果不平衡，偏轻的那个是问题球
- 如果平衡，说明那个问题球是
- 如果平衡，说明问题球是
- 如果不平衡，假设左边重（右边同理）
[
1,2,5] vs [3,4,6]- 如果平衡，说明
7或8轻了，将他们两个拿出来称下即可 - 如果左边重，说明
12重或6轻，再称1和2即可 - 如果右边重，说明
34重或5轻，再称3和4即可
- 如果平衡，说明
- 如果平衡，说明问题球在C组中
[
程序设计
通过计算机使用三进制编号可以清楚地构造出该问题的通用解，具体算法还是参照上面的链接
package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
// 简单的单位三进制数，方便转换
type ternary struct {
n int
}
func (t *ternary) get() int {
return t.n
}
func (t *ternary) set(i int) {
t.n = i
}
func (t ternary) addOne() int {
if t.n == 2 {
return 0
} else {
return t.n + 1
}
}
func (t *ternary) incr() bool {
t.set(t.addOne())
return t.get() == 0
}
func addOneEach(t []ternary) {
incFlag := t[len(t)-1].incr()
if len(t) < 2 {
return
}
for i := len(t) - 2; i >= 0; i-- {
if incFlag {
incFlag = t[i].incr()
}
}
}
func lookForward(t []ternary) bool {
last := t[0].get()
if len(t) < 2 {
return true
}
for i := 1; i < len(t); i++ {
current := t[i].get()
if last != current {
// 算法关键
return (last == 0 && current == 1 ||
last == 1 && current == 2 ||
last == 2 && current == 0)
}
}
return false
}
func makeBalls(num int) []int {
balls := make([]int, num)
rn := rand.New(rand.NewSource(time.Now().UnixNano()))
isLighter := rn.Intn(2) == 0
// 倒数第二行可能被unset掉
badIndex := rn.Intn(num - 1)
if isUnset && badIndex == num-2 {
badIndex = num - 1
}
for i := range balls {
if i == badIndex {
if isLighter {
balls[i] = rn.Intn(9) + 1
} else {
balls[i] = rn.Intn(9) + 11
}
} else {
balls[i] = 10
}
if isUnset && i == num-1 {
fmt.Printf("%d. %d\n", num-1, balls[i])
} else if isUnset && i == num-2 {
} else {
fmt.Printf("%d. %d\n", i+1, balls[i])
}
}
return balls
}
var isUnset bool = false
func main() {
num := 100
times := 1
// go语言对数函数计算ceil(log3(2N+3))存在精度问题
for i := 3; i < 2*num+3; i = 3 * i {
times++
}
if num%3 != 0 {
isUnset = true
num++
}
balls := makeBalls(num)
pos := make([][]ternary, num)
for i := 0; i < num; i++ {
pos[i] = make([]ternary, times)
if i%3 == 0 {
if i == 0 {
pos[0][times-1].set(1)
} else {
copy(pos[i], pos[i-3])
addOneEach(pos[i])
for !lookForward(pos[i]) {
addOneEach(pos[i])
}
}
} else {
for j := 0; j < times; j++ {
pos[i][j].set(pos[i-1][j].addOne())
}
}
}
if isUnset {
for j := 0; j < times; j++ {
pos[num-2][j].set(1)
}
}
result := []int{}
freeBalls := []int{}
safeBalls := []int{}
for i := 0; i < times; i++ {
leftScale := []int{}
rightScale := []int{}
for j := 0; j < num; j++ {
if pos[j][i].get() == 0 {
leftScale = append(leftScale, j)
} else if pos[j][i].get() == 2 {
rightScale = append(rightScale, j)
} else if i == 0 {
freeBalls = append(freeBalls, j)
}
}
diffNum := len(leftScale) - len(rightScale)
// 如果num%3!=0，确保第一次正确执行并找出记录下至少1/3正常球
// 后面再用其中的正常球来配平
if diffNum != 0 {
sScale := append(leftScale, rightScale...)
sort.Ints(sScale)
safeIndex := -1
for _, j := range safeBalls {
index := sort.SearchInts(sScale, j)
if index < len(sScale) && sScale[index] != j {
// 找一个这次称量不需要放在天平两端的正常球
safeIndex = j
break
}
}
// 修复: 如果天平两端放上了所有正常球导致无法加球配平
if safeIndex == -1 {
// 从多的一方删除一个正常小球，这里为什么直接删第一个，一是图方便
// 二是这种情况一般出现在冗余较多的条件下，比如13个球称4次
// 会在第一次称量平衡后直接在某边放一个其他球进行第二次称量
if diffNum < 0 {
rightScale = rightScale[1:]
} else {
leftScale = leftScale[1:]
}
diffNum = len(leftScale) - len(rightScale)
}
if diffNum < 0 {
for j := 0; j < -diffNum; j++ {
leftScale = append(leftScale, safeIndex)
}
} else if diffNum > 0 {
for j := 0; j < diffNum; j++ {
rightScale = append(rightScale, safeIndex)
}
}
}
// 实际称量
reduce := func(scale []int) int {
sum := 0
for _, i := range scale {
sum += balls[i]
}
return sum
}
leftWeight := reduce(leftScale)
rightWeight := reduce(rightScale)
fmt.Printf("\n第%d次:\n", i+1)
printScales(leftScale, num)
if leftWeight == rightWeight {
result = append(result, 1)
print(" vs ")
} else if leftWeight < rightWeight {
result = append(result, 2)
print(" vs ▼ ")
} else {
result = append(result, 0)
print(" ▼ vs ")
}
// 第一次测量后保存1/3正常球列表
if isUnset && i == 0 {
if leftWeight == rightWeight {
safeBalls = append(leftScale, rightScale...)
} else {
safeBalls = freeBalls
}
}
printScales(rightScale, num)
println()
}
printResult(pos, result, "重")
for i := range pos {
for j := range pos[i] {
if pos[i][j].get() == 0 {
pos[i][j].set(2)
} else if pos[i][j].get() == 2 {
pos[i][j].set(0)
}
}
}
printResult(pos, result, "轻")
}
func printScales(scale []int, num int) {
print("[")
for i, j := range scale {
pi := j
if isUnset && j == num-1 {
pi = num - 2
}
print(pi + 1)
if i != len(scale)-1 {
print(",")
}
}
print("]")
}
func printResult(pos [][]ternary, result []int, s string) {
for i := range pos {
sq := true
for j := range pos[i] {
if pos[i][j].get() != result[j] {
// 要是支持 break 2 语法就好了
sq = false
}
}
posi := i
if isUnset && i == len(pos)-1 {
posi = len(pos) - 2
}
if sq {
fmt.Printf("\n该小球位于%d号,重量更%s\n", posi+1, s)
}
}
}运行结果：
1. 10
2. 10
3. 10
4. 10
5. 10
6. 10
7. 10
8. 2
9. 10
10. 10
11. 10
12. 10
第1次:
[1,4,7,10] vs [3,6,9,12]
第2次:
[1,6,9,12] ▼ vs [3,5,8,11]
第3次:
[3,4,9,11] ▼ vs [2,6,8,10]
该小球位于8号,重量更轻
N 为 100 时：
...
96. 10
97. 10
98. 7
99. 10
100. 10
第1次:
[1,4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55,58,61,64,67,70,73,76,79,82,85,88,91,94,97] vs [3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99]
第2次:
[1,4,7,10,13,16,19,22,25,28,31,34,37,42,45,48,51,54,57,60,63,66,69,72,75,78,81,84,87,90,93,96,99,40] ▼ vs [3,6,9,12,15,18,21,24,27,30,33,36,39,41,44,47,50,53,56,59,62,65,68,71,74,77,80,83,86,89,92,95,98,100]
第3次:
[1,4,7,10,15,18,21,24,27,30,33,36,39,40,43,46,49,52,55,58,61,64,69,72,75,78,81,84,87,90,93,95,98,100] vs ▼ [3,6,9,12,14,17,20,23,26,29,32,35,38,42,45,48,51,54,57,60,63,66,68,71,74,77,80,83,86,89,92,94,97,13]
第4次:
[1,6,9,12,13,16,19,24,27,30,32,35,38,40,43,46,51,54,57,59,62,65,67,70,73,78,81,84,86,89,92,94,97] vs [3,5,8,11,15,18,21,23,26,29,31,34,37,42,45,48,50,53,56,58,61,64,69,72,75,77,80,83,85,88,91,96,99]
第5次:
[3,4,9,11,13,18,20,22,27,29,31,36,38,40,45,47,49,54,56,58,63,65,67,72,74,76,81,83,85,90,92,94,99,100] ▼ vs [2,6,8,10,15,17,19,24,26,28,33,35,37,42,44,46,51,53,55,60,62,64,69,71,73,78,80,82,87,89,91,96,98,1]
该小球位于98号,重量更轻
只需要称量 5 次就可以找到