開窗游戲[谷風(fēng)軟件]

1、開窗游戲:問題重述：現(xiàn)有n行n列共有n2個(gè)窗戶，每個(gè)窗戶只有兩個(gè)狀態(tài)：開和關(guān)。如果你點(diǎn)擊其中一個(gè)窗戶，則這個(gè)窗戶和它上下左右的四個(gè)窗戶的狀態(tài)都會(huì)發(fā)生變化，即開著的就會(huì)關(guān)閉，關(guān)閉的就會(huì)打開，對(duì)于邊界的窗戶我們只考慮存在的窗戶。對(duì)于以上定義的游戲規(guī)則, 試建立模型求解以下問題:(a) 假定n=5，所有窗戶的初始狀態(tài)為開，問如何點(diǎn)擊鼠標(biāo)將窗戶全部關(guān)閉, 且點(diǎn)擊鼠標(biāo)的次數(shù)盡可能少。(b)對(duì)于任意的n，假定棋盤的初始狀態(tài)為一個(gè)殘局: 部分方格為開, 部分方格為關(guān)閉, 能否給出一個(gè)判斷方法, 按照以上規(guī)則操作，該殘局最終能否變?yōu)槿P(guān)閉。問題分析：事實(shí)上，我們組最終的結(jié)果主要是針對(duì)（b）情況（因?yàn)?a)情況

2、實(shí)際上也就是全為開的5階殘局），這樣，問題就變?yōu)椋簩?duì)于任意的n，假定所有窗戶的初始狀態(tài)為一個(gè)殘局: 部分方格為開, 部分方格為關(guān)閉,問，是否有一種方案確定可以使殘局最終變?yōu)槿P(guān)閉？對(duì)于這個(gè)問題，我們解答如下：（1）首先要確定的是，一個(gè)窗戶在一定的點(diǎn)擊方案之下，最終變?yōu)殛P(guān)閉的充分必要條件是什么。我們首先研究一開始為全開的情況。在一開始為全開時(shí)，我們不妨假設(shè)未被點(diǎn)擊的窗戶為0，被點(diǎn)擊的窗戶為1，那么原題中所謂的窗戶陣列就被抽象為一個(gè)n階方陣。事實(shí)上，在這里我們可以推導(dǎo)出如下引理：當(dāng)且僅當(dāng)，方陣之中的某個(gè)數(shù)字及其上下左右（如果存在）數(shù)字之和為奇數(shù)時(shí)，該數(shù)字所代表的窗戶就是關(guān)閉的。這個(gè)引理的推導(dǎo)是簡(jiǎn)單

3、的：因?yàn)橐簧却皯舻臓顟B(tài)只受其上下左右（如果存在）窗戶點(diǎn)擊的影響，且一扇窗戶重復(fù)點(diǎn)擊實(shí)際上是沒有意義的，那么顯然這五扇窗戶的點(diǎn)擊對(duì)于中間一扇來講是等價(jià)的。這樣，對(duì)于這些窗戶奇數(shù)次的點(diǎn)擊就一定能使中間的窗戶關(guān)閉。引理證畢。但是，在窗戶排列為殘局時(shí)，這個(gè)引理的成立就受到了限制。一方面，殘局之中關(guān)閉的窗戶我們并沒有給它賦值；另一方面，假如給在殘局之中關(guān)閉的窗戶賦值為1，那么引理的成立就收到了挑戰(zhàn)，這是因?yàn)?，賦值為1無形之中就將在殘局之中關(guān)閉的窗戶與被點(diǎn)擊的窗戶等同了，但事實(shí)上，在殘局之中關(guān)閉的窗戶并不對(duì)中心的窗戶造成影響（中間的窗戶在殘局之中關(guān)閉的情況除外），于是就會(huì)導(dǎo)致誤判。為解決這個(gè)問題，我們只能

4、將在殘局之中關(guān)閉的窗戶與被點(diǎn)擊的窗戶區(qū)別起來，我們組的區(qū)別方案如下：1=需要被點(diǎn)擊的、一開始開啟的窗戶；0=不需要點(diǎn)擊的、一開始開啟窗戶；12=需要被點(diǎn)擊的、一開始關(guān)閉的窗戶；11=不需要點(diǎn)擊的、一開始關(guān)閉的窗戶。利用這個(gè)方案，當(dāng)我們甄別出一個(gè)窗戶在開始時(shí)就關(guān)閉時(shí)，我們就可以將其減去11以判定該窗戶是否遭到點(diǎn)擊（若是需要判定的窗戶在殘局之中關(guān)閉的話，在求和時(shí)不用對(duì)中間的窗戶如此做，事實(shí)上，此時(shí)該窗戶本身值的奇偶就已經(jīng)對(duì)其自身造成了影響）。這樣，該引理更改為：當(dāng)且僅當(dāng)，方陣之中的某個(gè)數(shù)字及其上下左右（如果存在）數(shù)字之和為奇數(shù)時(shí)，該數(shù)字所代表的窗戶就是關(guān)閉的。假如，上下左右（如果存在）的數(shù)字有超過

