Reference:https://www.icourse163.org/learn/PKU-1001894005?tid=1450413466#/learn/content
基于逐个尝试答案的一种问题求解策略。
使用枚举方法，最好可以通过一些明显的特征，减少枚举数量。
提高枚举效率的方法就是，跳过不必要的测试值。
例如：求小于 N 的最大素数。
找不到一个数学公式，使得根据 N 就可以计算出这个素数，所以只好使用枚举方法。
完美立方
通过条件减小枚举范围。
形如 a3 = b3 + c3 + d3 的等式称为 完美立方等式。
Q：对任给的正整数 N（N<=100），寻找所有的四元组（a、b、c、d），使得 a3 = b3 + c3 + d3 ，其中 a、b、c、d 大于 1，小于等于 N，且 b<=c<=d 。
```C
#include <stdio.h>
#include <Windows.h>
// 微软认为 scanf() 不安全，所以在 VS 中添加以下两条预处理命令，避免因为scanf报错。
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 4996)
int main()
{
int N;
bool flag = false;
printf("please input N(0<N<=100):");
while (true) {
scanf("%d", &N);
if (N > 0 && N <= 100) {
break;
}
}
/* 缩小枚举范围，提高效率
因为 a3 = b3 + c3 + d3
所以 1<b,c,d<a
又因为 1<a,b,c,d<N
所以 1<a<N
*/
for (int a = 2; a <= N; a++) {
for (int b = 2; b < a; b++) {
for (int c = b; c < a; c++) {
for (int d = c; d < a; d++) {
if (a * a * a == b * b * b + c * c * c + d * d * d) {
printf("Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d);
flag = true;
}
}
}
}
}
// 找不到结果时，提示没有符合的数据
if (flag == false) {
printf("未找到符合条件的数据。\n");
}
Sleep(50000);
return 0;
}
```生理周期
逐步查找符合条件的值，跳过不必要的测试值。
人有体力、情商、智商的高峰日子，它们分别每隔23天、28天和33天出现一次。对于每个人，我们想知道何时三个高峰落在同一天。给定三个高峰出现的日子p,e和i（不一定是第一次高峰出现的日子）, 再给定另一个指定的日子d，你的任务是输出日子d之后，下一次三个高峰落在同一天的日 子（用距离d的天数表示）。例如：给定日子为10，下次出现三个高峰同一天的日子是12，则输出2。
Q：输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的日子。d是给定的日子，可能小于p, e或 i。所有给定日子是非负的并且小于或等于365，所求的日子小于或等于21252。
```C
#include <stdio.h>
#include <Windows.h>
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 4996)
int main()
{
int p, e, i, d;
printf("请输入依次输入体力、情感、智力的高峰日和指定的日子（以空格隔开）：");
while (1) {
scanf("%d %d %d %d", &p, &e, &i, &d);
if ((p >= 0 && p <= 365) && (e >= 0 && e <= 365) && (i >= 0 && i <= 365) && (0 <= d && d <= 365)) {
break;
}
}
/* 从d+1天开始，一直试到第21252 天，对其中每个日期k,看是否满足
通过for循环可以跳过不必要的测试值，较快的锁定k的值
*/
int k = d + 1;
// 当第一个for循环结束时，(k-p)%23==0，k代表体力高峰日
for (; (k - p) % 23; k++);
// 当第二个for循环结束时，(k-e)%28==0，k代表情商高峰日，又因为k的步进为23，所以保证了k仍是体力高峰日
for (; (k - e) % 28; k += 23);
// 当第三个for循环结束时，(k-i)%33==0，k代表智商高峰日，又因为k的步进为23*28（23和28的最小公倍数），所以保证了k仍是体力和情商高峰日。至此，k为三个生理周期的高峰日。
for (; (k - i) % 33; k += 23 * 28);
printf("the next triple peak occurs in %d days.", k-d);
Sleep(50000);
return 0;
}
```称硬币（假币问题）
当结果是少数有限种情况时，假设其中一种情况，带入条件进行验证。
有12枚硬币。其中有11枚真币和1枚假币。假币和真币重量不同，但不知道假币比真币轻还是重。
Q：用一架天平称了这些币三次，告诉你称的结果，请你找出假币并且确定假币是轻是重（数据保证一定能找出来）。
```C
#include <stdio.h>
#include <Windows.h>
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 4996)
/* 设三个二维数组，分别用来表示天平左边、右边、结果，三次称量对应的情况。
因为共有12枚硬币，且每次称量两边数量必须一样，所以每边最多能放6个。
*/
char left[3][7];
char right[3][7];
char result[3][7];
// 假设传入的 c 是假币。且 light 为真时，假币较轻；反之，假币较重。
bool isFake(char c, bool light);
int main()
{
printf("请依次输入（大写）左边天平的硬币标号、右边天平的硬币标号、称量结果。\n");
for (int i = 0; i < 3; i++) {
printf("\n第 %d 次称量：", i);
scanf("%s", left[i]);
scanf("%s", right[i]);
scanf("%s", result[i]);
}
for (char c = 'A'; c <= 'L'; c++) {
if (isFake(c, true)) {
printf("%c is the counterfelt coin and it's light.\n", c);
break;
}
else if (isFake(c, false)) {
printf("%c is the counterfelt coin and it's heavy.\n", c);
break;
}
}
Sleep(50000);
return 0;
}
bool isFake(char c, bool light) {
// 将假设带入三次称量结果中进行验证
for (int i = 0; i < 3; i++) {
char* pleft;
char* pright;
if (light) {
pleft = left[i];
pright = right[i];
}
else {
// 当假币较重时，情况相反
pleft = right[i];
pright = left[i];
}
// 假设不成立时返回false
switch (result[i][0]) {
case 'U':
if (strchr(pright, c) == NULL) return false; // C 库函数 char* strchr(const char* str, int c) 在参数 str 所指向的字符串中搜索第一次出现字符 c（一个无符号字符）的位置。
break;
case 'E':
if (strchr(pleft, c) || strchr(pright, c)) return false;
break;
case 'D':
if (strchr(pleft, c == NULL)) return false;
break;
}
}
// 假设成立返回true
return true;
}
```熄灯问题
通过一个有代表性的局部算法，该局部状态一旦确定，其他部分状态也确定，所以枚举该局部的所有状态即可跳过其他部分不必要的测试值。
有一个由按钮组成的矩阵, 其中每行有6个按钮, 共5行。每个按钮的位置上有一盏灯，当按下一个按钮后, 该按钮以及周围位置(上边, 下边, 左边, 右边)的灯都会改变状态（亮--->灭；灭---> 亮）。
Q：给定矩阵中每盏灯的初始状态，求一种按按钮方案，使得所有的灯都熄灭。
分析：同一个按钮按两次会抵消第一次按下的效果，相当于没按，所以，按钮要么按一次，要么不按；
因为每个按钮最多按一次，所以按下按钮的顺序对最终结果没有影响；
锁定局部为第一行，因为要熄灭第一行所有的灯，则第二行只有唯一的按按钮方案；
同理，依次熄灭第一、二、三、四行所有的灯，此时只要最后一行也全部熄灭，则存在满足条件的按钮方案。
这里通过这种方法，可以将枚举数量从 25*6 减小到 26 。
```C
#include <stdio.h>
#include <Windows.h>
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 4996)
int main()
{
int N;
printf("请输入测试次数：");
scanf("%d", &N);
int n = N;
while (N--) {
// 用二维数组表示每盏灯的初始状态。0 表示熄灭；1 表示点亮
int status[5][6];
// 用二维数组表示按钮。0 表示不按的按钮，1 表示按下的按钮。
int button[5][6] = { 0 };
// 某一行按按钮的方案
int switchs[6];
// 存储按过按钮后每盏灯的状态
int lights[5][6];
printf("\n请输入第 %d 次测试的数据。\n", n-N);
// 接收测试灯的初始状态
for (int i = 0; i < 5; i++) {
printf("第 %d 行灯的初始状态(以空格隔开)：", i+1);
scanf("%d %d %d %d %d %d", &status[i][0], &status[i][1], &status[i][2], &status[i][3], &status[i][4], &status[i][5]);
lights[i][0] = status[i][0];
lights[i][1] = status[i][1];
lights[i][2] = status[i][2];
lights[i][3] = status[i][3];
lights[i][4] = status[i][4];
lights[i][5] = status[i][5];
}
// 对第一行灯的按按钮方案进行枚举
for (int k = 0; k < 2 * 2 * 2 * 2 * 2 * 2; k++) {
// 将 k 分解为二进制赋给 switchs
switchs[0] = (k>=32 ? 1 : 0);
switchs[1] = (k%32>=16 ? 1 : 0);
switchs[2] = (k%16>=8 ? 1 : 0);
switchs[3] = (k%8>=4 ? 1 : 0);
switchs[4] = (k%4>=2 ? 1 : 0);
switchs[5] = (k%2==1 ? 1 : 0);
for (int i = 0; i < 5; i++) {
if (i > 0) {
for (int j = 0; j < 6; j++) {
// 上一行灯的状态决定了本行要按的按钮
switchs[j] = lights[i-1][j];
}
}
for (int j = 0; j < 6; j++) {
if (switchs[j] == 1) {
button[i][j] = 1; // 按过的按钮存入button
lights[i][j] = lights[i][j] == 1 ? 0 : 1; // 更改本位的灯的状态
// 更改上下两行的灯的状态
if (i > 0) {
lights[i - 1][j] = lights[i - 1][j] == 1 ? 0 : 1;
}
if (i < 4) {
lights[i + 1][j] = lights[i + 1][j] == 1 ? 0 : 1;
}
// 更改左右两边的灯的状态
if (j > 0) {
lights[i][j - 1] = lights[i][j - 1] == 1 ? 0 : 1;
}
if (j < 5) {
lights[i][j + 1] = lights[i][j + 1] == 1 ? 0 : 1;
}
}
}
}
if (lights[4][0] + lights[4][1] + lights[4][2] + lights[4][3] + lights[4][4] + lights[4][5] == 0) {
printf("PUZZLE # %d\n", n-N);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 6; j++) {
printf("%d ", button[i][j]);
}
printf("\n");
}
break;
}
else {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 6; j++) {
button[i][j] = 0;
lights[i][j] = status[i][j];
}
}
}
}
}
Sleep(50000);
return 0;
}
```上述算法已经可以实现题目的要求，但是使用 int 类型的二维数组来实现太过浪费内存。
在 64位 计算机中，一个 int 类型的变量占用 4Byte 空间，可以通过 short、 char 等占用空间更小的类型来实现上述算法。
在本题中，灯只有两种状态：亮、灭；按钮一直有两种状态：按、不按。所以更节约内存的方法是，直接使用 bit 位来表示灯或按钮。
```C
#include <stdio.h>
#include <iostream>
#include <Windows.h>
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 4996)
int getBit(char c, int i) {
return (c >> i) & 1;
}
void setBit(char& c, int i, int v) {
if (v) {
c |= (1 << i); // 设 1 时，其余位与 0 相或，保证其余位不变
}
else {
c &= ~(1 << i); // 设 0 时，其余位与 1 相与，保证其余位不变
}
}
void flip(char& c, int i) {
c ^= (1 << i); // 取反时，其余位与 0 异或，保证其余位不变，与 1 异或则取反。这里表示改变灯的状态
}
int main()
{
int N;
printf("请输入测试次数：");
scanf("%d", &N);
int n = N;
while (N--) {
// 用char类型的一维数组中的比特位表示每盏灯的初始状态。0 表示熄灭；1 表示点亮
char status[5];
// 用char类型的一维数组表示按钮。0 表示不按的按钮，1 表示按下的按钮。
char button[5] = { 0 };
// 某一行按按钮的方案
char switchs;
// 存储按过按钮后每盏灯的状态
char lights[5];
// 将灯的状态全部初始化为 0 ，切记一定要初始化。否则，char数组未赋值前，系统会令数组指针随机的指向任意一块可利用的地址。而这块地址可能存有失效的数据，导致最后 lights[4] 无法等于 0。
memset(status, 0, sizeof(status));
// C 库函数 void *memset(void *str, int c, size_t n) 复制字符 c（一个无符号字符）到参数 str 所指向的字符串的前 n 个字符。
printf("请输入第 %d 次测试的数据。\n", n-N);
// 接收测试灯的初始状态
for (int i = 0; i < 5; i++) {
printf("第 %d 行灯的初始状态(以空格隔开)：", i+1);
int k;
for (int j = 0; j < 6; j++) {
//scanf("%d ", &k); 使用 scanf 函数时，可能第一次输入的值无法读入
std::cin >> k;
setBit(status[i], j, k);
printf("%d %d\n",i,j);
}
lights[i] = status[i];
}
// 对第一行灯的按按钮方案进行枚举
for (int k = 0; k < 2 * 2 * 2 * 2 * 2 * 2; k++) {
switchs = k;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 6; j++) {
if (getBit(switchs,j)) {
setBit(button[i],j, 1); // 按过的按钮存入button
flip(lights[i], j); // 更改本位的灯的状态
// 更改上下两行的灯的状态
if (i > 0) {
flip(lights[i-1], j);
}
if (i < 4) {
flip(lights[i+1], j);
}
// 更改左右两边的灯的状态
if (j > 0) {
flip(lights[i], j-1);
}
if (j < 5) {
flip(lights[i], j+1);
}
}
}
// 第二行开始，本行灯的状态决定了下一行要按的按钮
switchs = lights[i];
}
if (lights[4] == 0) {
printf("PUZZLE # %d\n", n-N);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 6; j++) {
printf("%d ", getBit(button[i], j));
}
printf("\n");
}
break;
}
else {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 6; j++) {
setBit(button[i],j,0);
setBit(lights[i],j, getBit(status[i],j));
}
}
}
}
}
Sleep(50000);
return 0;
}
```
京公网安备 11010502036488号