遙控器同時開關多部空調(diào)問題的數(shù)學研究

1、遙控器同時開關多部空調(diào)問題的數(shù)學研究高二(9)班 陳浩 張子卓 廖居敬 賴哲 李皓杰指導教師 鄧獻寶問題提出 某辦公室里有6部空調(diào)并排安裝在一面墻上。當用遙控器對其中一部空調(diào)操作時，則會影響到相鄰的空調(diào)。而在不同的位置操作，所影響的空調(diào)的數(shù)目也會不同。如果需要使其中的空調(diào)狀態(tài)依照我們的意愿改變，那么這個問題可否運用數(shù)學的方法來解決呢？研究目的研究并找出空調(diào)改變狀態(tài)的規(guī)律，將其轉(zhuǎn)化成數(shù)學語言，結(jié)合編程軟件Pascal實現(xiàn)這一轉(zhuǎn)化（編寫程序），計算出在任何初始情況下，到達任意最終情況的最佳操作方案。研究過程1、問題假設假設在某一距離，用遙控器對其中一部空調(diào)進行操作，則相鄰兩部空調(diào)的狀態(tài)會同時改變（

2、遙控器上的“開/關”按鈕是屬切換按鈕）。即假設從左到右第2臺的狀態(tài)為開，第3、4臺的狀態(tài)為關，那么當用遙控器對第3臺操作的時候，第3、4臺被開啟，而第2臺則被關閉。若其中任意空調(diào)的狀態(tài)為開，在這個距離，能否通過有限次的操作，使這些空調(diào)的另外任意臺的狀態(tài)變?yōu)殚_呢？若是能夠，會有最優(yōu)方案嗎？2、初步探索首先，我們設定空調(diào)狀態(tài)“開”時為“1”，“關”時為“0”。例如“開關開開關關”表示為“101100”。先將機器從左到右編號為m1、m2、m3、m4、m5、m6設m1=1，m2=0，m3=0，m4=1，m5=0，m6=0。根據(jù)實際情況確定運算的規(guī)則為：定義賦值函數(shù)g (mn)=, 即若mn=0則將mn

3、=1，反之則賦值mn=0。從上面的公式我們發(fā)現(xiàn)函數(shù)的數(shù)值只取得到0和1，那么這個過程可否引入布爾運算呢？經(jīng)過討論，用布爾值運算結(jié)合程序的話，在最終轉(zhuǎn)化上會出現(xiàn)比較復雜的過程，而且只用1、0兩個數(shù)值來進行運算也是十分方便的，所以我們放棄了使用布爾值進行運算。定義判斷的規(guī)則之后，我們便開始討論該用何種方法找到最優(yōu)方案。其中我們要解決的問題主要有：1、最優(yōu)方案有什么規(guī)律？2、如何篩選最優(yōu)值？一開始，我們只是注意到每一步的操作結(jié)果，試圖找出每一步的操作與上一步的結(jié)果有什么聯(lián)系，但是我們漸漸發(fā)現(xiàn)，每一步之間并無聯(lián)系。于是我們放棄了這種想法，把注意力轉(zhuǎn)向其他想法。接著我們開始猜想，當一部空調(diào)被重復操作時，

4、這兩次重復的操作之間是否有什么關系呢？于是我們進行了第一次嘗試來證明我們的疑問：初始狀態(tài)100100情況一情況二第一次操作m1010100m2111000第二次操作m2001000第三次操作m1111000在情況一中，對m1的兩次操作，使得它們相互抵消，結(jié)果就和只操作m2的情況四是一樣的。若對同一部空調(diào)操作偶數(shù)次，操作則可以相互抵消，那么在最優(yōu)的操作方案中，每部機最多被操作一次。因此，可以進一步得出一個結(jié)論，當有n部空調(diào)時，從任意的初始狀態(tài)到任意的最終狀態(tài)，所操作的步數(shù)不超過n步。即最優(yōu)解的步數(shù)應該在n步之內(nèi)，并且最優(yōu)解中無重復操作。既然最優(yōu)解是n步以內(nèi)不重復的話，那么接下來我們就想到對空調(diào)操

5、作的先后順序會不會影響達到最優(yōu)情況？會不會影響到達最優(yōu)解的步數(shù)多少呢？于是我們作出了第二次嘗試。我們嘗試先后操作兩部空調(diào)m1和m3，記錄最后狀態(tài)。之后再顛倒操作順序，也記錄最后狀態(tài)。然后對兩種情況作對比。初始狀態(tài)100100情況三情況四第一次操作m1010100m3111000第二次操作m3001000m1001000對比兩種狀態(tài)，不難發(fā)現(xiàn)，無論操作的先后順序如何，最終到達的狀態(tài)都是一樣的。接著我們又提出了如果是三部或更多部空調(diào)的操作順序任意，最終結(jié)果是否也一樣呢？經(jīng)過嘗試，我們發(fā)現(xiàn)，無論是三部空調(diào)還是四部空調(diào)，甚至是n部，操作的先后順序怎樣顛倒，結(jié)果都是一樣的。所以我們得出一個結(jié)論，最優(yōu)解的

