一筆畫問(wèn)題程序解法新探

1、一筆畫問(wèn)題程序解法新探1736年瑞士數(shù)學(xué)家列昂哈德·歐拉發(fā)表了圖論的第一篇論文“哥尼斯堡七橋問(wèn)題”這個(gè)問(wèn)題是這樣的：哥尼斯城市有一條橫貫全城的普雷格爾河，城的各部分用七座橋聯(lián)接，每逢假日，城市的居民進(jìn)行環(huán)城逛游，這樣就產(chǎn)生了一個(gè)問(wèn)題，能不能設(shè)計(jì)一個(gè)次“遍游”，使得從某地出發(fā)，對(duì)每一座跨河橋只走一次，而在遍歷了七橋之后卻又能回到原地由哥尼斯堡七橋問(wèn)題又引出了一個(gè)類似的一筆畫問(wèn)題：一個(gè)圖能否從一個(gè)頂點(diǎn)出發(fā)不間斷地畫出，使得該圖的每條邊經(jīng)過(guò)并且只經(jīng)過(guò)一次，該問(wèn)題經(jīng)過(guò)歐拉證明得到如下定理：一個(gè)圖能夠一筆畫出，并且每遍經(jīng)過(guò)一次且只經(jīng)過(guò)一次，當(dāng)且僅當(dāng)該圖是連通的，并且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)所謂奇

2、數(shù)度結(jié)點(diǎn)，指的是經(jīng)過(guò)一個(gè)結(jié)點(diǎn)的邊有奇數(shù)條，否則為偶數(shù)度結(jié)點(diǎn)我們以圖為例來(lái)說(shuō)明一筆畫問(wèn)題算法：第一步：將圖轉(zhuǎn)化成矩陣，然后再轉(zhuǎn)化成計(jì)算機(jī)所能識(shí)別的表示方式，即用二數(shù)組來(lái)表示該圖用矩陣表示是：010111101010A =010111101011111100101100這是一個(gè)關(guān)于主對(duì)角線對(duì)的矩陣，矩陣中行數(shù)與列數(shù)均表示頂點(diǎn)的編號(hào)，如果i個(gè)頂點(diǎn)與第j個(gè)頂點(diǎn)之間有一條邊，則分別將A（i，j）與A（j，i）均置為1，否則置為0，如：第一個(gè)頂點(diǎn)與第二個(gè)頂點(diǎn)之間有一條邊，則將A（1，2）與A（2，1）均置為1，第五個(gè)頂點(diǎn)與第六個(gè)頂點(diǎn)之間沒(méi)有邊，則將A（5，6）與A（6，5）均置為0，其余以此類推第二步：求

3、出每個(gè)頂點(diǎn)的度，從中找出奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)，所謂頂點(diǎn)的度指的是與某個(gè)頂點(diǎn)有一條邊的頂點(diǎn)個(gè)數(shù)；用B（I）表示第I個(gè)結(jié)點(diǎn)的度數(shù)，則B（I）=A（I，1）+ A（I，2）+ + A（I，N），Num表示奇數(shù)度結(jié)點(diǎn)的個(gè)數(shù)，Num的值為B（1）、B（2）B（n）中奇數(shù)的個(gè)數(shù)之和第三步：若B（I）=0，則從任一結(jié)點(diǎn)開(kāi)始遍歷，若B（I）=2，則從其中一個(gè)奇數(shù)度結(jié)點(diǎn)開(kāi)始遍歷，將遍歷的第一個(gè)頂點(diǎn)編號(hào)送往t，打印t，否則該圖無(wú)法一筆畫，并結(jié)束第四步：以T號(hào)頂點(diǎn)為起點(diǎn)，從A（T，1），A（T，2），A（T，n）中找到一個(gè)值為1的數(shù)組元素A（T，J），將A（T，J）均置為1，B（J）與B（T）均自減1，將J=>T

4、，打印T第五步：判斷B（T）是否為0，則結(jié)束。否則轉(zhuǎn)到第四步重復(fù)執(zhí)行程序流程圖如下：初始化輸入NI=1··NJ=1··NREAD A (I，J)NI=1··NB（I）=0J=1··NB（I）=B（I）+A（I，J）B（I） MOD2<>0NUM=NUM+1YI=1顯示“不能一筆畫”B（I） MOD2<>0I=I+1NUM<>0且NUM<>2YT=INPRINT TJ<=NB（T）<>0J=1YA（J，T）=1NYYNA（T，J）=0B（T）=B（T）

5、-1J=J+1打印JA（T，J）=0PRINT結(jié)束B(niǎo)（J）=B（J）-1T=J以下是用兩種不同的語(yǔ)言編寫的程序QBASIC程序如下：NUM=0INPUT “N=”;NDIM A(N,N) B(N)FOR I=1 TO NFOR J=1 TO NREAD A (I,J)NEXT J,IFOR I=1 TO NB(I)=0FOR J=1 TO NB(I)=B(I)+A(I,J)NEXT JIF B(I) MOD 2<>0 THEN NUM=NUM+1NEXT IIF NUM<>0 AND NUM<>2 THET “不能一筆畫”；GOTO 100I=1WHILE

6、B(I) MOD 2=0I=I+1WENDT=I80 WHILE B(T) <> 0PRINT T:”J=1WHILE J <= NIF A(T,J)=1 THENA(T,J)=0A(T,J)=0B(T)=B(T)-1B(J)=B(J)-1T=JGOTO 80ELSEWENDWENDPRINT T100 ENDDATA<N*N個(gè)數(shù)據(jù)>Turbo Pascal程序如下：PROGRAM exam (input, output)LABEL abc, acb;Const n=6;Var num, i, j, t: integerA: array1.n,1.n of int

7、egerB: array1.n of integerBEGINNum: =0;For i: =1 to n doFor j: =1 to n doRead (Ai,j);For i: =1 to n doBeginBj:=0;For j: =1 to n doBi: =Bi+Ai,j;IF Bi mod 2 <> 0 then num: =num+1End;If num 0 <> and num <> 2 thenBeginWriteln (“不能一筆畫”)；Goto abcEnd;i: =1;While Bi mod 2 = 0 doi: =i+1;t: =i;acb;While Bt 0 doBeginwrite (t); write (“”)；i: =1;while j<=n doIf a t,