(完整文本版)MATLAB實驗四-數(shù)字填圖問題

PAGE實驗四數(shù)字填圖問題一、問題背景和實驗?zāi)康臄?shù)字填圖問題是數(shù)學(xué)問題的一種趣味形式．早在19世紀(jì)后半期，一些數(shù)學(xué)家就在報刊中大量使用數(shù)字填圖游戲和字謎游戲等，目的是使業(yè)余愛好者也能通過簡單的形式去認(rèn)識、理解和琢磨深奧的數(shù)學(xué)問題，這些問題中甚至包括困惑了世間智者350多年、于1994年才剛剛被證明了的“費(fèi)馬大定理”．100多年來，數(shù)字填圖問題對數(shù)學(xué)界所起的作用是不言而喻的．大家都知道，數(shù)學(xué)問題一般都經(jīng)過嚴(yán)格的邏輯證明才得以解決．而邏輯證明是指從一些公理出發(fā)，經(jīng)過邏輯推理來證明問題．但隨著20世紀(jì)40年代以來計算機(jī)的誕生和發(fā)展，計算機(jī)改變了整個世界，計算機(jī)已在各個領(lǐng)域發(fā)揮作用，并取得了許多重大進(jìn)展．于是，能否用計算機(jī)來證明數(shù)學(xué)問題便成了大家關(guān)心的話題．所謂計算機(jī)證明是指充分發(fā)揮計算機(jī)計算速度快和會“推理”的特點，用計算機(jī)程序模擬解題或進(jìn)行窮舉檢驗，最后得到問題的解．幾乎所有的數(shù)學(xué)家對計算機(jī)證明持保留態(tài)度，因為他們相信，只有邏輯證明才是真正可靠的．但“四色問題”的證明，又使他們感到困惑，因為“四色問題”的證明實際上是一個計算機(jī)證明．能否用計算機(jī)來證明數(shù)學(xué)問題的爭論可能會持續(xù)一個相當(dāng)長的時間，本實驗旨在通過生活中幾個常見的數(shù)字填圖問題的探究，談?wù)勥@類問題的邏輯推理解法和計算機(jī)解法．二、相關(guān)函數(shù)（命令）簡介1．cputime命令：記錄執(zhí)行本命令時的Matlab時鐘的時間(秒)．2．tic命令：開始計時．3．toc命令：結(jié)束計時．4．disp(x)：輸出矩陣x．x的各項應(yīng)為字符，所以在輸出時要進(jìn)行轉(zhuǎn)化．相關(guān)的命令有：num2str()：把數(shù)值轉(zhuǎn)化為字符；mat2str()：把矩陣轉(zhuǎn)化為字符．5．fopen(filename,mode)：用mode方式打開/建立filename文件，以備寫入數(shù)據(jù)，使用方式：fid=fopen(filename,mode)．6．fclose(fid)：關(guān)閉上述文件．例如下列程序是把一個兩行的矩陣y寫入文件output.dat：x=0:0.1:1;y=[x;exp(x)];fid=fopen(’output.dat’,’wt’);fprintf(fid,’xexp(x)\n’);fprintf(fid,’%6.2f%12.8f\n’,y);%實際得到的是矩陣y的轉(zhuǎn)置矩陣status=fclose(fid);與C語言的文件操作方式相類似．三、實驗內(nèi)容讓我們先從一個簡單的問題出發(fā)來談?wù)剶?shù)字填圖問題的兩種解法．然后通過幾個稍復(fù)雜問題的探究，從中展示邏輯推理的嚴(yán)謹(jǐn)以及計算機(jī)解法的魅力，啟迪我們?nèi)ソ鉀Q更復(fù)雜的數(shù)學(xué)問題．注：在本實驗中，將表達(dá)式abc理解為，即100*a+10*b+c，其余類似，不另加說明．(一)、一個簡單的問題及其解答問題一：在圖1的幾個加法等式中，每個□表示一個非零數(shù)字，任意兩個數(shù)字都不相同，問有多少個解?圖1【邏輯解法】為簡潔起見，將它的3個式子記作：a+b=c，d+e=f，g+h=i0，若問題有解，則顯然有i=1，且(a+b)+(d+e)+(g+h)=c+f+i10，故45=(a+b+c)+(d+e+f)+(g+h+i)=2(c+f)+i11，即c+f=17，故c=8，f=9或c=9，f=8．考慮到a~i互不相同，當(dāng)要求a<b，d<e，g<h時，有如下4組解（見下表）：注：本問題實際上僅有2個解是本質(zhì)的，即表中的第2、3行，第4、5行所代表的解僅是位置不同而已．如不要求a<b，d<e，g<h，則解的個數(shù)是個．【計算機(jī)解法】為驗證此結(jié)果，可用Mathematica、Matlab、TurboC等軟件進(jìn)行模擬解題，充分利用計算機(jī)運(yùn)算速度快的特點進(jìn)行窮舉法檢驗．實踐表明本問題解的情況恰如上所述．用Matlab實現(xiàn)的程序清單可參見附錄1，這一算法比較慢（一個更慢的算法參見附錄1B，試分析其原因），而一個提速的程序清單可參見附錄2，TurboC程序清單可參見附錄3，而Mathematica程序清單可參見附錄4．【評論】這個問題的邏輯解法十分簡單，或許根本不需要計算機(jī)解法，但所用程序有一定的代表性，稍加修改即可解決一系列問題，這點可從下面的問題中看到．(二)、幾個較復(fù)雜的問題及其解答問題二：在圖2的4個算式中，每個□表示一個非零數(shù)字，任意兩個數(shù)字都不相同，問(A)、(B)、(C)和(D)這4種情形分別有多少個解?圖2討論：顯然，情形(C)無解．情形(D)與情形(C)實際上是同一個問題，因此也無解．情形(B)與情形(A)實際上也是同一個問題．我們先討論情形(A)的解的個數(shù)．【邏輯解法】為簡潔起見，將此豎式記作：abc+def=ghi，即，其中a~i代表1~9這9個互不相同的非零數(shù)字．據(jù)九余數(shù)性質(zhì)可知，兩個“加數(shù)”中的六個數(shù)字之和被9除的余數(shù)應(yīng)等于“和數(shù)”中的三個數(shù)字之和被9除的余數(shù)．又這兩個“加數(shù)”與“和數(shù)”中共九個數(shù)字正好是1，2，，9，它們的和為45，被9除的余數(shù)是0，易見“和數(shù)”的三個數(shù)字之和被9除的余數(shù)必為0，也即：“和數(shù)”是9的倍數(shù)．注意到題設(shè)可知，“和數(shù)”的三個數(shù)字之和必定為：g+h+i=9或g+h+i=18．<1>考慮g+h+i=9的情形．(1)首先必定有g(shù)>3，否則{a，d}最小為{1，2}，{b，e}最小為{4，5}，{c，f}最小為{6，7}，此時已有abc+def>400，與g3矛盾．故g4；另外，g6為顯然；(2)若g=4，由g+h+i=9，h+i=5，故{h，i}最小為{1，4}或{2，3}；但已有g(shù)=4，故{h，i}為{2，3}，而{a，d}最小為{1，4}，從而g5，與g=4矛盾；(3)若g=5，由g+h+i=9，h+i=4，故{h，i}為{1，3}；而{a，d}最小為{2，4}，從而g6，與g=5矛盾；(4)若g=6，由g+h+i=9，h+i=3，故{h，i}為{1，2}；而{a，d}最小為{3，4}，從而g7，與g=6矛盾．綜上所述，g+h+i=9的情形下問題無解．<2>考慮g+h+i=18的情形．由于g4（理由同上），以下按g=9，8，，4的順序分類討論：(1)g=9，則h+i=9．由于a~i互不相同，于是g，h，i的可能的取值見下表：對這些豎式有序地交換兩個加數(shù)的百位數(shù)、十位數(shù)和個位數(shù)，可得到每個類型的8(=)個不同豎式(解)，小計有解128=96個．注意：表中的第2、5、6、9列為容易造成失解的地方，要特別留意．完全類似地有如下一系列過程：(2)g=8，則h+i=10．仿(1)，小計有解108=80個，解例見下表：(3)g=7，則h+i=11．小計有解58=40個，解例見下表：(4)g=6，則h+i=12．小計有解68=48個，解例見下表：(5)g=5，則h+i=13．小計有解58=40個，解例見下表：(6)g=4，則h+i=14．小計有解48=32個，解例見下表：結(jié)論：本問題的解的個數(shù)為：(12+10+5+6+5+4)8=428=336．注：<1>如不考慮兩個加數(shù)的上下位置關(guān)系，則總的解的個數(shù)為：428/2=168．<2>由于情形(B)與情形(A)是同一個問題，故解的個數(shù)也為：428=336．【計算機(jī)解法】為驗證此結(jié)果，仍用Matlab、Mathematica、TurboC編程進(jìn)行模擬解題，充分利用計算機(jī)運(yùn)算速度快的特點進(jìn)行窮舉法檢驗．實踐表明本問題有且只有336個不同豎式（解），而Matlab程序清單可參見附錄5，你可發(fā)現(xiàn)它與附錄1十分相似．【評論】這個問題的邏輯解法較復(fù)雜，而計算機(jī)解法則是如此的簡單快捷，運(yùn)行整個程序不要1分鐘．實際上非常復(fù)雜的“四色問題”的證明也是這樣：對1482種有代表性地圖的分析，若依靠人工去做，可能要幾十年甚至上百年的時間，而用計算機(jī)，只要1200小時即告完成．這還是70年計算機(jī)的計算水平，若用現(xiàn)在的計算機(jī)，計算時間應(yīng)該不會超過一天!問題三：在圖3的加法算式中，每個□表示一個非零數(shù)字，任意兩個數(shù)字都不相同，問可有多少個解?【邏輯解法】為簡潔起見，將此豎式記作：a+bc+def=ghi或，其中a~i代表1~9這9個互不相同的非零數(shù)字．據(jù)九余數(shù)性質(zhì)并采用完全類似問題二的討論可知，“和數(shù)”的三個數(shù)字之和必定為：g+h+i=9或g+h+i=18．同時，g1，否則d=1；另外g>d，從而g=d+1．由于9g2，以下按g=9，8，7，(0)g=9，d=8．則h+i=9．由于a~i互不相同，于是g，h，i的可能的取值為（見下表）：圖3小計有解0個．(1)g=8，d=7．則h+i=1(不可能，舍去)或h+i=10．由于a~i互不相同，于是g，h，i的可能的取值為(見下表)：對這些豎式有序地交換三個加數(shù)的個位數(shù)、兩個加數(shù)的十位數(shù)，可得到每個類型的12個不同豎式(解)，小計有解212=24個．完全類似地有如下一系列過程：(2)g=7，d=6．則h+i=2(不可能，舍去)或h+i=11．仿(1)，小計有解212=24個．(3)g=6，d=5．則h+i=3或h+i=12．有解112=12個，解例見下表：(4)g=5，d=4．則h+i=4或h+i=13．有解312=36個，解例見下表：(5)g=4，d=3．則h+i=5或h+i=14．有解212=24個，解例見下表：(6)g=3，d=2．則h+i=6或h+i=15．有解212=24個，解例見下表：(7)g=2，d=1．則h+i=7或h+i=16．有解212=24個，解例見下表：結(jié)論：本問題的解的個數(shù)為：(2+2+1+3+2+2+2)12=168．【計算機(jī)解法】讓我們再嘗試計算機(jī)解法．仍用Matlab、Mathematica、TurboC編程進(jìn)行窮舉法驗證，程序清單類似于附錄1~附錄5，不再另附．運(yùn)行結(jié)果表明本問題的確有且只有168個不同豎式（解），要說明的是：該程序在一般的計算機(jī)上運(yùn)行一次也只需不到1分鐘．【評論】也許有人會說，你的問題還僅是一個有窮的問題，象“費(fèi)馬大定理”這樣的無窮問題，你的計算機(jī)就無能為力了!情況或許是這樣．但應(yīng)該注意到：非常復(fù)雜的“四色問題”也是一個無窮問題，但妙就妙在有人能將它們縮小到1482種有代表性地圖以內(nèi)，從而成為一個有窮的問題!至此，對于計算機(jī)解題的作用恐怕再不能視而不見了!下面的兩個問題也是成功地運(yùn)用計算機(jī)解題的的一些典型例子，而至少到目前為止還沒有看到它們的推理解法.問題四：圖4的加法等式是：兩個真分?jǐn)?shù)之和等于第三個真分?jǐn)?shù)，每個□表示一個不為0的數(shù)字，任意兩個數(shù)字都不相同．比如：，試找出所有可能的解．圖4【計算機(jī)解法】本問題利用計算機(jī)程序已找到解答，共有10個解．解答請參見：《數(shù)學(xué)教學(xué)》（華東師范大學(xué)）1994年第5期．【評論】程序如何編?看起來問題似乎很簡單，只要將附錄1~附錄5稍加修改即可．例如可利用附錄6的Matlab程序進(jìn)行計算．但實際情況讓我們大吃一驚：用Matlab程序居然只有6個解！還有4個解到哪里去了？用TurboC程序編寫出的類似的程序居然只有7（或9）個解！還有3（或1）個解到哪里去了？還有人用TurboC程序編寫出的類似的程序，卻居然得到了11個“解”！這個多出的1個“解”是哪里來的？類似的問題還會發(fā)生在本實驗的“四、自己動手”的第6題中，用不同的語言編寫出的類似程序，其運(yùn)行結(jié)果居然差距很大，你能明白其中的道理嗎？根據(jù)觀察，可能是浮點問題，也可能是整數(shù)的上界問題，或別的什么原因．具體什么原因，留作思考題．問題五：圖5的加法等式是：兩個假分?jǐn)?shù)之和等于第三個假分?jǐn)?shù)，每個□表示一個不為0的數(shù)字，任意兩個數(shù)字都不相同．試找出所有可能的解．圖5【計算機(jī)解法】本問題利用計算機(jī)程序也已找到解答，共有41個解．同樣只要將附錄1~5的程序稍加修改即可．(三)、小結(jié)數(shù)字填圖問題是一種活潑的、變形的數(shù)學(xué)問題，邏輯推理是這類問題的一般解法．但也有若干數(shù)字填圖問題要找到這樣的邏輯推理解法是非常地困難，而采用計算機(jī)解法則輕而易舉．問題一和問題二就是這樣的例子．至于問題四和問題五則只能給出計算機(jī)解法．盡管數(shù)學(xué)家們很難接受計算機(jī)解法，因為他們擔(dān)心計算機(jī)會出錯（盡管這種出錯的概率幾乎為零!），更重要的是他們堅信邏輯證明是解答這類問題的根本方法．但上述事實證明計算機(jī)解法也是十分有效的．另一個公認(rèn)的例子是“四色問題”，它的證明實際上就是一個計算機(jī)證明．關(guān)于這個問題的爭論可能會有一個相當(dāng)長的時間．不管將來的結(jié)論如何，但計算機(jī)證明(解題)畢竟代表將來數(shù)學(xué)問題解決的一個方向．就象安德魯·懷爾斯(AndrewWiles)突發(fā)靈感地把“伊娃沙娃理論”和“科利瓦金弗萊切方法”結(jié)合在一起可以完美地互相補(bǔ)足，以致最終證明了“費(fèi)馬大定理”一樣，未來的數(shù)學(xué)家或許會讓“邏輯證明”和“計算機(jī)證明”也完美結(jié)合，從而解決更多的數(shù)學(xué)問題．注；西蒙·辛格[英]，1998年．《費(fèi)馬大定理一個困惑了世間智者358年的謎》，薛密譯，上海譯文出版社．四、自己動手1．一道競賽題（以下稱“原問題”）1998年4月香港數(shù)理教育學(xué)會主辦的初中數(shù)學(xué)競賽有這樣一道試題：在下面的加法算式中，每個□表示一個數(shù)字，任意兩個數(shù)字都不相同，那么A與B的乘積的最大值是多少?解答：最大值是15．你能給出邏輯推理解法并用計算機(jī)加以驗證嗎?由上述問題引伸出的三個問題：2．滿足原問題題意的不同的加法算式（豎式）共有多少個?本問題有60個不同豎式（解）．試給出邏輯推理解法并用計算機(jī)加以驗證．原競賽題是針對初中生而設(shè)計的，故問題的難度被大大降低了．本練習(xí)已有一定難度．不可否認(rèn)，邏輯推理是解決問題的重要途徑，而計算機(jī)模擬解題在其中所起的作用也是不言而喻的．我們可以將練習(xí)2一般化，你將發(fā)現(xiàn)計算機(jī)模擬解題的有效性和重要性．3．如果在原問題中刪除條件：“任意兩個數(shù)字都不相同”，則滿足題意的不同的加法算式（豎式）共有多少個?本問題實際上是一個有約束條件的全排列問題．本問題的答案是：48195個!這真是一個神奇的數(shù)值．要得到這個數(shù)值應(yīng)該說是有一定難度的．試給出邏輯推理解法并用計算機(jī)加以驗證．注：假如在本問題中允許三個“加數(shù)”與“和數(shù)”均可以由數(shù)字0作為開頭，去掉“任意兩個數(shù)字都不相同”這個條件限制，本問題則變成一個真正的全排列問題．在a+bc+def=ghij中，“和數(shù)”ghij是被動的．由a，b，c，d，e，f{0，1，2，3，4，5，6，7，8，9}，此時本問題有解106個．練習(xí)3是利用計算機(jī)模擬解題的真正代表，可以說計算機(jī)模擬解題能力在某些方面確已達(dá)到了邏輯推理解題的能力．而以下的練習(xí)4將把練習(xí)2的難度進(jìn)一步加大．你將發(fā)現(xiàn)運(yùn)用計算機(jī)模擬解題在某些方面甚至已超過運(yùn)用邏輯推理解題．這個問題是：4．假如違反常規(guī)，允許三個“加數(shù)”與“和數(shù)”均可以由數(shù)字0作為開頭，保留條件：“任意兩個數(shù)字都不相同”，則滿足原問題題意的不同的加法算式（豎式）共有多少個?本問題共有228個解，即在練習(xí)2有60個不同豎式（解）的基礎(chǔ)上再增加168個解．試給出邏輯推理解法并用計算機(jī)加以驗證．分析和觀察：練習(xí)4的結(jié)論與本實驗中的“問題三”的結(jié)論是否有一定的聯(lián)系?有何聯(lián)系?5．驗證本實驗中的“問題四”、“問題五”的結(jié)論．能否給出相應(yīng)的推理解法?答案是：非常困難!不妨一試．你是否發(fā)現(xiàn)運(yùn)用計算機(jī)模擬解決本問題，已超過運(yùn)用邏輯推理解決本問題?6．設(shè)A~J表示十個互不相同的數(shù)字，問：方程（注意：組成分?jǐn)?shù)的四個數(shù)的第一位數(shù)字不能為0）共有多少個解？答案是110個?是118個?是其它的數(shù)字？為什么？7．前面所說的“用不同的語言編寫出的類似程序，其運(yùn)行結(jié)果居然差距很大”現(xiàn)象，你遇到過嗎？試結(jié)合附錄6，分析產(chǎn)生漏（增）解的原因．8．利用Matlab文件操作技術(shù)修改附錄1，使得結(jié)果可以保存到一個文本文件中．類似地，用TurboC文件操作技術(shù)修改附錄3，使得結(jié)果也可以保存到一個文本文件中．五、附錄附錄1(fulu1.m)：tic;n=0;fora=1:9forb=1:9if(b==a),continue;endforc=1:9if(c==a|c==b),continue;endford=1:9if(d==a|d==b|d==c),continue;endfore=1:9if(e==a|e==b|e==c|e==d),continue;endforf=1:9if(f==a|f==b|f==c|f==d|f==e),continue;endforg=1:9if(g==a|g==b|g==c|g==d|g==e|g==f),continue;endforh=1:9if(h==a|h==b|h==c|h==d|h==e|h==f|h==g),continue;endfori=1:9if(i==a|i==b|i==c|i==d|i==e|i==f|i==g|i==h)continue;endif(a<d&a*(10*e+f)*(10*h+i)+d*(10*b+c)*(10*h+i)==g*(10*b+c)*(10*e+f))n=n+1;disp(['第',num2str(n),'個解：',...num2str(a),'/',num2str(b),num2str(c),'+',...num2str(d),'/',num2str(e),num2str(f),'=',...num2str(g),'/',num2str(h),num2str(i)])end;end;end;end;end;end;end;end;end;end;%%共有10個endt3=toc;fprintf('\nTheelapsedtime(measuredbytic/toc)is:%g',t3)附錄1B(fulu1B.m)：t=cputime;n=0;fora=1:9forb=1:9ifb~=aforc=1:9ifc~=a&c~=bford=1:9ifd~=a&d~=b&d~=cfore=1:9ife~=a&e~=b&e~=c&e~=dforf=1:9iff~=a&f~=b&f~=c&f~=d&f~=eforg=1:9ifg~=a&g~=b&g~=c&g~=d&g~=e&g~=fforh=1:9ifh~=a&h~=b&h~=c&h~=d&h~=e&h~=f&h~=gfori=1:9ifi~=a&i~=b&i~=c&i~=d&i~=e&i~=f&i~=g&i~=h...&a+b==c&d+e==f&g+h==i*10&a<b&d<e&a<d&g<hn=n+1;disp(['第',num2str(n),'個解：',...num2str(a),'+',num2str(b),'=',num2str(c),'',...num2str(d),'+',num2str(e),'=',num2str(f),'',...num2str(g),'+',num2str(h),'=',num2str(i),'0'])end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end;end%%共有17個endtime=cputime-t附錄2(fulu2.m，提速版)：t02=clock;n=0;A1=1:9;fori1=1:9a=A1(i1);A2=A1([1:i1-1,i1+1:9]);fori2=1:8b=A2(i2);A3=A2([1:i2-1,i2+1:8]);fori3=1:7c=A3(i3);A4=A3([1:i3-1,i3+1:7]);fori4=1:6d=A4(i4);A5=A4([1:i4-1,i4+1:6]);fori5=1:5e=A5(i5);A6=A5([1:i5-1,i5+1:5]);fori6=1:4f=A6(i6);A7=A6([1:i6-1,i6+1:4]);fori7=1:3g=A7(i7);A8=A7([1:i7-1,i7+1:3]);fori8=1:2h=A8(i8);i=A8([1:i8-1,i8+1:2]);if(a<d&a*(10*e+f)*(10*h+i)+d*(10*b+c)*(10*h+i)==g*(10*b+c)*(10*e+f))n=n+1;disp(['第',num2str(n),'個解：',...num2str(a),'/',num2str(b),num2str(c),'+',...num2str(d),'/',num2str(e),num2str(f),'=',...num2str(g),'/',num2str(h),num2str(i)])endendendendendendendendendt2=etime(clock,t02);fprintf('\nTheelapsedtime(measuredbyclock/etime)is:%g',t2)附錄3(TurboC程序，fulu3.c)：#include<stdio.h>main(){inta,b,c,d,e,f,g,h,i,j,n=0;printf("\n\n");for(a=1;a<=9;a++){for(b=1;b<=9;b++){if(b==a)continue;for(c=1;c<=9;c++){if(c==a||c==b)continue;for(d=1;d<=9;d++){if(d==a||d==b||d==c)continue;for(e=1;e<=9;e++){if(e==a||e==b||e==c||e==d)continue;for(f=1;f<=9;f++){if(f==a||f==b||f==c||f==d||f==e)continue;for(g=1;g<=9;g++){if(g==a||g==b||g==c||g==d||g==e||g==f)continue;for(h=1;h<=9;h++){if(h==a||h==b||h==c||h==d||h==e||h==f||h==g)continue;for(i=1;i<=9;i++){if(i==a||i==b||i==c||i==d||i==e||i==f||i==g||i==h)continue;elseif((a+b==c)&&(d+e==f)&&(g+h==10*i)&&(a<b)&&(d<e)&&(a<d)&&(g<h)){printf("%3d:%d+%d=%d,%d+%d=%d,%d+%d=%d0",++n,a,b,c,d,e,f,g,h,i);if(n%3==0)printf("\n");}}}}}}}}}}}}附錄4(Mathematica程序，fulu4.nb)：Timing[(*a+b=c,d+e=f,g+h=i0*)Clear[n,a,b,c,d,e,f,g,h,i];n=0;For[a