6、步數(shù)在n步之內(nèi)，最優(yōu)解中無重復操作，并且最優(yōu)解中各部機器被操作的的順序是可任意的。根據(jù)以上研究得出的結(jié)論，剩下的問題就是如何確定最優(yōu)解操作。 1）根據(jù)上面的結(jié)論，最優(yōu)的操作次數(shù)不會超過6次，并且對每一次操作會同時對2部或3部空調(diào)賦值，即2或3臺空調(diào)的狀態(tài)會被改變。因此，第一與第六部空調(diào)最多被賦值2次，而第二到第五部空調(diào)對多被賦值3次。所以我們可以得出以下的不等式：0m1m2m616事實上，若fmn3（2n5），說明對fmn賦值了3次，根據(jù)操作規(guī)則，一定使左右兩部空調(diào)至少被賦值2次。那fmn-12，fmn+12。若fmn0（2n5），則fmn-11，fmn+11，那就是說，若fm20或fm50，

7、則一定有fm10或fm60。 于是我們得出了第一種確定最優(yōu)解的方法： 因為目標狀態(tài)于初始狀態(tài)對比，就同一部空調(diào)而言前后兩個狀態(tài)就只存在相同或者相反兩種情況。在最優(yōu)解情況下，假如空調(diào)mn初始狀態(tài)與它所對應的目標狀態(tài)相同的話，那么它被賦值的次數(shù)就必然是偶次，換言之就是fmn=0或fmn=2；反之，則fmn=1或fmn=3（n=1或n=n時fmn只等于1）。那么要判斷是否達到最優(yōu)解，就只要先確定每部空調(diào)被賦值的次數(shù)應為奇次或偶次，最后只要每部空調(diào)都達到了所要求的賦值次數(shù)，那么就證明達到目標狀態(tài)了。這時就運用上面的理論再進行推理就可以找出最優(yōu)解方案了。 2）然后又根據(jù)上面的結(jié)論，最優(yōu)解應是n步以內(nèi)的不

8、重復的操作。重復的步驟是可以抵消的，那么抵消的條件就是對該機器的操作次數(shù)為2、2×2、2×3，即偶數(shù)次時就可以抵消；反之則奇數(shù)次的就可以保留。 所以這就產(chǎn)生了第二種決定最優(yōu)解的方法： 通過無限次的操作達到目標狀態(tài)之后，判斷在這過程中每臺機器被直接操作過的次數(shù)，如果被操作的次數(shù)為偶數(shù)次的話，則會被抵消，也就是說這一步可以忽略；反之為奇數(shù)的話則證明這步操作不能被抵消，也就是這一步是一定要操作的。于是剔除所有被操作了偶數(shù)次的機器，剩下的被操作了奇數(shù)次的機器則為最優(yōu)解中的操作了。最后基于我們的研究是要結(jié)合程序語言來解決數(shù)學問題，我們經(jīng)過討論，對于上面1）的判斷篩選最優(yōu)解過程，無論從

9、人為判斷還是要翻譯成程序語言，都十分的復雜，所以我們就采用了2）的篩選判斷最優(yōu)解方法了。3、提出方案與討論在得到以上規(guī)律后，提出了三種方案。方案一：我們第一想到的是按m1、m2、m3、m4、m5、m6這樣的順序一臺一臺操作下去，然后通過多重循環(huán)來算出最佳方案，但是這又遇到了問題：假如解決方案并不是一個順序操作，那么程序會不會進入死循環(huán)呢？于是我們設想先從16進行一次順序的賦值操作，如果得不到結(jié)果的話，那么就回到對4賦值，跳過對5的賦值，執(zhí)行對6的賦值，如果仍沒有結(jié)果，則退到對3的賦值，接下來再對5、6賦值，如果還沒有結(jié)果的話，則只對5賦值，或只對6賦值。如果退到對1賦值仍沒有結(jié)果則從2開始賦值

