PAT乙级(Basic Level)练习题 有假币
题目描述
居然有假币！ 现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。nowcoder这就去买猪肉，结果找来的零钱中有假币！！！可惜nowcoder一不小心把它混进了一堆真币里面去了。只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），请用最快的时间把那个可恶的假币找出来。
输入描述:
1≤n≤2^30,输入0结束程序。
输出描述:
最多要称几次一定能把那个假币找出来？
输入例子:
3
12
0
输出例子:
1
3
解题思路：\color{blue}解题思路：解题思路：
一看到这道题，我首先想到的是一个猜数游戏，就是随机生成[1,1000]之间的一个数，你每次报出一个猜想值，只告诉你你猜的数是比随机数大还是小，每次根据反馈调整猜的数值，直到猜中为止。玩过的都知道，折半查找是最快的，比如将[1,1000]分为[1,500]、[500,1000]，第一次猜500，如果大了就猜250，否则猜750。这样按照折半的规则猜，最多需要 log2n向上取整 次。
对于这道题，我一开始的思路也是折半查找，把n分成两堆，如果n不是偶数，就分成(n - 1) / 2。但这种思路并不是最优的，无法通过所有测试。
我们首先来看前面几个示例：
当n = 1时，不需要再称了，它就是假币，总共需要0次
当n = 2时，1、1放天平两端，轻的就是假币，总共需要1次
当n = 3时，随机抽出2个放到天平两端，如果天平平衡，则剩下1个就是假币，
否则天平中较轻的是假币，总共需要1次
当n = 4时，分成1、1、2，天平秤1、1，注意题目要求最短时间，
并且是次数最大的情况，也就是我们需要考虑最坏的情况，第一次1、1重量相等，
接着我们把2分开称，总共需要2次
当n = 5时，分成2、2、1，天平秤2、2，同样考虑最坏的情况，2、2重量相等，
接着我们把2分开称，总共需要2次
当n = 6时，分成2、2、2，天平秤2、2，同样考虑最坏的情况，不管如何，还需要
把2分开称，总共需要2次
当n = 7时，分成2、2、3，天平先称2、2，考虑最坏的情况，重量相等，接着我们就需要
按照n = 3的最优情况称，总共需要2次
...
其中有一个规则，我们每次把n分成是3堆，
如果n % 3 == 0,分成 n/3、 n/3、 n/3三堆， 剩下 n/3
如果n % 3 == 1,分成 n/3、 n/3、1 + (n/3)三堆，最坏剩下 1 + (n/3)
如果n % 3 == 2,分成 n/3、 1 + (n/3)、1 + (n/3)三堆，最坏剩下 1 + (n/3)
代码实现：\color{blue}代码实现：代码实现：
#include
using namespace std;
int main() {
int n = 0;
//scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
while (scanf("%d", &n) != - 1) {
if (n == 0) {
break;
}
int count = 0;
while (n > 1) {
count += 1;
//每次取1/3,如果不能整除3，有两种情况
//剩余1个，分成 1/3 、1/3 、1 + (1/3) ，两个1/3放入天平两端，
//剩余2个，分成 1/3 、1 + (1/3) 、 1 + (1/3)，两个1 + (1/3)放入天平两端
//由于题目要求最快的时间，并且是求最多的次数，因此取每次剩余的最大值 1 + (1/3)
n = n / 3 + (n % 3 > 0);
}
printf("%d\n", count);
}
return 0;
}
作者：hestyle
