1.求一個(gè)小于N 的最大素?cái)?shù)
N- k 是素?cái)?shù)的充分必要條件：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? N- K 不能被任何一個(gè)大于1尚蝌， 小于N-K 的素?cái)?shù)整除
問(wèn)題的轉(zhuǎn)換
? ? ? ? ? ? ? ? ? ? ? ? ? ? N-K 是否是素?cái)?shù) ----> 小于N-K 的全部素?cái)?shù)
枚舉解決辦法：
? ? ? 2? 是素?cái)?shù) ，記為 P0
? ? ? ? 根據(jù) p0,p1...pk 乱投，尋找比pk大的最小素?cái)?shù)p(k+1)
? ? ? ? 如果p(k+1) 大于N, 則PK 是我們需要找的素?cái)?shù) 代虾，否則， 繼續(xù)尋找
枚舉的本質(zhì)： 從可能的集合中一一列舉各元素炕柔。
枚舉算法：
對(duì)問(wèn)題可能解集合 的每一項(xiàng)
? ? ? ? ? ? ? ? ? ? ? ? 根據(jù)問(wèn)題給定的檢驗(yàn)條件判定哪些是成立的
? ? ? ? ? ? ? ? ? ? ? ? 使條件成立的既是問(wèn)題的解
枚舉的過(guò)程：
- 判斷猜測(cè)的答案是否正確
---》 2是小于N的最大素?cái)?shù)嗎皿曲？
- 進(jìn)行新的猜測(cè)：Ｄσ伞！有兩個(gè)重要的注意因素
? ? ? ? ? ? ? ? ? ? -? 猜測(cè)的結(jié)果必須是前面的猜測(cè)中沒(méi)有出現(xiàn)過(guò)的鞋怀， 每次猜測(cè)是素?cái)?shù)双泪，一定比已經(jīng)找到的素?cái)?shù)大
? ? ? ? ? ? ? ? ? - 猜測(cè)的過(guò)程中要及早排除錯(cuò)誤的答案 ， 除2以外密似， 只有奇數(shù)才有可能是素?cái)?shù)焙矛。
### 熄燈問(wèn)題
1. 問(wèn)題描述
- 有一個(gè)由按鈕組成的矩陣， 其中每行有6個(gè)按鈕残腌，共5行村斟，
- 每個(gè)按鈕的位置上有一盞燈
- 每按下一個(gè)按鈕后贫导， 該按鈕以及周?chē)臒魰?huì)改變一次
- 狀態(tài)： 熄滅/ 點(diǎn)亮
- ！蟆盹！特殊情況：
? ? ? ? ? ? ? ? ? ? ? -在矩陣角上的按鈕改變3盞燈孩灯、
? ? ? ? ? ? ? ? ? ? ? - 矩陣邊上的按鈕改變4盞燈
? ? ? ? ? ? ? ? ? ? ? - 其他的按鈕改變5盞燈
2.題目分析
- 第2次按下同一個(gè)按鈕時(shí)，將抵消第1次按下時(shí)產(chǎn)生的結(jié)果
- --》 每個(gè)按鈕最多只需要按一下
-? 每個(gè)按鈕被按下的順序?qū)ψ罱K的結(jié)果沒(méi)影響
- 對(duì)第1行中每盞點(diǎn)亮的燈逾滥，按下第二行對(duì)應(yīng)的按鈕峰档， 就可以熄滅第1行的全部燈
--- 第一種想法：
### 枚舉所有可能的按鈕狀態(tài)， 對(duì)每個(gè)狀態(tài)計(jì)算一下最后燈的情況寨昙， 看是否都熄滅
- 每個(gè)按鈕：０／１
- 一共有３０個(gè)開(kāi)關(guān)讥巡， 狀態(tài)數(shù)時(shí)２＾３０ ，會(huì)超時(shí)
－－－－－－－－－－－－－－－－－－－－－－－－
如何減少枚舉的狀態(tài)數(shù)目舔哪？
如果存在某個(gè)局部欢顷， 一旦這個(gè)局部的狀態(tài)被確定， 那么剩余其他部分的狀態(tài)只能是確定的一種捉蚤， 或者不多的ｎ種吱涉， 那么只需枚舉這個(gè)布局的狀態(tài)即可.
** 第一行是這樣一個(gè)“局部”
- 因?yàn)榈谝恍械母鏖_(kāi)關(guān)狀態(tài)確定的情況下， 這些開(kāi)關(guān)作用過(guò)后外里， 將導(dǎo)致第一行某些燈是亮著的
- 要熄滅第一行某個(gè)亮著的燈， 那么唯一的辦法就是按下第二行的燈
--》 為了使第一行的燈全部熄滅特石，第二行的合理開(kāi)關(guān)狀態(tài)就是唯一的
--》 第二行開(kāi)關(guān)起作用后盅蝗， 第三行的開(kāi)關(guān)狀態(tài)也是唯一的
--》 最后一張的開(kāi)關(guān)也是唯一的
### 只要第一行的狀態(tài)定下來(lái)，定為A 那么剩余行的情況就是確定唯一的
因此姆蘸， 要推算的是：
最后一行的所有燈起作用后墩莫， 最后一行的燈是否都熄滅，
- 如果是逞敷， 那么A是一個(gè)解的狀態(tài)
- 如果不是狂秦， 那么A 不是解的狀態(tài)， 第1行換個(gè)狀態(tài)重新嘗試
2. 將按鈕矩陣的第一行的每個(gè)取值看作是一個(gè)二進(jìn)制數(shù)
3. 通過(guò)實(shí)現(xiàn)++ 操作實(shí)現(xiàn)
```
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;
//進(jìn)位操作
while (press[1][c] > 1){
press[1][c] = 0;
c++;
press[1][c] ++;
}
}
return ;
}
```
