1.求一个小于N 的最大素数
N- k 是素数的充分必要条件：
N- K 不能被任何一个大于1， 小于N-K 的素数整除
问题的转换
N-K 是否是素数 ----> 小于N-K 的全部素数
枚举解决办法：
2 是素数 ，记为 P0
根据 p0,p1...pk ，寻找比pk大的最小素数p(k+1)
如果p(k+1) 大于N, 则PK 是我们需要找的素数 ，否则， 继续寻找
枚举的本质： 从可能的集合中一一列举各元素。
枚举算法：
对问题可能解集合 的每一项
根据问题给定的检验条件判定哪些是成立的
使条件成立的既是问题的解
枚举的过程：
- 判断猜测的答案是否正确
---》 2是小于N的最大素数吗？
- 进行新的猜测：！！有两个重要的注意因素
- 猜测的结果必须是前面的猜测中没有出现过的， 每次猜测是素数，一定比已经找到的素数大
- 猜测的过程中要及早排除错误的答案 ， 除2以外， 只有奇数才有可能是素数。
### 熄灯问题
1. 问题描述
- 有一个由按钮组成的矩阵， 其中每行有6个按钮，共5行，
- 每个按钮的位置上有一盏灯
- 每按下一个按钮后， 该按钮以及周围的灯会改变一次
- 状态： 熄灭/ 点亮
- ！！特殊情况：
-在矩阵角上的按钮改变3盏灯、
- 矩阵边上的按钮改变4盏灯
- 其他的按钮改变5盏灯
2.题目分析
- 第2次按下同一个按钮时，将抵消第1次按下时产生的结果
- --》 每个按钮最多只需要按一下
- 每个按钮被按下的顺序对最终的结果没影响
- 对第1行中每盏点亮的灯，按下第二行对应的按钮， 就可以熄灭第1行的全部灯
--- 第一种想法：
### 枚举所有可能的按钮状态， 对每个状态计算一下最后灯的情况， 看是否都熄灭
- 每个按钮：０／１
- 一共有３０个开关， 状态数时２＾３０ ，会超时
－－－－－－－－－－－－－－－－－－－－－－－－
如何减少枚举的状态数目？
如果存在某个局部， 一旦这个局部的状态被确定， 那么剩余其他部分的状态只能是确定的一种， 或者不多的ｎ种， 那么只需枚举这个布局的状态即可.
** 第一行是这样一个“局部”
- 因为第一行的各开关状态确定的情况下， 这些开关作用过后， 将导致第一行某些灯是亮着的
- 要熄灭第一行某个亮着的灯， 那么唯一的办法就是按下第二行的灯
--》 为了使第一行的灯全部熄灭，第二行的合理开关状态就是唯一的
--》 第二行开关起作用后， 第三行的开关状态也是唯一的
--》 最后一张的开关也是唯一的
### 只要第一行的状态定下来，定为A 那么剩余行的情况就是确定唯一的
因此， 要推算的是：
最后一行的所有灯起作用后， 最后一行的灯是否都熄灭，
- 如果是， 那么A是一个解的状态
- 如果不是， 那么A 不是解的状态， 第1行换个状态重新尝试
2. 将按钮矩阵的第一行的每个取值看作是一个二进制数
3. 通过实现++ 操作实现
```
press[r+1][c] = (puzzle[r][c] + press[r][c-1] + press[r][c] + press[r][c+1] + press[r-1][c]) % 2;
```
````
#include <stdio.h>
int puzzle[6][8], press[6][8];
bool guess(){
int c,r;
for(r= 1; r< 5; r++)
for(c = 1; c<7; c++)
press[r+1][c] = (puzzle[r][c] + press[r][c-1] + press[r][c] + press[r][c+1] + press[r-1][c]) % 2;
for(c= 1; c<7; c++）
if((press[5][c-1] + press[5][c] + press[5][c+1] + press[4][c] % 2 != puzzle[5][c])// (1,1)⇒ 0, (0,0)⇒ 0
return false;
return true;
}
```
```
void enumerate()
{
int c;
bool success;
for(c = 1; c<7; c++)
press[1][c] = 0;
while (guess() == false){
press[1][1] ++;
c = 1;
//进位操作
while (press[1][c] > 1){
press[1][c] = 0;
c++;
press[1][c] ++;
}
}
return ;
}
```
网友评论