组合题5 个小题
已作答 0 / 5
(2)(精明与糊涂)有 N 个人,分为两类: i) 精明人:永远能正确判断其他人是精明还是糊涂; ii)糊涂人:判断不可靠,会给出随机的判断。
已知精明人严格占据多数,即如果精明人有 k 个,则满足 k>N/2。
你只能通过函数 query(i,j) 让第 i 个人判断第 j 个人:返回 true 表示判断结果为“精明人”;返回 false 表示判断结果为“糊涂人”。你的目标是,通过这些互相判断,找出至少一个百分之百确定的精明人。同时,你无需关心 query(i,j) 的内部实现。
以下程序利用“精明人占多数”的优势。设想一个“消除”的过程,让人们互相判断并进行抵消。经过若干轮抵消后,最终留下的候选人必然属于多数派,即精明人。
例如,假设有三人 0,1,2。如果 0 说 1 是糊涂人,而 1 也说 0 是糊涂人,则 0 和 1 至少有一个是糊涂人。程序将同时淘汰 0 和 1。由于三人里至少有两个精明人,我们确定 2 是精明人。
试补全程序。
1#include <iostream>2#include <vector>3using namespace std;4 5int N;6bool query(int i, int j);7 8int main() {9 cin >> N;10 11 int candidate = 0;12 int count = __①__;13 for (int i = 1; i < N; ++i) {14 if (__②__) {15 candidate = i;16 count = 1;17 } else {18 if (__③__) {19 __④__;20 } else {21 count++;22 }23 }24 }25 cout << __⑤__ << endl;26 return 0;27}②处应填( )