ACM/ICPC算法基础训练教程（2）

关于《ACM/ICPC算法基础训练教程》这本书的一些解释与自我理解

• 1.2枚举法
• • 1.2.1基本概念
  • 1.2.2例题讲解

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;
}