5、9的，那么將其減去11再求和。有了這樣一個(gè)引理之后，我們就可以利用解方程的方式，對(duì)于每一扇窗戶的關(guān)閉分別列出方程求解問題。但是這樣的方法無疑是有著巨大缺點(diǎn)的：首先，該方法的計(jì)算量過于龐大，已達(dá)到2n2量級(jí)；另外，當(dāng)n值變化時(shí)，所對(duì)應(yīng)的方程就必須重新列出。這兩個(gè)缺點(diǎn)無疑大幅降低了該種方法的實(shí)用性，所以，我們組采用 Matlab 編程的方式解決此題。（一）第一個(gè)程序：我們組進(jìn)行Matlab 編程的中心思想如下：1、首先是賦值模塊。由于n階情況中每一個(gè)窗戶都有兩種狀態(tài)，總共就存在2n2種方案。我們組利用算法，將12n2的整數(shù)，與每種方案相對(duì)應(yīng)，這樣就遍歷了所有可能的方案。2、之后是檢測(cè)模塊。檢測(cè)模塊

6、的主要原理就是前述的引理（補(bǔ)充后）。在本模塊中，我們利用軟件對(duì)每一種賦值模塊產(chǎn)生的方案進(jìn)行驗(yàn)證，若每扇窗戶都滿足前述引理，那么這種方案就是我們所求的。3、最后是優(yōu)化模塊。在本模塊之中，我們計(jì)算出每種可行方案所需要的點(diǎn)擊次數(shù)，并利用求最大值的方法進(jìn)行逐個(gè)比較，找到最小值后，最小值所對(duì)應(yīng)的方案即為我們的最終結(jié)果（如有多個(gè)，那么只取一種，因?yàn)槭聦?shí)上，所謂的多種最優(yōu)方案都是經(jīng)過一種方案旋轉(zhuǎn)或?qū)ΨQ得到的。）。以下為我們按照這種思路編寫的代碼：j=4;min=j2*11;for n=1:2(j2) x=n;B=11 11 11 11;11 11 11 0;11 0 0 0;0 0 0 0; for m=j

7、:-1:1 for o=j:-1:1 if mod(x,2)=1 x=(x-1)/2; B(m,o)=B(m,o)+1; else x=x/2; B(m,o)=B(m,o)+0; end end end for q=j:-1:1 for s=j:-1:1 sum=B(q,s);i=0; if s1 if B(q,s-1)9 sum=sum+B(q,s-1)-11; else sum=sum+B(q,s-1); end end if s9 sum=sum+B(q,s+1)-11; else sum=sum+B(q,s+1); end end if q1 if B(q-1,s)9 sum=sum+

8、B(q-1,s)-11; else sum=sum+B(q-1,s); end end if q9 sum=sum+B(q+1,s)-11; else sum=sum+B(q+1,s); end end if mod(sum,2)=1 continue else i=1; end if i=1 break end end if i=1 break end end if i=0 r=0; for c=1:j for d=1:j if B(c,d)10 r=r+B(c,d)-11; else r=r+B(c,d); end end end if r(j-2)*j h=x; else h=(j-2)

9、*j; end for i=j2:-1:h B(j,j)=0; c,C=Godlike(x,i,j,B); if c=0 break end end if c=0 break end endr=0;for e=1:j for f=1:j if C(e,f)10 r=r+C(e,f)-11; else r=r+C(e,f); end endendfprintf(答案是 %c 次.n點(diǎn)擊方案如下：n,r)disp(C)fprintf(注：n 1或12=點(diǎn)擊的窗戶n 0或11=未被點(diǎn)擊的窗戶n)遞歸函數(shù)Godlike：function c,C=Godlike(x,i,j,B) if x0 if mo

