有假币(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;
}