10、，重復以上的方法，直到最后找出最佳方案為止。方案一若編為程序，會出現(xiàn)運算量較大，使運行時間過長的問題。編寫的程序也相對復雜，容易出錯?；谏鲜鲈颍覀儧Q定放棄這種方案。 方案二：由于每步操作的順序是不受限制的，于是利用電腦的高速運算的能力，對于任意的初始狀態(tài)，通過程序，每次隨機對一部空調(diào)進行操作，并同時記錄下每一部空調(diào)被直接操作的次數(shù)。當判斷到達所給出的最終狀態(tài)后，對每部空調(diào)操作的次數(shù)進行判斷，若被操作次數(shù)是偶數(shù)次的空調(diào)則舍去；若被操作次數(shù)是奇數(shù)次的空調(diào)直接打印空調(diào)的編號。這樣就可以得到最優(yōu)的方案。就方案二而言，可以算出答案，而它不具有針對性，可以推廣到N臺空調(diào)。但是這種方案在程序的運行時是

11、沒有一定的規(guī)律，因為它是隨機的對任意一臺空調(diào)操作。因此，此方案可能會出現(xiàn)運算時間長的情況。 方案三：這個方案是針對所提出的問題所設計的。通過電腦編程，對1到6所有不重復的操作組合都枚舉出來（例如12、13、123），再利用電腦程序?qū)⑦@些操作的組合套到所給出的最初情況中，當其中一個組合使得最初情況達到所要求的最終情況時，就停止程序并把這個組合打印出來。對于方案三，不僅可以得到答案，而且它具有一定的針對性，在程序運行時會按照一定的規(guī)律，所以在運算的時間不會太長。但是，這種方案在推廣方面就會比較困難，每增加一部空調(diào)，所得到的組合的方案數(shù)就會增加，當所輸入的空調(diào)的數(shù)目達到某個程度，所需要的運行時間可能

12、會較長。 最后，我們決定采用方案二為基礎進行編程。4、方案程序化當確定了按方案二來解決該問題后，我們就開始著手于將方案的思路用程序語言來實現(xiàn)。第一 要確定機器的情況：1）先手動輸入空調(diào)的數(shù)目n；2）再手動輸入這n臺機器的初始狀態(tài)（用數(shù)組m1.n來儲存，同時m1.n也用于儲存過程狀態(tài)）和目標狀態(tài)（用e1.n來儲存）；第二 通過電腦程序算出最優(yōu)值3）先隨機產(chǎn)生一個1n之間的整數(shù)j；4）對mj、mj+1、mj-1進行判斷，若“狀態(tài)”為1的就賦值為0，否則就賦值為1，同時再將第j部機被改變狀態(tài)的次數(shù)加上1（用數(shù)組f1.n來分別記錄每部機器被操作的次數(shù)）；5）每次對第j、j+1、j-1三臺機的狀態(tài)進行改

13、變之后，都要將當時的過程狀態(tài)與目標狀態(tài)進行對比并計算其相似度（用p來記錄m數(shù)組和e數(shù)組狀態(tài)吻合的個數(shù)作為相似度）。若pn就說明未到達目標狀態(tài)，則返回第3步繼續(xù)運算；若p=n則說明已達到目標狀態(tài)，則繼續(xù)進行下面的步驟分析并打印出最優(yōu)解； 第三 分析數(shù)據(jù)并列出最優(yōu)解 6）對數(shù)組f1.n中記錄到的每臺機器被操作的次數(shù)進行求余操作，若fi mod 2=1（即fi除以2的余數(shù)為0，即奇數(shù)），則操作第i部機器為最優(yōu)解中的一步，記錄下來，若fi mod 2=0(即fi為偶數(shù))，則這部機器的操作可省略； 7）輸出第6步中記錄的最優(yōu)解； 8）程序結(jié)束。 一維程序主體見“附1”。5、問題推廣以上問題是針對改變單行

14、機器狀態(tài)的，即一維問題。那么，如果變成是針對a×b這么一個矩陣式的機器排列的狀態(tài)轉(zhuǎn)換問題，即二維問題，是否也能解決呢？首先我們建立一個二維數(shù)組，并以機器的坐標表示作為它的編號，即ma,b。例如，一個3×3的機器矩陣中各機器的編號如下：m1,1 m1,2 m1,3m2,1 m2,2 m2,3m3,1 m3,2 m3,3假設對其中任一臺ma,b進行操作，則ma,b-1 ma,b+1 ma-1,b ma+1,b的狀態(tài)也會受影響，即對一部空調(diào)操作，除該空調(diào)外，它左右上下四臺空調(diào)的狀態(tài)也會改變。而對于某些特殊點上的空調(diào)，例如m2,1，由于其左方并沒有其他空調(diào)，所以對它的操作就只能影響

