更轻或者更重？设计一个 θ(1)的算法来确定假币比真币重还是轻

Question

你有n>2个外观相似的硬币和一个没有砝码的天平。其中一枚为假币，但并不知道它比真币重还是轻。设计一个 的算法来确定假币比真币重还是轻。

Answer 1

我的想法： 主要是要确定哪一枚是假币。
1，n为偶数。
（1）则分成A,B相同数量的硬币在天平上称。 比如8， 分成4，4。A>B或者A<B。
（2）把A继续分成数量相同的硬币在天平上称，B也同样分成两份。 A1=2 A2=2,B1=2，B2=2. A1与A2比，B1与B2比。
哪个不平，假币就在那两份中。此时就能缩小范围，假币在其中，一份中。
（3）最后确定假币在两枚中的一枚，只要交其中一枚与其它的币在天平上称一次即可判断谁是假币。
当然，在n/2的时候，分成的数量可以是奇数，则可以看奇数时的情况。
2，n为奇数。
(1) 把n分成A,B,C三份。其中A=B=（n-1/）2; C=1;将A,B放在天平上称，如果A=B，则C是假币，将C与其它一枚硬币相比便知假币轻重。
（2），如果，A!=B.则返回成了n为偶数的情况。同样也能确定假币，知道假币轻重。

这个方法的时间复杂度，是lg（n）.