10、d(i,j)0 t=j-(i-mod(i,j)/j; else t=j-(i-mod(i,j)/j+1; end p=j-mod(i,j); B(t,p)=B(t,p)+1; for k=i-1:-1:x-1 c,C=Godlike(x-1,k,j,B); if c=0 return end endelse for q=j:-1:1 for s=j:-1:1 sum=B(q,s); c=0; if s1 if B(q,s-1)9 sum=sum+B(q,s-1)-11; else sum=sum+B(q,s-1); end end if s9 sum=sum+B(q,s+1)-11; else

11、 sum=sum+B(q,s+1); end end if q1 if B(q-1,s)9 sum=sum+B(q-1,s)-11; else sum=sum+B(q-1,s); end end if q9 sum=sum+B(q+1,s)-11; else sum=sum+B(q+1,s); end end if mod(sum,2)=1 continue else c=1; end if c=1 break end end if c=1 break end end if c=0 C=B; else C(j,j)=0; endendend不過，從數(shù)學(xué)角度看，僅僅數(shù)倍的減少對(duì)于2n2量級(jí)的數(shù)字

12、僅僅是微不足道的。另外，這個(gè)程序只能運(yùn)算5階及以下的任意殘局，甚至在5階時(shí)就已經(jīng)需要20分鐘左右，所以，這個(gè)程序也是不實(shí)用的。出于最優(yōu)的角度考慮，我們組最終設(shè)計(jì)了最終的第三套程序?。ㄈ┑谌齻€(gè)程序：我們的第三個(gè)程序較前兩個(gè)程序而言，其設(shè)計(jì)思路已經(jīng)完全不同。首先，我們先定義斜行的概念。所謂斜行，指的就是處在與右對(duì)角線（右上角與左下角的連線）相平行的直線上的一系列數(shù)字。我們不妨對(duì)斜行進(jìn)行排序。設(shè)從左上至右下的斜行所對(duì)應(yīng)的序列號(hào)依次增大，特殊的，左上角與右下角的數(shù)字分別為第一斜行與最后斜行?；谛毙卸x，我們提出如下兩條引理：引理1：如果一斜行最左側(cè)的數(shù)字及序號(hào)比該斜行小的所有斜行上的數(shù)字被唯一確定

13、，則本斜行上的所有數(shù)字也被完全確定。引理2：如果一個(gè)n階方陣中的序列號(hào)不超過n的斜行（即包括右對(duì)角線在內(nèi)的所有序列號(hào)不超過右對(duì)角線的斜行）上的數(shù)字已經(jīng)被完全確定，那么整個(gè)方陣上的數(shù)字就被完全確定。對(duì)于引理1，事實(shí)上，當(dāng)引理1提及的一斜行最左側(cè)的數(shù)字及序號(hào)比該斜行小的所有斜行上的數(shù)字都被確定時(shí)，該斜行左側(cè)第二個(gè)數(shù)字就可以確定下來。這是因?yàn)樽髠?cè)第二個(gè)數(shù)字（不妨設(shè)為a）左面的數(shù)字已經(jīng)被確定下來，但是其周圍的數(shù)字之中只有a還沒有確定，為保證該方案在最后使a左面的窗戶也關(guān)上，那么a就只能被賦上唯一的值。左面第三個(gè)數(shù)字及以后的數(shù)字也按照這種方法，就能夠全部被唯一確定。引理1證畢。對(duì)于引理2，由于右對(duì)角線及

14、其之上的所有斜行都已經(jīng)被賦值，我們不妨考慮左下角數(shù)字的右面的數(shù)字（設(shè)為b）。對(duì)左下角數(shù)字有影響的只有它上面的數(shù)字和b，此時(shí)包括左下角數(shù)字與它上面的數(shù)字都已經(jīng)被賦值，那么，與引理1的證明過程類似，我們也就可以確定b，乃至確定b所在的斜行（引理1）。接下來，仍利用同樣的方式，我們就可以把所有未被賦值的地方全部賦值。引理2證畢。由這兩條引理，我們又推導(dǎo)出兩條推論：推論1：當(dāng)且僅當(dāng)最左面的一豎排數(shù)字全部確定，整個(gè)方陣可以被唯一確定。推論2：當(dāng)方陣被推論1唯一確定后，當(dāng)且僅當(dāng)最右面的一豎排數(shù)字全部符合要求，整個(gè)方陣才是符合要求的。推論1其實(shí)是引理1、引理2的聯(lián)合應(yīng)用，在此不過多闡述。推論2其實(shí)是十分有意

15、思的。在引理1的推斷過程中我們利用a左面的窗戶來確定a的狀態(tài)，但實(shí)際上，我們說，我們這么做實(shí)際上是保證了a左面窗戶的“合法性”?；蛘撸覀冇挚梢钥吹?，每一個(gè)窗戶的“合法性”都由他們右面的窗戶來確定。但是，我們會(huì)發(fā)現(xiàn)，由于右面已經(jīng)沒有數(shù)字了，所以最右面的一豎排數(shù)字的“合法性”實(shí)際上是沒辦法得到保證的。所以，只要我們確定了最右面的一豎排數(shù)字的“合法性”，我們就相當(dāng)于確定了方陣的“合法性”，也即是否符合要求。如此，推論2證畢。至此，我們這個(gè)程序的理論基礎(chǔ)已經(jīng)敘述完畢，接下來就是本程序的主要模塊：1、賦值模塊。只利用第一個(gè)程序提供的賦值方法，將最左面的一豎排數(shù)字用02n對(duì)應(yīng)的二進(jìn)制數(shù)進(jìn)行遍歷，之后利用

