← 查看本卷题目
组合题5 个小题
已作答 0 / 5

(2)(精明与糊涂)有 NN 个人,分为两类: i) 精明人:永远能正确判断其他人是精明还是糊涂; ii)糊涂人:判断不可靠,会给出随机的判断。

已知精明人严格占据多数,即如果精明人有 kk 个,则满足 k>N/2k > N/2。

你只能通过函数 query(i,j)\text{query}(i, j) 让第 ii 个人判断第 jj 个人:返回 true\text{true} 表示判断结果为“精明人”;返回 false\text{false} 表示判断结果为“糊涂人”。你的目标是,通过这些互相判断,找出至少一个百分之百确定的精明人。同时,你无需关心 query(i,j)\text{query}(i, j) 的内部实现。

以下程序利用“精明人占多数”的优势。设想一个“消除”的过程,让人们互相判断并进行抵消。经过若干轮抵消后,最终留下的候选人必然属于多数派,即精明人。

例如,假设有三人 0,1,20, 1, 2。如果 00 说 11 是糊涂人,而 11 也说 00 是糊涂人,则 00 和 11 至少有一个是糊涂人。程序将同时淘汰 00 和 11。由于三人里至少有两个精明人,我们确定 22 是精明人。

试补全程序。

#include <iostream>#include <vector>using namespace std; int N;bool query(int i, int j); int main() {    cin >> N;     int candidate = 0;    int count = __①__;    for (int i = 1; i < N; ++i) {        if (__②__) {            candidate = i;            count = 1;        } else {            if (__③__) {                __④__;            } else {            count++;            }        }    }    cout << __⑤__ << endl;    return 0;}
第 39 题单选题原卷 3 分

②处应填( )

填写答案