算法：更轻或者更重？

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

【开始分析】

这个题目首先我们要明白我们只是需要确定假币是比真币重还是轻，所以说并不需要我们找出这枚硬币，所以按照这个思路继续往下走，那么我们可以确定在大多数的情况下在天平上只需要比较两次我们就可以分析出结果。

在看到这个题目之后，我的第一反应是这样划分：首先不考虑硬币少的情况下，我们假设有11个硬币，为奇数次，我们划分为两堆，每堆5枚硬币，多出来的一枚先放一遍，那么分情况进行第一次判断：

1.天平两边相等的情况下。

那么这是最好的情况，直接就可以判断出多出来的那一个就是假币，然后随便替换一边就可以得出哪边轻哪边重了，从而得出结论。

2.天平左边重或者轻的情况下。

每边平分之后我们既可以一眼看出哪边轻哪边重，这是第一次称，那么我们带着假设假币是轻的代入第二次称，依旧是平分，多出来一个或者不多出，那么如果两个相等说明剩下的那个是假币，再按照替换的方式就能得出结论。

但是这个方式行的通吗？明显是行不通的，我们不能用假设的思路去判断它，因为有很多不确定性，所以我们得换一种思路。

刚才我们想的是分成两堆硬币进行判断，但是这次我们试着分成三堆来判断。

那么由于n>2，我们就可以判断出两种情况：

情况一：当n是3的整数倍。我们可以将这堆硬币按数量等分为三堆，比如有12个硬币，我们等分为4 4 4 三堆。也设为A、B、C三堆，假币一定在其中一堆中。

第一次在天平上比较A堆和B堆的重量。分为三种子情况：

情况二：当n不是3的整数倍。此时仍然可以将这堆硬币按数量等分为三堆A、B、C，比如13个硬币，我们分成4 4 5。多出来的1~2个硬币先放到一边。

第一次在天平上比较A堆和B堆的重量。也分为三种子情况：

A=B，则A、B堆均为真币。说明假币一定在C堆中，我们可以随意从A、B堆中选择一边，然后第二次称再从另外一堆真币中拿一个真币与C堆称，如果A>C，那么假币就比真币轻，如果A<C，那么假币就比真币重。
A>B，则C堆一定全为真币，假币在A或B中。第二次称随意从A、B堆中选择一边，C堆去除一个与其中一堆称，例如与B堆，如果与B等重，说明B中全是真币，又因为A>B，所以假币是重于真币的，如果C>B，那么假币就是在B中，且假币比真币轻。那么会不会出现C<B<A呢，很明显这个就不成立了，因为假币只有一个，又已知C中全是真币，所以假币必须是在B和A中在其中一堆里。
A<B，同子情况b，C堆一定全为真币，假币在A或B中。第二次比较A堆与C堆，若A与C等重，则假币在B中且假币比真币重，若A比C重，则假币比真币重，若A比C轻，则假币比真币轻。