【每日一题】有假币

文章目录

• 【每日一题】有假币

---

1、题目来源

  牛客网：有假币

---

2、题目描述

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

---

3、输入/输出描述

  输入描述： 1≤n≤2^30，输入0结束程序。
  输出描述： 最多要称几次一定能把那个假币找出来？

---

4、示例

  输入：

3
12
0

  输出：

1
3

---

5、解题思路

  三等分法是最快的方法，将硬币先按数量平均分成3份，任意2份进行称重，对比出3份中最重的一份，然后对最重的那份再次进行称重，直到称重的个数不足2个时（<2）则结束，获得假币。

  如果无法平均分3分则余数要么是1要么是2，因为求得的是最多称几次，n=n/3+1满足每次取硬币数量最多的那份，再将其按数量平均分成3份，取其中两份一样多的过秤，然后把3份中硬币数量最多的那份继续分，直到硬币剩余0或1则结束，获得假币。

---

6、代码展示

#include<iostream>
using namespace std;
int main()
{
    int n;
    int ret;
    while(cin>>n)
    {
        if(n==0)
            break;
        ret=0;
        while(n>=2)
        {
            if(n%3)          
                n=n/3+1; //不可以整除则取最多的那份，是n/3+1
            else 
                n/=3;//可以整除再直接整除，能够获取到最重的一份
            ret++;
        }
        cout<<ret<<endl;
    }
    return 0;
}

---

7、推荐文章

  【思维与逻辑】快速测出假硬币