點燈遊戲是一個十分有趣的智力遊戲,他的規則是這樣的:有一行N行N列的燈,開始時全部是滅的,當你點擊其中一盞燈是他的上下左右(若存在的話)狀態全部改變,現在要求你在限定的時間內以最少
地步數,將全部的燈點亮.
現在,我們以某一盞燈為研究對象,顯然,當此燈狀態被改變奇數次後,燈被點亮.反之,被點擊偶數次,
燈則維持原來的熄滅狀態不變.而促使燈狀態改變的事件不外乎其上下左右(若存在的話)被點擊.
推而廣之,只要所有的燈狀態被改變奇數次,則可保證所有的燈全部被點亮.同時,應該,說明的是,
對每一盞燈來說,自身被點次奇數數與一次效果相同,這是因為,對每盞燈來說,被點一次後,再點偶數次,
自身他的上下左右(若存在的話)狀態恢復原態.同樣道理,自身被點偶數次,相當於沒被點.故在最少步數
的限制下,每盞燈要么沒被點,要么僅被點一次.
我們很容易想到,可以用枚舉的方法來解決問題,以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次數地增加,執行時間加長.
為此又提出一種改進算法:
我們知道對每一盞燈而言,每盞燈的狀態改變次數僅與其上下左右(若存在的話)和自身
被點次數有關.這樣我們就可以對第一行利用枚舉法.列出其所有的可能值,
#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(k=0;k<row;k++)
for(i=1;i<row;i++) /* OUT 1ROW */
for(j=0;j<row;j++)
{ s=a【(i-1)*row+j】; /* 上 */
if(i-2>=0)s+=a【(i-2)*row+j】; /*上上 */
if(i-1>=0) { if(j-1>=0) s+=a【(i-1)*row+j-1】; /*上左 */
if(j+1<row)s+=a【(i-1)*row+j+1】; /*上右 */
}
if(s<=1) a【i*row+j】=1-s;/*self */
else if(s<=3) a【i*row+j】=3-s;
else a【i*row+j】=1;
}
m=row-1;
for(n=0;n<row;n++) /*Judge last row ok? */
{ ss=a【m*row+n】+a【(m-1)*row+n】;/*上 self */
if(n-1>=0) ss+=a【m*row+n-1】; /*左 */
if(n+1<row) ss+=a【m*row+n+1】; /*右 */
if(ss%2==0) break;
}
if(n==row) { printf("\n OK !\n"); fputs("\n OK !\n",fp);
sum=0;
for(i=0;i<n*n;i++)
{ sum+=a;
printf("%2d",a); fprintf(fp,"%2d",a);
if((i+1)%n==0) printf("\n"),fputs("\n",fp);
}printf("點擊次數:%2d.\n\n", sum);
fprintf(fp,"點擊次數:%2d.\n\n", sum);
getch();
}
} fclose(fp);
}