16、遞歸程序，按照推論1的做法將整個(gè)方陣賦值。2、檢測(cè)模塊。對(duì)于經(jīng)過賦值模塊賦值得到的新方陣，我們就利用推論2提供的簡(jiǎn)單方法對(duì)整個(gè)方陣進(jìn)行檢測(cè)即可。3、優(yōu)化模塊。類似第一個(gè)程序。第三個(gè)程序的代碼如下：主程序：j=4;C=11 11 11 0;0 11 0 0 ;0 0 0 0;0 0 0 0;sum1,D1=main_god(1,0,C,j);sum2,D2=main_god(1,1,C,j);if sum1sum2 sum=sum2; D=D2;else sum=sum1; D=D1; endif sum=j2 fprintf(無答案！n)else fprintf(答案是 %d 次.n原布局為：

17、n,sum) disp(C) fprintf(n點(diǎn)擊方案為：n) disp(D) fprintf(注：n 1=需要被點(diǎn)擊的、一開始開啟的窗戶n 0=不需要點(diǎn)擊的、一開始開啟窗戶n12=需要被點(diǎn)擊的、一開始關(guān)閉的窗戶n11=不需要點(diǎn)擊的、一開始關(guān)閉的窗戶n)end遞歸賦值函數(shù)main_god：function sum,D=main_god(n,i,C,j)if nsum2 sum=sum2; D=D2; else sum=sum1; D=D1; endelse if n9 sum=sum+C(q,j-1)-11; else sum=sum+C(q,j-1); end if C(q,j)9 sum

18、=sum+C(q,j)-11; else sum=sum+C(q,j); end if q1 if C(q-1,j)9 sum=sum+C(q-1,j)-11; else sum=sum+C(q-1,j); end end if q9 sum=sum+C(q+1,j)-11; else sum=sum+C(q+1,j); end end if mod(sum,2)=0 c=1; end if c=1 break end end if c=0 sum=0; for x=1:j for y=1:j if C(x,y)9 sum=sum+C(x,y)-11; else sum=sum+C(x,y);

19、 end end end D=C; else sum=j2; D=C; end endend end獨(dú)立賦值模塊函數(shù)god_brother1、 god_brother2：function D=god_brother1(n,i,C,j)C(n,1)=i+C(n,1);if n1 for k=n-1:-1:1 C(k,n-k+1)=god_judger(k,n-k+1,C,j)+C(k,n-k+1); endendD=C;endfunction D=god_brother2(n,i,C,j)C(j,n-j+1)=i+C(j,n-j+1);if n-j+11 if C(q,s-2)9 sum=sum

20、+C(q,s-2)-11; else sum=sum+C(q,s-2); endendif s-19 sum=sum+C(q,s-1)-10; else sum=sum+C(q,s-1); endendif q1 if C(q-1,s-1)9 sum=sum+C(q-1,s-1)-11; else sum=sum+C(q-1,s-1); endendif q9 sum=sum+C(q+1,s-1)-11; else sum=sum+C(q+1,s-1); endendif mod(sum,2)=0 k=1;else k=0;endend以上即為第三個(gè)程序的全部代碼。較之前兩個(gè)程序，第三個(gè)程序已

21、經(jīng)是臻于完美。從運(yùn)算角度講，第三個(gè)程序運(yùn)算量的數(shù)量級(jí)為2n，比前兩個(gè)程序的運(yùn)算量可以說是降了一個(gè)臺(tái)階。從使用功能角度講，第三個(gè)程序的運(yùn)行界面也無疑是更友好的，結(jié)果之中把點(diǎn)擊之前的殘局狀態(tài)也一并列出，方便使用者比較。從算法結(jié)構(gòu)角度考慮，第三個(gè)算法之中更是利用了為遞歸函數(shù)賦值的方法避免了全局變量的使用，從而大大增強(qiáng)了運(yùn)算的準(zhǔn)確性。實(shí)際上，利用第三個(gè)程序計(jì)算21階方陣的時(shí)間和利用第一、二個(gè)程序計(jì)算5階方陣的時(shí)間是基本等同的，這也從側(cè)面反映出第三個(gè)算法的優(yōu)越性。我們將在最后列出310階開始時(shí)全為開的點(diǎn)擊方案，以資參考。但是不得不說，整個(gè)題目最大的遺憾在于，直到最后也沒能找出一種適用于任何情況的普遍規(guī)律，來指導(dǎo)人們不利用計(jì)算機(jī)解決題目?？磥?，這個(gè)問題只能遺留給更有才能的同學(xué)解決，我們組對(duì)于這種問題仍是力有未逮。全文至此。附：410階非殘局方陣最優(yōu)點(diǎn)擊方法 （n=方陣階數(shù)；N=最優(yōu)點(diǎn)擊次數(shù)。）n=4N=4 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 n=5N=15 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0