[数据结构与算法]一、枚举法（来自郭炜老师的慕课）

1.大体思想：对某一类事情的所有情况进行逐一枚举，并逐一进行检验是否满足条件，这种思想叫做枚举思想。

2.采用枚举法解决问题要注意的三个方面：

a.建立简洁的数学模型；

b.减少搜索的空间；

c.采用合适的搜索顺序。

3.老师的例题：

熄灯问题：（先上代码）

# include<iostream>
# include<string>
# include<cstring>
using namespace std;

char orilight[5];//灯泡的原始状态
char light[5];//灯泡的目前状态
char result[5];//结果状态（即开关状态）

int GetBit(char c, int i)//获得字符c的第i个比特
{
	return ((c >> i) & 1);
}

void SetBit(char &c, int i, int s)//把字符c的第i个比特置为s
{
	if (s)
	{
		c |= (1 << i);
	}
	else
	{
		c &= ~(1 << i);
	}
}

void FlipBit(char& c, int i)//对字符c的第i个比特取反
{
	c ^= (1 << i);
}

void OutPut(char result[])
{
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			cout << GetBit(result[i], j);
			if (j < 5)
			{
				cout << " ";
			}
		}
			cout << endl;
	}
}

int main()
{
	int s;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			cin >> s;
			SetBit(orilight[i], j, s);
		}
	}
	for (int n = 0; n < 64; n++)//第一行有6个位置的01对应0到63个二进制数
	{
		int switchs = n;//每一行开关的状态
		memcpy(light, orilight, sizeof(orilight));
		for (int i = 0; i < 5; i++)
		{
			result[i] = switchs;//每次循环确定一个开关的状态
			for (int j = 0; j < 6; j++)
			{
				//通过开关控制当前行的灯光
				if (GetBit(switchs, j))
				{
					if (j > 0)
					{
						FlipBit(light[i], j - 1);
					}
					if (j < 5)
					{
						FlipBit(light[i], j + 1);
					}
					FlipBit(light[i], j);
				}
			}
			if (i < 4)
			{
				light[i + 1] ^= switchs;
			}
			switchs = light[i];
		}
		if (light[4] == 0)
			OutPut(result);
	}
	return 0.;
}

解题思路：只需要枚举第一行的开关即可，第一行的开关确定第二行的开关也就确定了，第一行一共6个开关，用0~63的6个二进制位表示第一行按钮的开关状态。每行有6个开关按钮，用6个二进制位表示即可，选用1个字节（8个二进制位）的字符类型，每一位表示一个开关按钮的状态。因此第一行确定以后，由第一行还未熄灭的灯光确定第二行按钮的开关状态，以此类推，看最后一排的灯光是否全部熄灭，如果熄灭则满足条件。
这个例题用到了位运算，后面的练习题中也会用到。通过位运算降低了时空复杂度，因此除了学会枚举思想，学会利用位运算简化操作也是一种需要我们学习的重要手段。
4、课后练习题：
a.
特殊密码锁

# include<iostream>
# include<string>
# include<cstring>
using namespace std;

int OriLock;//原始锁的状态
int NowLock;//现在锁的状态
int ResultLock;//锁要达到的状态

int GetBit(int l, int i)//得到l的第i个比特
{
	return (1 & (l >> i));
}

void SetBit(int& l, int i, int s)//把l的第i位置为s
{
	if (s)
	{
		l |= (1 << i);
	}
	else
	{
		l &= ~(1 << i);
	}
}

void FlipBit(int& l, int i)//翻转第i个比特位
{
	l ^= (1 << i);
}

int main()
{
	char c;
	int i = 0;
	while ((c = getchar()) != '\n')
	{
		if (c == '1')
		{
			SetBit(OriLock, i, 1);
			i++;
		}
		else
		{
			SetBit(OriLock, i, 0);
			i++;
		}
	}
	i = 0;
	while ((c = getchar()) != '\n')
	{
		if (c == '1')
		{
			SetBit(ResultLock, i, 1);
			i++;
		}
		else
		{
			SetBit(ResultLock, i, 0);
			i++;
		}
	}
	int sum1 = 0,sum=32;
	for (int k = 0; k < 2; k++)
	{
		sum1 = 1;
		memcpy(&NowLock, &OriLock, sizeof(OriLock));
		if (k == 0)
		{
			FlipBit(NowLock, 0);
			FlipBit(NowLock, 1);
		}
			for (int j = 0; j < i-1; j++)
			{
				if (GetBit(NowLock, j) != GetBit(ResultLock, j))
				{
					sum1++;
					FlipBit(NowLock, j);
					FlipBit(NowLock, j + 1);
					if (j < i - 2)
						FlipBit(NowLock, j + 2);
				}
			}
			if (sum > sum1 && NowLock == ResultLock)
				sum = sum1;
	}
	if (sum==32)
		cout << "impossible";
	else
		cout << sum;
	return 0;
}

同样是采用位运算的操作，注意到题干描述n<30，整型变量可以满足条件（4个字节就是32位）。
这里只需要枚举第一个开关的状态即可，第一个开关按钮按下或者是不按，因为第一个开关确定后第二个开关也随之确定了。
b.拨钟问题

# include<iostream>
using namespace std;

int main()
{
	int clock[9];
	for (int i = 0; i < 9; i++)
	{
		cin >> clock[i];
	}
	int oper[9];
	for(oper[0]=0;oper[0]<4;oper[0]++)
		for (oper[1] = 0; oper[1] < 4; oper[1]++)
			for (oper[2] = 0; oper[2] < 4; oper[2]++)
				for (oper[3] = 0; oper[3] < 4; oper[3]++)
					for (oper[4] = 0; oper[4] < 4; oper[4]++)
						for (oper[5] = 0; oper[5] < 4; oper[5]++)
							for (oper[6] = 0; oper[6] < 4; oper[6]++)
								for (oper[7] = 0; oper[7] < 4; oper[7]++)
									for (oper[8] = 0; oper[8] < 4; oper[8]++)
									{
										int result = 0;
										result += (clock[0] + oper[0] + oper[1] + oper[3]) % 4;
										result += (clock[1] + oper[0] + oper[1] + oper[2] + oper[4]) % 4;
										result += (clock[2] + oper[1] + oper[2] + oper[5]) % 4;
										result += (clock[3] + oper[0] + oper[3] + oper[4] + oper[6]) % 4;
										result += (clock[4] + oper[0] + oper[2] + oper[4] + oper[6] + oper[8])%4;
										result += (clock[5] + oper[2] + oper[4] + oper[5] + oper[8])%4;
										result += (clock[6] + oper[3] + oper[6] + oper[7]) % 4;
										result += (clock[7] + oper[4] + oper[6] + oper[7] + oper[8]) % 4;
										result += (clock[8] + oper[5] + oper[7] + oper[8]) % 4;
										if (result == 0)
										{
											for (int i = 0; i < 9; i++)
											{
												while (oper[i] != 0)
												{
													cout << i + 1 << " ";
													oper[i]--;
												}
											}
											return 0;
										}
									}
}

注意到钟只有四个状态，因此每个操作执行四次相当于不执行，并且操作执行的顺序不影响最后结果。枚举每个操作的执行次数即可。