有假币(PAT)

1.题目描述

居然有假币！现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。nowcoder这就去买猪肉，结果找来的零钱中有假币！！！可惜nowcoder一不小心把它混进了一堆真币里面去了。只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），请用最快的时间把那个可恶的假币找出来。

2.输入描述:

1≤n≤2^30,输入0结束程序。

3.输出描述:

最多要称几次一定能把那个假币找出来？

4.输入例子:

3
12
0

5.输出例子:

1
3

6.解题思路：

题意：求出（在最快的称量方法下）最多要称量的次数
先枚举，再找规律
n=1个硬币，称量 0次，称量硬币的分配为（1，0，0）
n=2个硬币，称量 1次，称量硬币的分配为（1，1，0）
n=3个硬币，称量 1次，称量硬币的分配为（1，1，1）
n=4个硬币，称量 2次，称量硬币的分配为（1，1，2）
n=5个硬币，称量 2次，称量硬币的分配为（1，2，2），
n=6个硬币，称量 2次，称量硬币的分配为（2，2，2）
n=7个硬币，称量 2次，称量硬币的分配为（2，2，3）
n=8个硬币，称量 2次，称量硬币的分配为（2，3，3）
n=9个硬币，称量 2次，称量硬币的分配为（3，3，3）
n=10个硬币，称量 3次，称量硬币的分配为（3，3，4）

如果n % 3 = 0，分成 n/3、 n/3、 n/3三部分
如果n % 3 = 1，分成 n/3、 n/3、1 + (n/3)三部分
如果n % 3 = 2，分成 n/3、 1 + (n/3)、1 + (n/3)三部分
首先我们肯定先比较相同数量硬币的两部分（考虑最坏情况）
如果n % 3 = 0， n/3与n/3比较，然后再在n/3个中重复以上分配
如果n % 3 = 1， n/3与n/3比较，然后再在1+n/3个中重复以上分配
如果n % 3 = 2， 1+n/3与1+n/3比较，然后再在1+n/3个中重复以上分配

例如：
一、当n=6、9个硬币，称量 2次，称量硬币的分配为（2，2，2）、（3、3、3）
2和2比较，3和3比较，不管重量相等还是不相等，下次比较的硬币数量都是一样的
二、当n=4、7时，称量硬币的分配为（1，1，2）、（（2，2，3）
1和1比较，2和2比较，重量相等和不相等，下次比较的硬币数量是不一样的，而我们要从中考虑最坏的情况，那么只能假设重量相等，因为1+n/3大于n/3，那么下次就只能取剩下硬币数量为1+n/3的部分再进行称量；
三、当n=5、8时，称量硬币的分配为（1，2，2）、（2，3，3）
2和2比较，3和3比较，重量相等和不相等，下次比较的硬币数量是不一样的，而我们要从中考虑最坏的情况，那么只能假设重量不相等，因为1+n/3大于n/3，那么下次就只能取硬币数量为1+n/3的部分再进行称量；

7.源代码：

#include<stdio.h>
int main()
{
	int n;
	while(scanf("%d",&n)!=-1&&n)
	{
		int count=0;
		while(n>1)
		{
			if(n%3==0)
				n=n/3;
			else
				n=n/3+1;
			count++;
		}
		printf("%d\n",count);
	}
	return 0;
}