事情是这样的，现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。渊子这就去买猪肉，结果找来的零钱中有假币！！！可惜渊子一不小心把它混进了一堆真币里面去了。现在知道假币的重量比真币的质量要轻。给你一个天平，请用最快的时间把那个可恶的假币找出来。
3 12 0
1 3
一、 首先我们先来考虑最简单的问题1。为了方便叙述，把n个硬币按1,2,…,n顺次编号。
二、 若n=3，把一号硬币放在天平左边、二号硬币放在天平右边。如果天平：
三、 左偏，一号重，是假币。
四、 右偏，二号重，是假币。
五、 保持平衡，那么一、二都是正常的硬币，因此就只有可能三号硬币是假币了。
六、 因此n=3，至多一次就能称出哪个是假币。记作f(3)=1。
七、 下面考虑n=9。把所有的硬币分成三组：A{1,2,3},B{4,5,6},C{7,8,9}。A组的硬币放在左边、B组放在右边。如果天平：
八、 左偏，则假币在A组里面。
九、 右偏，则假币在B组里面。
十、 保持平衡，假币在C组里面。
十一、 无论在哪个组里面，我们已经把假币的范围从“9”缩小到了“3”，也就是减少到原来的1/3。之前我们已经研究过，3个硬币1次就能称出来，故而f(9)=2。
十二、 不难推广到一般的情况：
十三、 定理1.1 f(3n)=n。
十四、 证明：n=1,2时，已证。设n=k成立，则f(3k)=k；下面考虑n=k+1的情况。
十五、 将3k+1个硬币分成三堆A, B, C，使得|A|=|B|=|C|=3k。把A放在天平左边、B放在右边，天平：
十六、 左偏，假币在A
十七、 右偏，假币在B
十八、 平衡，假币在C
十九、 无论哪种结果，我们都把假币的范围缩小到了3k个硬币里面。而f(3k)=k，故而f(3k+1)=k+1。
二十、 综上，定理1.1成立。
二十一、稍经分析不难得到：
二十二、定理1.2 f(n)=
二十三、这个的证明和定理1.1完全类似，分n mod 3 = 0, 1, 2适当讨论即可。
二十四、我们必须注意到 是可行的，因为我们能够构造出这样一个方案。问题是它是否最优？
二十五、我们采取的方案是每次将硬币尽量均匀的三分，这样做的根据就是天平只有三种结果：左偏、右偏、平衡。于是就能保证无论假币在哪一份都能将结果的范围缩小到原来的1/3。从感性上认识， 应该就是最优解了。
二十六、为了更加严格的证明 的最优性，我们引进判定树的概念。
二十七、下图就是n=9时的一种判定树：
二十八、此题的判定树是这样一棵树：
二十九、叶子节点代表一种可能的结果。
三十、 非叶子节点代表一次称量。
三十一、非叶子节点至多有三个儿子，分别代表天平的左偏、右偏、平衡三种情况。
三十二、任意一种称量方案都能唯一的表示成一棵判定树；反过来一棵判定树也唯一对应一种称量方案。
三十三、容易看出判定树的深度就是称量次数。这就是我们之所以引进它的原因。
三十四、做出判断之前，谁也无法预知哪个硬币是假币，每个都有可能是我们的目标；因此一个有意义的判定树应该具有至少n个叶子节点。
三十五、 n个叶子节点的树的深度h ≥ ，故而可以证明，f(n)= 是最优的。
三十六、 我们的结论是：有n（n≥3）个硬币，其中一个是假币，假币的重量比其他的要重一些。给一架天平，至少称 次，就能找出那个假币。
三十七、 具体的方案是将硬币每次都尽量均匀的三分。
三十八、 让我们总结一下。
三十九、 “三分”是整个解法的核心。我们选择三分，而不是二分或者四分是有原因的，它的本质是由判定树的特殊结构——三叉树——所决定的。
四十、 同时还必须注意一点，我们在三分的时候有两个字很讲究：“均匀”。实际上h ≥ 中的“=”当且仅当硬币被均匀的分配时才能达到。
四十一、 这里说的“均匀”是指“在最坏情况下获得最好的效果”。因为一棵树的深度是由它根节点儿子中深度最大的儿子决定的，为了使得整个树深度最小，我们就要务必使得深度最大的儿子深度最小，这就是“均匀”分配的理论根据。
参考代码
#include <stdio.h> #include <math.h> int main() { long int n; int m; while(scanf("%ld",&n)&&n) { m=(int)ceil(log(n*1.0)/log(3.0));//ceil()向上取整函数 log(n)/log(3)用三分法可证 printf("%d ",m); } return 0; }