設計點燈游戲前的總結

因c語言程序設計實踐課，恰好選擇了對點燈游戲的實現(xiàn)，則我們先來歸納如何去求點燈游戲的方案。

零——前置芝士

點燈游戲簡介

一層大樓共有?\(n×n\)?個房間，每個房間都有一盞燈和一個按鈕。按動一個房間的按鈕后，這個房間和周圍四個相鄰的房間的燈的狀態(tài)全部都會改變（由暗變?yōu)榱粱蛘吡磷優(yōu)榘担Ｄ繕耸峭ㄟ^按按鈕把所有的燈都點亮（默認情況下全暗）。

點燈游戲規(guī)律

我們不難發(fā)現(xiàn)以下規(guī)律

\(1.\)按偶數(shù)次按鈕相當于沒有按。

\(2.\)無論按按鈕順序如何結果總是一樣的。

因此我們有以下結論

\(1.\)對于盤面上的每一個按鈕，我們只需要考慮其按開或關的狀態(tài)。

\(2.\)每一個按鈕的狀態(tài)都是互相獨立的，不需要考慮按按鈕的順序。

壹——解決算法

1.完全窮舉法，\(O(2^{n^2})\)

對于每一個按鈕，只有開和關兩種狀態(tài)。

而如果所有按鈕的狀態(tài)確定了，那么燈的狀態(tài)也就確定了。

那么，我們就將點燈的問題轉化為了對按鈕狀態(tài)的統(tǒng)計，只需要將所有按鈕的所有可能的狀態(tài)列舉出來，算出燈所對應的狀態(tài)并判斷燈是否全部點亮即可。

不難發(fā)現(xiàn)，一個按鈕的狀態(tài)有開關?\(2\)?種，因此x個按鈕的狀態(tài)則為?\(2^x\)?種。一個房間共有?\(n×n\)?個按鈕，因此共?\(2^{n×n}\)?種狀態(tài)。復雜度則為?\(O(2^{n^2})\)?。

\[注：此處應為 O(2^{n^2}+n^2)，因為每個燈的計算還需要O(1)，但是n^2遠小于2^{n^2},\\故可忽略不記。
\]

2.首行窮舉法，?\(O(2^n)\)

對于算法1，當?\(n=6\)?時，狀態(tài)已達到?\(2^{36}=68719476736\)?。所以我們要考慮剪枝或者進一步簡化。

比如只按1或2個按鈕的狀態(tài)顯然不成立，可以快速排除。

我們將整個房間的每一排從上到下看作有順序的，那么從第一行開始按按鈕。

假設我們已經(jīng)決定了第一行按鈕的狀態(tài)，此時只有第一行和第二行的燈的狀態(tài)發(fā)生了改變。

由于只有第一行和第二行才會改變第一行燈的狀態(tài)，那么為了使第一行全亮，而且此時第一行按鈕狀態(tài)已確定，我們只能通過改變第二行按鈕的狀態(tài)來使第一行全亮。

同理，為了使第二行全亮，因第二行按鈕已確定，所以要改變第三行按鈕的狀態(tài)，以此類推，整個房間的按鈕都被第一行的按鈕所確定，而房間里除了最后一行也都是全亮的。

因此，我們不需要把房間里所有的按鈕可能的狀態(tài)列出來，只需第一行。對于每一種第一行的狀態(tài)，再按上面的步驟計算后面?\(n-1\)?行的按鈕狀態(tài)，然后判斷最后一行的燈是否全亮即可。

第一行共?\(n\)?個燈，因此共?\(2^n\)?種狀態(tài)。復雜度為?\(O(2^n)\)?。

3.完全方程法，\(O(n^6)\)

雖然算法2已經(jīng)將復雜度降到了?\(O(2^n)\)?，但是當?\(n>30\)?時，這仍是普通計算機無法承受之大。那么我們怎么才能再降一降時間復雜度呢？

在我們從?\(1 \rightarrow 2\)?時，發(fā)現(xiàn)了一行燈的狀態(tài)由它的上一行，這一行和下一行按鈕決定，而不是所有按鈕，是行與行的關系。

這啟發(fā)我們是不是對于同一行的按鈕或者燈的狀態(tài)也能找出來關系呢？

答案是肯定的。我們知道，一個按鈕可以影響它和它周圍4個燈的狀態(tài)，反過來，一個燈的狀態(tài)則由它本身和周圍最多4個按鈕決定的。

\[\color{gold}{——————————奇跡時間到——————————}
\]

我們假設方塊為按鈕，圓圈為燈，黑表示開，白表示關。

再假設一個燈由兩個按鈕決定狀態(tài)，那么具體可以表示為：

\[\Box+\Box= \circ\\
\blacksquare+\Box=\bullet\\
\Box+\blacksquare=\bullet\\
\blacksquare+\blacksquare= \circ
\]

看起來好像可以轉化為數(shù)學式子，假設

\[\Box=0,\blacksquare=1,\circ=1,\bullet=1
\]

那么，上面四個等式可轉化為

\[0+0=0\\
1+0=1\\
0+1=1\\
1+1=0
\]

欸，這個+好像不是加法，而是（邏輯上的）異或運算?\(\oplus\)

現(xiàn)在，把燈轉化為一般情況，那么就由本身以及上下左右四個按鈕來決定燈的狀態(tài)。例如

\[\Box12+\Box21+\Box22+\Box23+\Box32=\circ22
\]

那么，對于房間里所有按鈕和燈，我們可以列出?\(n*n\)?個式子，而且因為我們的目的是將所有燈點亮，那么燈的狀態(tài)應均為?\(\bullet\)?，若此時以按鈕為未知數(shù)，即為?\(n^2\)?元一次方程組。

我們只需要解方程就可以了(????)

說到解方程，大家可能立馬會想到矩陣。沒錯，我們把方程式表示成矩陣的形式，然后對矩陣高斯消元即可。

高斯消元的過程等同于求逆矩陣，而所得的矩陣的每一行就表示需要單獨點亮一個燈，需要按哪些按鈕。

而且可以通過矩陣秩的運算求出多解，這里不過多說明。

高斯消元本身的復雜度是?\(O(n^3)\)?，而矩陣邊長為?\(n^2\)?，所以總時間復雜度為?\(O(n^6)\)?。（成功進入線性時代）

4.首行方程法，?\(O(n^3)\)

如同從1到2，3到4也是實現(xiàn)了由整體到第一行，不再過多說明。

高斯消元復雜度為?\(O(n^3)\)?，由第一行按鈕推算全部的按鈕復雜度為?\(O(n^2)\)?，總體為?\(O(n^3)\)?。

5.n不同時解的數(shù)量

挖個坑，學完線性代數(shù)再回來填。

秩真不明白。

逼零集，點燈游戲和解線性方程組 - 知乎 (zhihu.com)

貳——點燈游戲代碼的實現(xiàn)

此處代碼并非只是方案實現(xiàn)的代碼，也要實現(xiàn)程序設計課程的要求以及程序的美觀。

（下周這個時候不見不散。）

鏈接：https://www.dianjilingqu.com/628031.html