枚举

发表于

枚举，基于已有的知识进行答案猜测的一种问题求解策略。
从可能的集合中一一列举各元素，根据已经知道的知识，给一个猜测的答案。

Ex.以找到比N小的最大素数为例

枚举算法

对问题可能解集的每一项根据问题给定的检验条件判定哪些是成立的，使条件成立的即是问题的解。

枚举过程

1, 判断猜测的答案是否正确。（例如，2是小于N的最大素数吗）
2, 进行新的猜测：注意要保证，（1）猜测的结果必须是前面的猜测中没有出现过的。（每次猜测的素数要比之前的要大）（2）猜测的过程中要尽早的排除错误答案。（除2之外，只有奇数才可能是素数。）

所以要考虑到三个关键问题。

1， 给出解空间，建立简洁的数学模型。
2， 减少搜索的空间。 利用知识缩小模型中各个变量的范围。
3， 采用合适的搜索顺序。

先附上之前问题的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//找到小于N的最大素数
//用这种枚举的方法，要比去判断n-1, n-2...是否是质数要快。
int findNum(const int N)
{
	int ret;
	std::vector<int> prim;
	prim.push_back(2);
	bool flag = true; //标识当前的数是否是质数
	for (int i = 3; i < N; i = i + 2/* 排除偶数*/)
	{
		for (int j = 0; j < prim.size() - 1; ++j)
		{
			if (i % prim[j] == 0)
			{
				flag = false;
				break;
			}
		}
		if (flag) prim.push_back(i);//如果当前i是质数，把它Push到质数数组里
		flag = true;
	}
	return prim[prim.size() - 1];
}

例一 熄灯问题

问题描述

有一个由按钮组成的矩阵，其中每行有6个按钮，共5行，每个按钮上有一盏灯。当你按下一个按钮后，该按钮以及其周围上下左右四盏灯都会改变，亮-->暗或者暗-->亮。
要求对矩阵中的每盏灯设置一个初始状态，请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。

ji
如果穷举所有的状态，即为2^(56)种，肯定是不现实的。
*那么此时穷举的技巧是，如果存在某个局部，一旦这个局部的状态被确定，那么剩余其他部分的状态只能是确定的一种，或者不多的n种，那么就只需要枚举这个局部的状态就可以。
本题是有这样的“局部”的，当第一行的开关状态确定后，如果要熄灭第一行的所有灯，只能依靠第二行在第一行亮灯的对应位置下Press,故在第一行状态后，第二行的状态实际上已经确定好了；依次类推，第三行第四行…所有有一个思路是枚举第一行的所有的状态，然后判断第五行是否恰好都熄灭。以下是代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//-------------------------------------------------
//**熄灯问题**
//枚举第一行的所有情况 2^6 = 64种。
//对于每一种情况，下面的1-4行结果唯一，最后判断第五行是否正好都别熄灭，若是，则得到正确解。
int press[6][8], puzzle[6][8];
bool guess()
{
	for (int i = 1; i < 7; ++i)
	{
		for (int j = 0; j < 5; ++j)
		{
			//根据Press第一行和puzzle数组，计算press其它行的值
			press[i + 1][j] = (puzzle[i][j] + press[i - 1][j] + press[i][j] + press[i][j + 1] + press[i][j - 1]) % 2;
		}
	}
	for (int i = 1; i < 7; ++i)
	{
		//判断所计算的press数组能否熄灭第五行的所有灯
		if ((puzzle[5][i] + press[5][i] + press[5][i - 1] + press[5][i + 1]) % 2 == 1)
			return false;
	}
	return true;
}
void enumerate()
{
	int c;
	for (c = 1; c < 7; ++c)
	{
		press[1][c] = 0;
	}
	while (!guess())
	{
		//对press第一行的元素的各种取值进行枚举，依次考虑
		c = 1;
		press[1][c]++;
		//累加进位
		while (press[1][c] > 1)
		{
			press[1][c] = 0;
			c++;
			press[1][c] += 1;
		}
	}
	
	return;
}
int main(int argc, char** argv)
{
	int cases, i, r, c;
	scanf("%d", &cases); 
	//将扩大的矩阵的边缘用0填充
	for (r = 0; r < 6; r++)
	{
		press[r][0] = 0;
		press[r][7] = 0;
	}
	for (c = 0; c < 8; c++)
	{
		press[0][c] = 0;
	}
	for (i = 0; i < cases; ++i)
	{
		for (r = 1; r < 6; ++r)
		{
			for (c = 1; c < 7; ++c)
			{
				scanf("%d", &puzzle[r][c]);
			}
		}
		enumerate();
		
		printf("PUZZLE# %d\n", i + 1);
		for (r = 1; r < 6; ++r)
		{
			for (c = 1; c < 7; ++c)
			{
				printf("%d ", press[r][c]);
			}
			printf("\n");
		}
	}
	return 0;
	
	
}

