AI题库 · 信息学奥赛-入门级题库
题目分享 #22092
精明与糊涂
有N个人,分为两类:①精明人:永远能正确判断其他人是精明还是糊涂;②糊涂人:判断不可靠,会给出随机的判断。已知精明人严格占据多数,即如果精明人有k个,则满足k>N/2
你只能通过函数query(;j)让第i个人判断第j个人:返回true表示判断结果为“精明人”;返回false表示判断结果为“糊涂人”。目标是通过互相判断,找出至少一个百分之百能确定的精明人(无需关心query(i,j)的内部实现)。
以下程序利用“精明人占多数”的优势,通过“消除”过程让人们互相判断并抵消.经过若干轮抵消后,最终留下的候选者必然属于多数派,即精明人。
例如,假设有三个人0、1、2。如果0说1是糊涂人,而1也说0是糊涂人,则O和1至少有一个是糊涂人。程序将同时淘汰0和1。由千三人里至少有两个精明人,我们确定2是精明人。试补全程序。
#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;
}
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。