15、它本身和其右方、上方、下方三臺空調(diào)的狀態(tài)。其他的特殊點也依此類推。經(jīng)過討論研究發(fā)現(xiàn)，對于矩陣排列空調(diào)的控制，從任一初始狀態(tài)到達另任意目標狀態(tài)，其運算及判斷的方法基本上是一樣的，只是狀態(tài)被改變的影響范圍增加了并且把一維數(shù)組升級為二維數(shù)組就能夠解決問題了。 由于是a×b的一個矩陣，那么a、b就是任意的非零的數(shù)，那么當a=1，b3時，這就又回到了上面的一維問題。所以解決二維的程序同時也能夠解決一維的問題。 由于解決兩個問題的理論依據(jù)基本相似，所以在對一維問題的程序進行適當?shù)男薷闹?，我們得出了二維問題的程序。但是由于技術(shù)上的原因，目前程序只能夠?qū)崿F(xiàn)對“3×3”“2×3”

16、“3×2”三種矩陣的最優(yōu)方案的計算，而當a,b>3的情況并未能實現(xiàn)。我們將會在今后的實踐中對程序進行修改和對方法進行優(yōu)化，以解決此不足。二維程序主體見“附2”。研究體會以下是我們對這次研究性學習的三點總結(jié)：【科學性】從一般生活問題，發(fā)現(xiàn)并總結(jié)其規(guī)律，得到的研究成果具有針對性，可以推廣，以及可以在實際生活中應用?！緞?chuàng)新性】此研究性課題是從真實生活中發(fā)現(xiàn)的原始問題，并將其進行了數(shù)學建模，最后進一步建立程序模型來解決數(shù)學問題。這彌補了某些研究找出解決方案但通過人為很難實現(xiàn)的缺點?！疽?義】我們的研究從一開始的探索規(guī)律到解決一個一維問題并將其推廣到二維問題來解決，然后又從二維問題重新回

17、歸到一維問題的身上，這不但體現(xiàn)了數(shù)學問題的多變與聯(lián)系，同時也體現(xiàn)了事物是普遍聯(lián)系的哲學道理。在接到這個課題的時候，我們腦海里是一片空白的。原因是這個課題比較新穎，并沒有人研究過，致使我們不知道應該從何入手。盡管在整個研究過程中也經(jīng)歷過好幾次的失敗，但我們并沒有氣餒，而是通過不斷的嘗試，不懈的努力，加上老師的指導幫助，最終很好的完成了此課題的研究，得到了一個不錯的研究成果。經(jīng)過對此課題的研究，我們的思維得到了鍛煉，而且增強了解決問題的能力以及培養(yǎng)了嚴謹?shù)闹螌W態(tài)度。在以數(shù)學思維去解決問題的同時，我們的邏輯思維能力也有所提升，并且學會了組員之間應該如何相處、如何互助，培養(yǎng)了可貴的團隊精神。這些都將成

18、為我們成長過程中的寶貴經(jīng)驗，使我們終生受益。指導教師評析 本課題對生活問題進行數(shù)學建模，并且課題新穎，研究到位，具有較強的的科學性，創(chuàng)新性和應用性。其中將生活問題進行數(shù)學建模，運用計算機編程實現(xiàn)最優(yōu)解；并且實現(xiàn)由一維問題到二維問題的推廣；都是其優(yōu)勢所在。附1：一維問題程序：Program Research;Var n,i,k,j,l,t :integer; m,e,f,s :array1.100 of integer;Begin l:=1; write('Input The Number Of Machines:');readln(n); for i:=1 to n do fi

19、:=0; writeln('Input The Beginning Situation.'); for i:=1 to n do begin write('Machine',i,':'); readln(mi); end; writeln('Input The Ending Situation.'); for i:=1 to n do begin write('Machine',i,':'); readln(ei); end; repeat k:=0; j:=random(n)+1; fj:=fj+

20、1; if mj=1 then mj:=0 else mj:=1; if mj+1=1 then mj+1:=0 else mj+1:=1; if mj-1=1 then mj-1:=0 else mj-1:=1; for i:=1 to n do if mi=ei then k:=k+1; until k=n; for i:=1 to n do begin t:=fi mod 2; if t=1 then begin sl:=i;l:=l+1; end; end; write('The Best Solution Is:'); for i:=1 to l-1 do write

21、(si:3); readln;End.附2：二維問題程序Program ReSearch2;Var m,e,f,s :array1.50,1.50 of integer; a,b,i,j,k,l,r,p,t1,t2,z :integer;Begin l:=1;r:=0; writeln(' Length'); writeln(' -'); writeln(' W | |'); writeln(' i | |'); writeln(' d | |'); writeln(' t | |'); write

22、ln(' h | |'); writeln(' -'); write('Input The Length:');readln(b); write('Input The Width :');readln(a); for j:=1 to a do begin writeln('Input The Beginning Situation Of Row',r+1,':'); r:=r+1; for k:=1 to b do begin write('(',j,',',k,'):'); read(mj,k);fj,k:=0;sj,k:=0; end; end; r:=0; for j:=1 to a do begin writeln('Input The Ending Situation Of Row&#