踩地雷的研究

《踩地雷的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、踩地雷的硏究硏究者：高子婷黃雅婷陳裕美壹、緒論:（-）遊戲規則：在偌大的棋盤中，有許多被覆蓋的格子拼在一起'逐步翻開棋盤，我們必須避免翻開有地雷的格子，而翻開所有非地雷的格子（稱此爲安全格）便是遊戲的最終目的。若不小心翻到有地雷的格子，則算失敗，得重新開始遊戲。如何完成目標呢？我們可以利用打開格子所顯示的訊息，一個格子的訊息可能有2種，（一種爲地雷。（一種爲安全格。格內標有數字M，M代表在被此格子影響的格子（註）中有M個地雷。M又可以分爲J零=〉顯示一個空白格子（簡稱爲空白）（非零=〉以數字1.2.3....M表示註：「被此格子影

2、響的格子」即是一個格子A鄰近的一些格子，在這一些格子皆無地雷存在時，當這些鄰近的格子會因A是否爲地雷而改變其數字'這些格子就稱爲被A影響的格子。數爲而在響的在windows內建的踩地雷遊戲中，一個格子所能影響的格子其左、右、上、下、左上、左下、右上、右下的格子。如圖！最一層外圍的格子，由於其鄰近的格子較中間的少，所以影格子會較少。遊嗽⑼脱明QD1111Awindows踩地雷起始畫面冇數個未開啓的格子。（二）示範遊戲▲任意開啓一個格子5當此格爲非地雷且非零時顯示數字。▲當此格爲零時,程式會幫你開啓至冇數字的範圍。▲當開啓的爲地雷時，

3、遊戲失敗。▲當開啓所冇的非地雷格子後，遊戲成功。护踩地■HBE3理歎©农明QDF跨地雷HHE3遊戲©説明GD▲先在棋盤上任選一格開啓。▲觀察已開啓之訊息，思考下一步該如何走。▲圖中的1周圍八格中已有七格開啓，故未開啓的必爲地雷'以▲再看另外一個1,其右下角已有一地雷，故其周圍未開啓的格脱明01）▲右上角先告一段落。現在看圖中這個1，同前理可知其左上角爲地雷。»歸也HSE3I▲而在另外的1其下方已有一個地雷，同前理可打開其右上右方右下的安全格。(132111.1.1Al1X♦♦”1111111地ttg）脱明（H）子必爲安全格°#踩地

4、晳HBE3»ttQ2)風明(H)12nQni1A22i32222231，又可判斷地雷左邊爲安全格，將其開啓。▲而由新開的1其旁邊已有一個地雷，所以左邊就是安全格。（因碰到空白故電腦自動開啓至有數字的地方）▲按照此原則,打開所有的安全格,便成功了。貳、硏究動機:盛遜及塞鱼遜何者爲地雷呢？可惡，好不容易玩到這裡開金弓竞然無從判斷！！踩地雷一向被視爲益智的動腦遊戲，卻在緊要關JZS13頭失去了動腦的意義，問題在哪裡？想和微軟(microsoft)鬥腦力，找科詔彳出其中的奧秘冷•冷••匕參、硏究目的：利用排列組合與踩地雷的關係，進而設計不

5、需要猜測就能完全解開的踩地雷肆、實驗器材：筆，計算紙，電腦(TurboC++)(MicrosoftVisualBasic)，人腦伍、硏究過程與方法：(一)方法總述1•觀察:問題棋盤(無法推理的棋盤)的地雷排列有無規則？試著觀察幾個：♦剩下地雷數J問題棋盤直觀下，似乎是沒有規則；那如果直接更改棋盤能不能避免猜測？251如右圖，棋盤要怎麼改，綠色箭頭及紫色箭頭才能確定?分析兩者可能情況：1)f(B+f(W=o那剩下的地雷該改放哪呢？放了也不能保證不會出現一樣的狀況(2)f傕)+f隆)=1就是右圖，不能確定誰是地雷(3)f(M)+f(^

6、)=2多需要的地雷該從哪裡移過來？移過來以後會不會換另外一邊不能推理？註：f(x)=x的地雷狀況，f(x)=l-有地雷；f(x)=O—無地雷★棋盤太大且一個格子可影響八格，以至於一次要考慮的因素太多，所以局部的改，很難達成我們的目標，毬否簡化棋盤皮縮小棋盤!尼?2•簡化棋盤&縮小棋盤•(1)1-2先從一維(X軸)開始，一個格子影響左右兩個II□工-oooooieio(2)1-4再加一維(xy軸)，一個格子影響上下左右1(3)1—8最後再回到wiIIdows內建的‘3•歹!/成表:11

7、121111002・01>200100•個格子

8、影響八方在各基層棋盤中，窮舉所有可能的地雷分布，搭配第一步開出的位置，觀察此棋盤是否可全部靠推理解開。表格如下：1—2第一層1個地雷:ABCgooogooog

9、一配合棋盤的所有第一步所有可能的棋盤—「0？u?地雷!•!u•1地雷對稱A•10—A對稱第一個棋盤，故不考慮棋盤配合第一步產生的結果★窮舉第一層的棋盤數日還算小，但是當我們要進行1—2第二層及1—4甚至18各基層時，W南俪找出所有棋盤並扣掉旋轉對稱的重複棋盤呢從-個格子開始，其可以影響的格子及其本身稱爲第一層；而第一層可以影響的格子加上第一層本身稱爲第二層；以此類推。4棋盤

10、的排列:分析各個棋盤扣除旋轉對稱後的情況'並加以列式後，輔助我們寫出電腦程式以窮舉所有的棋盤排列。令(n，k)=第n層取k個地雷扣除旋轉對稱後的組合數(-)1-2n爲層數總棋盤格子數S=2n+11.1-21個地雷(1)觀察：•OOOO0^00000