讨厌的青蛙

问题描述
有一种青蛙，会跳跃稻田，从而踩踏稻子。青蛙总是沿着一条直线跳跃稻田，并且每次跳跃的距离都相同。（可竖直也可倾斜）。来看看标准输入输出。



那么，我们枚举的是什么？肯定不能枚举所有可能出现的情况。
我们知道，两点确定一条直线，所以基本思路就是枚举第一个点和第二个点。
先直接粘贴代码，注释中有比较详细的思路。总结在之后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
//-------------------------------------------------
//**讨厌的青蛙**
//定义了一个结构体用于描述踩踏水稻的横纵坐标
struct Plant
{
	int x;
	int y;
};
Plant plants[5000];
int r, c, n;
//申请一个动态的空间来存放稻田是否被踩踏
int **field;
int searchPath(int dx, int dy, Plant p)
{
	int step = 1;
	int x = p.x;
	int y = p.y;
	while (x >= 1 && x <= c && y >= 1 && y <= r)
	{
		step++;
		//这一步也可以用二叉查找来找plants里面有没有x, y相对应的点
		if(field[x][y] != 1 /* std::!binary_search(plants, plants + n, plants)*/) return 0;
		x += dx;
		y += dy;
	}
	return step;
}
void input()
{
	scanf("%d %d %d", &r, &c, &n);
	field = new int*[r + 1];
	for (int i = 0; i < r + 1; ++i)
	{
		field[i] = new int[c + 1];
	}
	//先初始化其为0
	for (int i = 1; i < r + 1; ++i)
	{
		for (int j = 1; j < c + 1; ++j)
		{
			field[i][j] = 0;
		}
	}
	for (int i = 0; i < n; ++i)
	{
		scanf("%d %d", &plants[i].x, &plants[i].y);
		field[plants[i].x][plants[i].y] = 1;
	}
	for (int i = 1; i < r + 1; ++i)
	{
		for (int j = 1; j < c + 1; ++j)
		{
			printf("%d ", field[i][j]);
		}
		printf("\n");
	}
}
int hatingFlog()
{
	int dx, dy;
	int max = 2;
	int tmpStep;
	input();
	std::sort(plants, plants + n);
	for (int i = 0; i < n - 1; ++i)
	{
		for (int j = i + 1; j < n; ++j)
		{
			dx = plants[j].x - plants[i].x;
			dy = plants[j].y - plants[i].y;
			//如果第一个点的前一个点还在field内，则肯定不是最优答案的起点，换第二个点。
			if (plants[i].x - dx >= 1 && plants[i].x - dx <= c && plants[i].y - dy >= 1 && plants[i].y <= r)
				continue;
			//如果第一个点经过比max还小的step就越界了，肯定也不可能满足条件。
			//由于是按x排好序的，再往后换第二个点必然也不满足条件，所以换第一个点。
			if (plants[i].x + dx * (max - 1) > r)
				break;
			//如果y方向过早越界
			if (plants[i].y + dy * (max - 1) > c || plants[i].y + dy * (max - 1) < 1)
				continue;
			//如果三种提前的排除无法排除该店，那么算这条路径的step，看其是否为最大。
			int tmpStep = searchPath(dx, dy, plants[i]);
			if (tmpStep > max) max = tmpStep;
		}
	}
	if (max <= 2) max = 0;
	return max;
}
bool operator < (const Plant& p1, const Plant& p2)
{
	if (p1.x == p2.x) return p1.y < p2.y;
	return p1.x < p2.x;
}

思路值得我们继续巩固的点有：
1，通过思考得到“局部”枚举的方式。
2，对标准库里面函数的运用，sort, 包括binary_search的运用；当然，有很多时候我们对一些复杂的数据结构进行排序时，需要我们自己进行操作符重载。