點燈遊戲

點燈遊戲

點燈遊戲是一個十分有趣的智力遊戲:有一行N行N列的燈,開始時全部是滅的,當你點擊其中一盞燈時他的上下左右(若存在的話)狀態全部改變,現在要求你在限定的時間內以最少地步數,將全部的燈點亮。

基本介紹

  • 中文名:點燈遊戲
  • 遊戲類型:智力遊戲
  • 遊戲要求:將全部的燈點亮
  • 遊戲勝利:當25個格子全變成黑色時
遊戲介紹,遊戲規則,遊戲程式,改進算法,

遊戲介紹

點燈遊戲是這樣的,例如一開始有5×5共25盞燈,都處於關的狀態,現在要想辦法把25盞燈全打開,每次只能開/關一盞燈,但由於電路原因,和它相鄰的四盞燈也會改變開/關狀態,於是想把25盞燈全打開就有一定難度。
遊戲效果如圖4.1所示,一開始有25個格子,全是白色,點擊一個格子,它和周圍四個格子的顏色都會由白變黑或由黑變白。當25個格子全變成黑色時,遊戲勝利。
圖4.1圖4.1

遊戲規則

現在,我們以某一盞燈為研究對象,顯然,當此燈狀態被改變奇數次後,燈被點亮.反之,被點擊偶數次,
燈則維持原來的熄滅狀態不變.而促使燈狀態改變的事件不外乎其上下左右(若存在的話)被點擊.
推而廣之,只要所有的燈狀態被改變奇數次,則可保證所有的燈全部被點亮.同時,應該,說明的是,
對每一盞燈來說,自身被點次奇數數與一次效果相同,這是因為,對每盞燈來說,被點一次後,再點偶數次,
自身他的上下左右(若存在的話)狀態恢復原態.同樣道理,自身被點偶數次,相當於沒被點.故在最少步數
的限制下,每盞燈要么沒被點,要么僅被點一次.
點燈遊戲

遊戲程式

我們很容易想到,可以用枚舉的方法來解決問題,以4行4列為例,程式如下:
#include"stdio.h" #include"string.h"
點燈遊戲
#include"stdlib.h"
#include"Conio.h"
main()
{ FILE *fp;
int row=6;
int a[100]=,i,j,m,n,k,s,ss,sum;
clrscr();
for(a[0]=0;a[0]<=1;a[0]++)
for(a[1]=0;a[1]<=1;a[1]++)
for(a[2]=0;a[2]<=1;a[2]++)
for(a[3]=0;a[3]<=1;a[3]++)
for(a[4]=0;a[4]<=1;a[4]++)
for(a[5]=0;a[5]<=1;a[5]++)
.....
for(a[15]=0;a[15]<=1;a[15]++)
{ for(i=0;i<4;i++)
for(j=0;j<4;j++)
{ m=(i-1)>=0?a[(i-1)*4+j]:0;
n=(j-1)>=0?a[i*4+j-1]:0;
p=(j+1)>=0?a[i*4+j+1]:0;
q=(i+1)>=0?a[(i+1)*4+j]:0;
s=m+n+p+q+a[i*4+j];
if(s%2==0) break;
}
}
此算法的最大缺點是:循環次數太多,使N*N次,隨著N次數地增加,執行時間加長.

改進算法

為此又提出一種改進算法:
我們知道對每一盞燈而言,每盞燈的狀態改變次數僅與其上下左右(若存在的話)和自身
被點次數有關.這樣我們就可以對第一行利用枚舉法.列出其所有的可能值,

相關詞條

熱門詞條

聯絡我們