称球问题总结

称球问题指有一堆球，除一个坏球外，所有球的重量都相同。用一个天平，需要称几次才能把这个球找出来。这个问题经常出现在面试和算法题中，最近看到该问题的一般公式，故记录下来。
如果以=代表天平平衡，<>代表天平不平衡，<和>代表天平倾斜的方向，整个称量过程就可以形成一棵三叉树，每一个球都对应于一个符号，像树上的结点。例如，称量次数为2时，有5个结点，意味着2次称量可以从5个球中找出那个坏球。同样，3次称量可以求出14个球的答案。
题中并不知道坏球是轻了还是重了，所以在天平第一次出现倾斜的时候，倾斜的方向是没有意义的，但这以后的方向却可以与第一次的不平衡参照，于是就知道坏球是轻是重了。
根据级数求和公式，称量n次所得到的状态数为1+1+3+3^2+3^3+...+3^(n-1)=(3^n+1)/2。
=路线表明坏球一定不在天平上，他必然在剩余的球里面。可见，第一次称量应该取<>分支所含状态数那么多的球来称。<>对应这天平两个盘之间球的交换。称量以前要交换一部分球，若方向变了，则坏球在交换的那部分中；若不变，则在未交换的那部分中。
到现在，我们知道，称量n次可以从(3^n+1)/2个球中找出那个与众不同的球来。第一次需要在天平两边各放(3^(n-1)-1)/2个球。