【例83.3】假币问题

解题思路

已知假币偏轻，每称一次最多三种结果，可把候选分成三组排除到其中一组。k次最多区分3^k枚，因此求最小k使3^k≥n。

正确性说明

每次天平结果最多提供三分支，所以3^k≥n是必要条件。把候选尽量均分、称两组，倾斜选轻组、平衡选剩余，可递归达到该信息上界。

易错点

n=1不需称；0终止不输出。

复杂度

每组时间O(log n)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    while (cin >> n && n) {
        long long capacity = 1;
        int k = 0;
        while (capacity < n) {
            capacity *= 3;
            k++;
        }
        cout << k << "\n";
    }
    return 0;
}