关于《ACM/ICPC算法基础训练教程》这本书的一些解释与自我理解
1.2枚举法
1.2.1基本概念
在某些问题中,问题的解被限制在一个有限的范围内,此类问题只需要按照题目的限定,逐一判断这些可能的解是否符合题目的要求,这种方法称为枚举。
枚举算法需要注育两个方面:
一方面,不重、不漏地描述用来限定问题的解的范围,重复了必定会降低效率遗漏了则表示不全面,有可能会找不到问题的解;
另一方面,等价地表示问题对解的要求对于一个元素,如果它是问题的解则判断程序给出“是”的回答,如果判断程序给出“是”的回答则它是问题的解.
1.2.2例题讲解
【例 1-4】 猜数字,
题目描述:
游戏的规则如下:计算机随机产生一个4位数,然后玩家猜这个4位数是什么。每猜一个数,计算机都会告诉玩家猜对几个数字,其中有几个数字在正确的位置上。输人数据有多组。每组的第一行为一个正整数N(1≤N<100),表示在这段对话中共有N次问答。在接下来的N行中,每行三个整数A、B、C。gameboy猜这个4位数A,然后计算机回答猜对了B个数字,其中C个在正确的位置上。当N=0时,则输入类据结束。
如果根据这段对话能确定这个4位数,则输出该4位数;若不能确定,则输出“Not sure"。
输入样例:
6
4815 2 1
5716 1 0
7842 1 0
4901 0 0
8585 3 3
8555 3 2
2
4815 0 0
2999 3 3
0
输出样例:
3585
Not sure
题目来源:
HDU 1172,1wg
http://acm.hdu.edu.cn/showproblem.php?pid=1172
代码示例:
#include<iostream>
#include<algorithm>
using namespace std;
//第i次回答gameboy猜这个数为a[i],猜对了b[i]个数,其中c[i]个在正确的位置上
int n, a[101], b[101], c[101];
int ans, num;
bool check(int x, int y) {
//4位数x是否符合第y次问答的结果
int s[4], t[4], pa = a[y], pb = b[y] ,pc = c[y];
for (int i = 3; i >= 0; i--) {
s[i] = x % 10, x /= 10, t[i] = pa % 10, pa /= 10;
}
//检查猜对的数字个数和在正确位置上的个数是否符合
int corret_num = 0, correct_pos = 0;
for (int i = 0; i < 4; i++)
if (s[i] == t[i]) correct_pos++;//正确位置上的个数
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (t[j] == s[i]) {
corret_num++;
t[j]=-1;
break;
}
return corret_num == pb && correct_pos == pc;
}
int main() {
while (cin >> n && n) {
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i] >> c[i];
num = 0;
for (int i = 1000; i < 10000 && num < 2; i++) {
int j = 0;
for (; j < n; j++) {
if (!check(i, j)) {
break;
}
if (j == n)num++, ans = i;
}
}
if (num == 1) cout << ans << endl;
else cout << "Not sure" << endl;
}
return 0;
}
标签:10,1.2,int,ACM,ICPC,++,基础训练,num,位数
From: https://blog.csdn.net/FGGFFoj/article/details/140260422