程序開(kāi)發(fā)和結(jié)構(gòu)化程序設(shè)計(jì)

1、第九章 程序開(kāi)發(fā)和結(jié)構(gòu)化程序設(shè)計(jì),良好的行文格式自頂向下逐步求精的程序設(shè)計(jì)技術(shù)受限排列組合——窮舉法與試探法本章小結(jié)作業(yè),良好的行文格式,程序的行文格式不好直接影響程序的可讀性、清晰性和外觀。,/* A */ #include int i;main (){i=25+38;printf(“25+38=%d”,i);}/* B */ #include

2、 int i;main () { i = 25+38; printf ( “25+38=%d” , i

3、 );}/* C */ #include int i; /* 聲明整型變量i */ int main (void) { /* 主函數(shù) */ i = 25+38;

4、 /* 求和運(yùn)算 */ printf ( “25+38=%d” , i ); /* 打印 */ },,,if ( b ) S1 else S2,switch ( expr ) { case a1: S1 case a2: S2 ... case an:

5、 sn } /* switch */,圖1 函數(shù)定義 圖2 IF語(yǔ)句 圖3 SWITCH語(yǔ)句,int main ( vido ) { DS DS ... } /* main */,do{ S }while (b),for(expr1;expr2;expe3){ S} /* for */,while ( b

6、) { S } /* while */,圖4 WHILE語(yǔ)句 圖5 FOR語(yǔ)句 圖6 DO語(yǔ)句,用合適的助記名來(lái)命名標(biāo)識(shí)符,注釋,自頂向下逐步求精的程序設(shè)計(jì)技術(shù),自頂向下、逐步求精若想讓計(jì)算機(jī)解題必須用清晰而無(wú)兩義性的方式給它提供算法。要求：找出一個(gè)算法，它能提供所解問(wèn)題的從輸入到輸出所需的映象。選擇一種程序語(yǔ)言寫(xiě)出程序，用計(jì)算機(jī)能接受的方式表述算

7、法。關(guān)鍵是如何找出算法。因?yàn)閷?xiě)出程序，只是表述算法，應(yīng)該沒(méi)有困難。,求精實(shí)例,測(cè)定字母偶的出現(xiàn)頻率三個(gè)齒輪嚙合問(wèn)題驗(yàn)證三角形外心定理,,編程序，測(cè)定字母偶的出現(xiàn)頻率,測(cè)定小寫(xiě)字符串中相鄰字母偶出現(xiàn)頻率。例如，針對(duì)the cat對(duì)th 、he 、ca 、at計(jì)數(shù)。設(shè)有說(shuō)明： int conmat[26][26] ;字母偶 he 的出現(xiàn)次數(shù)存入下標(biāo)變量conmat[‘h'-‘a(chǎn)’

8、]['e'-’a’],首先把該問(wèn)題分解成如下幾步：1）初始化計(jì)數(shù)器數(shù)組conmat ；2）統(tǒng)計(jì)每個(gè)字母偶的出現(xiàn)頻率；3）輸出統(tǒng)計(jì)結(jié)果。,,,,求精上述PAD中的每一個(gè)步驟：初始化數(shù)組conmat ,顯然應(yīng)該一行一行的初始化；對(duì)于每行又應(yīng)該一個(gè)元素一個(gè)元素的初始化。,初始化第c1行,考慮統(tǒng)計(jì)部分： 假設(shè)被統(tǒng)計(jì)的字符串是從終端輸入的，則顯然我們應(yīng)該把該字符串全部讀入，并在讀入的過(guò)程中邊讀邊統(tǒng)計(jì)。用下圖表示

9、。,讀 ( prevchar ),while(!EOF),統(tǒng)計(jì)一次,,,def,讀(thischar),,,再考慮具體統(tǒng)計(jì)算法，為統(tǒng)計(jì)字母偶的出現(xiàn)頻率，顯然在讀入字符串的過(guò)程中應(yīng)該始終保存兩個(gè)字符 prevchar 、thischar ，并且當(dāng)該兩個(gè)字符都是字母時(shí)，相應(yīng)計(jì)數(shù)單元加1；最后在讀入下一個(gè)字符之前還應(yīng)該把保存的兩個(gè)字符向前串。,最后考慮輸出部分, 我們把結(jié)果輸出成兩個(gè) 26×13 的表，每個(gè)表元素是相應(yīng)字母偶的出現(xiàn)次

10、數(shù)：* a b c d e ... mab ...z* n o p q r ... zab ... z,打印一個(gè)表（第一個(gè)表），顯然應(yīng)該先打印表頭再打印下邊各行,打印表頭,打印表體,,beginch ,endch,打印表頭可以求精成先輸出一個(gè)“*”

11、；再順次輸出各個(gè)字符。順次輸出各個(gè)字符是一個(gè)循環(huán)。,打印表頭,打印表體,,beginch ,endch,,輸出('*'),輸出("\n"),順次輸出各個(gè)字符,打印表體應(yīng)該一行一行的打印，每行應(yīng)該先打印行頭，再打印本行各個(gè)元素；打印本行各個(gè)元素，應(yīng)該一個(gè)元素一個(gè)元素的打印，是一個(gè)循環(huán),打印表體,,beginch ,endch,,輸出('*'),輸出("\n"

12、),輸出一行,輸出(c1),輸出("\n"),,輸出本行各個(gè)元素,,三個(gè)齒輪嚙合問(wèn)題,設(shè)有三個(gè)齒輪互相銜接，求當(dāng)三個(gè)齒輪的某兩對(duì)齒互相銜接后到下一次這兩對(duì)齒再互相銜接，每個(gè)齒輪最少各轉(zhuǎn)多少圈。解:這是求最小公倍數(shù)的問(wèn)題。每個(gè)齒輪需轉(zhuǎn)圈數(shù)是三個(gè)齒輪齒數(shù)的最小公倍數(shù)除以自己的齒數(shù)。設(shè)三個(gè)齒輪的齒數(shù)分別為:na、nb、nc ；嚙合最小圈數(shù)分別為:ma、mb、mc ；三齒輪齒數(shù)的最小公倍數(shù)為k3 。,計(jì)算步驟表示為

13、：,讀入三齒輪齒數(shù)和輸出結(jié)果，分別只是一次調(diào)用讀或?qū)懞瘮?shù)，不必求精。,求精計(jì)算三齒數(shù)的最小公倍數(shù)k3 ?？梢园言搯?wèn)題分解成 先求兩個(gè)齒數(shù)na與nb的最小公倍數(shù)k2 ， 然后再求k2與第三個(gè)齒數(shù) nc 的最小公倍數(shù)k3 ， k3即為na、nb、nc三個(gè)齒輪齒數(shù)的最小公倍數(shù)。設(shè)已經(jīng)有求兩個(gè)數(shù)的最小公倍數(shù)的函數(shù) int lowestcm( int x, int y )則該

14、求精過(guò)程可表示成 。,求精求兩個(gè)數(shù)的最小公倍數(shù)的函lowestcm 。 x、y的最小公倍數(shù)是x、y 的積除以x、y 的最大公約數(shù)。設(shè)已經(jīng)有求兩個(gè)數(shù)的最大公約數(shù)的函數(shù) int gcd(int x, int y)則該求精過(guò)程可表示成：,采用展轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)，函數(shù)int gcd(int x, int y)定義如下,函數(shù)gcd是一個(gè)遞歸函數(shù)，先采用分支求精過(guò)程、再采用遞歸求精過(guò)程，可以求精成下圖,最

15、后，分別計(jì)算嚙合的最小圈數(shù)可以被求精成下圖 。,,驗(yàn)證三角形外心定理,三角形三條邊的垂直平分線(xiàn)交于一點(diǎn)，該點(diǎn)是三角形外接圓的圓心。解：不失一般性，假設(shè)三角形的任意一條邊都不平行于任意一個(gè)坐標(biāo)軸。依據(jù)平面幾何知識(shí)，該問(wèn)題的驗(yàn)證步驟應(yīng)該是：讀入三點(diǎn)a,b,c的坐標(biāo)(x1,y1)、(x2,y2)、(x3,y3)；檢驗(yàn)三點(diǎn)是否構(gòu)成一個(gè)三角形；若三點(diǎn)構(gòu)成三角形，則驗(yàn)證外心定理 。,讀入三點(diǎn)坐標(biāo)只是一個(gè)讀語(yǔ)句，不必求精 ，下邊求精檢驗(yàn)是否

16、三角形和驗(yàn)證外心定理。,檢驗(yàn)三點(diǎn)是否構(gòu)成三角形使用一個(gè)bool型函數(shù)isTriange ，可以求精成：求兩點(diǎn)p1,p2確定的直線(xiàn)方程L12 ；判斷若p3在L12上，則 isTriange 為false ，否則isTriange為true 。,求兩點(diǎn)間直線(xiàn)方程可以寫(xiě)一個(gè)函數(shù) line(x1,y1,x2,y2, *a,*b )并求精成下圖 。,驗(yàn)證外心定理可以如下進(jìn)行： 求每條邊的垂直平分線(xiàn)； 驗(yàn)證該三條

17、直線(xiàn)是否交于一點(diǎn)； 若交于一點(diǎn)， 則驗(yàn)證該點(diǎn)到三角形各頂點(diǎn)距離是否相等否則 錯(cuò)誤命題。,求每條邊的垂直平分線(xiàn)方程可以寫(xiě)一個(gè)求一條線(xiàn)段的垂直平分線(xiàn)方程的函數(shù)，然后分別三次調(diào)用該函數(shù) 。,求一條邊的垂直平分線(xiàn)方程可以先調(diào)用前述函數(shù) line，求該邊的直線(xiàn)方程;再求該邊的中點(diǎn),然后求過(guò)該中點(diǎn)的與該邊垂直的直線(xiàn)方程，得下圖,驗(yàn)證該三條直線(xiàn)是否交于一點(diǎn)編成一個(gè)函數(shù)isOnePoint ，可以先求兩條直線(xiàn)的交點(diǎn)，然后再判斷第三

18、條直線(xiàn)是否過(guò)該點(diǎn)。,設(shè)有一個(gè)函數(shù) distance (x1,y1,x2,y2)可以計(jì)算兩點(diǎn)間距離，驗(yàn)證三條垂直平分線(xiàn)的交點(diǎn)到三角形各頂點(diǎn)距離是否相等，是一個(gè)布爾表達(dá)式。,,受限排列組合——窮舉法與試探法,有這樣一類(lèi)問(wèn)題，從若干元素的所有排列(或組合)中選取符合某種條件的一些排列(或組合)。八皇后問(wèn)題Debruijn 問(wèn)題,八皇后問(wèn)題,這是一個(gè)古老而有趣的游戲。高斯(C.F.Gauss)最早在1850年提出并研究過(guò)這個(gè)

19、問(wèn)題，但是沒(méi)有完全解決。該問(wèn)題是：在一個(gè)8*8格的國(guó)際象棋棋盤(pán)上放置八個(gè)皇后，使任意兩個(gè)皇后都不能互相攻擊。 按國(guó)際象棋規(guī)則，兩個(gè)皇后可以互相攻擊。若在同一行上，或在同一列上,或在同一條斜線(xiàn)上（包括左高右低、右高左低）,如圖放置的八個(gè)皇后便不能互相攻擊。編程序, 求出所有符合要求的布局。共有92種滿(mǎn)足條件的布局，若除去對(duì)稱(chēng)的等類(lèi)同布局, 完全不同者有12種。這里不考慮剔除類(lèi)同布局，求出全部92種布局。,解這類(lèi)問(wèn)題有兩

20、條途徑: 1. 窮舉法; 2. 試探法。下邊以八皇后問(wèn)題為例，分別介紹這兩種方法。,在具體介紹這兩種方法之前，先考慮八皇后問(wèn)題的表示方法。用一個(gè)一維數(shù)組表示棋盤(pán)。A[i]表示棋盤(pán)的第i列，若A[i]中存放有數(shù)k表示第i列中第k行上放置了皇后。例: A[3]=6表示在棋盤(pán)的第3列第6行上放置一個(gè)皇后。A[0]是根據(jù)下邊算法的需要, 多設(shè)的一個(gè)元素。,八皇后 窮舉法,本方法思路是，按某種順序枚舉出全部排列或

21、組合。每當(dāng)枚舉出一種排列或組合之后，便用給定條件判斷該種排列或組合是否符合條件。若符合條件，則本種排列或組合被選中，可以輸出或記錄下來(lái)。若不符合條件，則把本種排列或組合舍掉。 八個(gè)皇后的排列問(wèn)題，最簡(jiǎn)單的方法是八重循環(huán)，可以編出如下窮舉法程序。 在下述算法中，用到檢驗(yàn)函數(shù)check與輸出函數(shù)out。為簡(jiǎn)單起見(jiàn)，先省略它們的具體實(shí)現(xiàn)細(xì)節(jié)。,int main(void){ int a[9] ，i1,

22、i2,i3,i4,i5,i6,i7,i8 ; for ( i1=1; i1<=8; i1++ ) for ( i2=1; i2<=8; i2++ ) for ( i3=1; i3<=8; i3++ ) for ( i4=1; i4<=8; i4++ )

23、 for ( i5=1; i5<=8; i5++ ) for ( i6=1; i6<=8; i6++ ) for ( i7=1; i7<=8; i7++ )

24、 for ( i8=1; i8<=8; i8++ ) { a[1] = i1 ; a[2] = i2 ; a[3] = i3 ; a[4] = i4 ;

25、 a[5] = i5 ; a[6] = i6 ; a[7] = i7 ; a[8] = i8 ; if ( check() ) out();

26、 } },八皇后 試探法,按規(guī)律，從一滿(mǎn)足條件的初始狀態(tài)出發(fā)，逐步生成滿(mǎn)足條件的子排列, 不斷增加子排列長(zhǎng)度。增加子排列長(zhǎng)度過(guò)程中，每增加一位, 生成一個(gè)子排列后, 便檢驗(yàn)它是否滿(mǎn)足條件。不滿(mǎn)足條件, 則換一個(gè)子排列－即修改當(dāng)前位置滿(mǎn)足條件, 則延長(zhǎng)子排列, 增加子排列長(zhǎng)度。子排列的長(zhǎng)度滿(mǎn)足要求長(zhǎng)度,便找到了一個(gè)解。若要求找一個(gè)解即可，這時(shí)便可以結(jié)束。若要求找所有解，這時(shí)可以輸出或記錄本解

27、，然后按前述思路，繼續(xù)修改排列，繼續(xù)試探，找下個(gè)解,在上述試探過(guò)程中, 修改當(dāng)前位置時(shí)：若當(dāng)前位置上還有沒(méi)被試探過(guò)的元素，則應(yīng)該取下一個(gè)沒(méi)被試探過(guò)的元素進(jìn)行試探若當(dāng)前位置上所有元素都被試探過(guò)了，則在當(dāng)前位置上沒(méi)辦法再修改了這說(shuō)明前邊的某個(gè)位置有問(wèn)題，放置的元素不對(duì)，顯然應(yīng)該向回退一位?；厮莺? 原來(lái)的上 一個(gè)位置變成了當(dāng)前位置, 則又變成修改當(dāng)前位置的問(wèn)題了。這時(shí), 同樣還應(yīng)該考慮取下一個(gè)沒(méi)被試探過(guò)的元素進(jìn)行試探, 以及是否所

28、有元素在當(dāng)前位置上都被試探過(guò)了并回溯的問(wèn)題。,如圖所示，設(shè)要生成一個(gè) n 位的串A ；在每個(gè)位置上可選擇的符號(hào)有 K 個(gè)；A 應(yīng)該滿(mǎn)足條件 r ；m表示當(dāng)前試探位置。試探法的算法描述為：1. 初始時(shí)，從第一個(gè)位置開(kāi)始試探，令 m=1 ; 2. 然后在第 m 位逐次取可選符號(hào): B[1],B[2] , ... , B[k] 。對(duì)某一個(gè)B[i]有兩種可能:,若B[i]使A[1],A[2], ... ,A[m]滿(mǎn)足r, 則進(jìn)入

29、A的下一個(gè)位置。 m=m+1,若B[i]不能使A[1],A[2], ... ,A[m]滿(mǎn)足r, 則有兩種情況:i<k ，,若B[i]不能使A[1],A[2], ... ,A[m]滿(mǎn)足r, 則有兩種情況:i<k ，取B中下一個(gè)符號(hào)繼續(xù)試探i=i+1,若i=k 說(shuō)明在當(dāng)前位置上所有符號(hào)都已經(jīng)被試探過(guò),若i=k 說(shuō)明在當(dāng)前位置上所有符號(hào)都已經(jīng)被試探過(guò)應(yīng)該回溯到上一個(gè)位置, 作 m=m-1 后繼續(xù)試探

30、直到找到解、m=0結(jié)束,,*,*,*,,*,*,*,*,*,*,*,*,*,*,*,以四皇后問(wèn)題為例，考察試探過(guò)程：,,上述試探法思想描述成如下PAD:,程序如下: int A[ 9 ] , m ; bool check( int m ) ; /*檢查某格局是否合格的函數(shù) */ void out() ; /* 輸出函數(shù)

31、*/ void change(void) { /* 修正 */ while ( A[m]==8 ) m=m-1 ; A[m]=A[m]+1 ; } void extend(void) { /* 延長(zhǎng) */ m = m+1 ;

32、 A[m] = 1 ; },int main(void) { /* 主程序 */ A[0] = 0 ; A[1] = 1 ; m = 1 ; while ( m > 0 ) if ( c

33、heck(m) ) { if ( m==8 ) { out() ; change() ; }

34、 else extend() ; } else change();},從上例可以看出, 窮舉法與試探法的著眼點(diǎn)及主要區(qū)別在于:窮舉法是舉出全部可能的格局，對(duì)每種格局進(jìn)行檢驗(yàn), 使合格者入選，不合格者淘汰。試探法是從初始滿(mǎn)足條件的格局開(kāi)始，逐步前進(jìn)。每前進(jìn)一步都判斷子格局是否合適。若當(dāng)前子格局合適則進(jìn)入

35、下一級(jí); 若當(dāng)前子格局不合適則選同一級(jí)的下一個(gè)子格局; 但是若同級(jí)子格局已全部試探完畢, 則回溯到上一級(jí)直到當(dāng)前子格局夠長(zhǎng)為止。,顯然窮舉法的運(yùn)算量比試探法要大的多。因?yàn)樗紤]一切情況的排列，而試探法可以在中間丟掉大量的不合格排列。 事實(shí)上許多問(wèn)題的窮舉法是不適用的, 八皇后問(wèn)題窮舉法有88種排列，把每一種情況都排出來(lái)，并檢驗(yàn)其是否合格顯然是不可能的。 在上述算法中, 不論是窮舉法還是試探法，都是用循

36、環(huán)迭代的方式給出的解法。循環(huán)程序可以用遞歸來(lái)表示。 不論窮舉法還是試探法都可以寫(xiě)成遞歸形式:,八皇后 窮舉法的遞歸實(shí)現(xiàn),用窮舉法實(shí)現(xiàn)八皇后問(wèn)題, 可以抽象的描述為：在數(shù)組A的8個(gè)位置上分別排列一個(gè)1到8的整數(shù)。設(shè)想, 如果有一個(gè)函數(shù)queen(r)能夠完成 “在數(shù)組A后部的r個(gè)位置（從第8-r+1到8）上, 分別排列一個(gè)1到8的整數(shù)”。 則八皇后問(wèn)題便是 queen(8),“在數(shù)組A后部的r個(gè)位置

37、上, 分別排列一個(gè)1到8的整數(shù)”可以分解成: 先在第8-r+1位上分別排列一個(gè)1到8的整數(shù)；然后再在剩余的后部的r-1個(gè)位置上分別排列一個(gè)1到8的整數(shù)。步驟2便是對(duì)queen的遞歸調(diào)用 queen(r-1)。最后考慮遞歸出口, 顯然應(yīng)該在 r=1 時(shí)檢驗(yàn)輸出并退出遞歸。由此得遞歸實(shí)現(xiàn)八皇后問(wèn)題的窮舉算法及遞歸程序,int A[ 9 ] ; bool check(); /* 檢查某格局是否合

38、格的函數(shù), 分程序略 */ void out() ; /* 輸出函數(shù), 分程序略 */ void queen( int r ) { int i ; for ( i=1; i1 ) queen(r-1);

39、 else if ( cheek() ) out(); } } int main(void) { queen(8) },八皇后 試探法的遞歸實(shí)現(xiàn),試探方法的思路是，按一定規(guī)律，從某一滿(mǎn)足條件的初始狀態(tài)出發(fā)，逐步試探生成滿(mǎn)足條件的子排列,

40、不斷增加子排列長(zhǎng)度, 直到子排列的長(zhǎng)度滿(mǎn)足問(wèn)題的要求長(zhǎng)度n為止,便找到了一個(gè)解。設(shè)想, 如果有一個(gè)函數(shù)queen(r)能夠“合理的排列數(shù)組A后部的r個(gè)(從第n-r+1到n)元素”并保證序列滿(mǎn)足給定條件, 則八皇后問(wèn)題便是對(duì)queen的調(diào)用 queen(8),“合理的排列數(shù)組A后部的r個(gè)（從第n-r+1到n）元素”可以分解成: 首先在第n-r+1位上排列一個(gè)合格的元素, 然后在合理的排列從n-(r-1

41、)+1開(kāi)始的后部的r-1個(gè)元素。步驟1 “在第n-r+1位上排列一個(gè)合格的元素”，即是把8個(gè)元素順次的排列在第n-r+1位上, 并對(duì)每個(gè)元素檢驗(yàn)是否合格，使合格者入選。步驟2 “合理的排列后部的r-1個(gè)元素” 顯然與 “合理的排列后部的r個(gè)元素”具有相同的特征屬性, 只是排列的元素個(gè)數(shù)減少了,也就是說(shuō)它表現(xiàn)為對(duì)queen的遞歸調(diào)用。,在該算法中, 試探法的 “延長(zhǎng)” 體現(xiàn)在繼續(xù)遞歸調(diào)用上； “修正

42、本位” 體現(xiàn)在從 1 到 8 作 i 的循環(huán)上； “回溯” 則體現(xiàn)在遞歸出口的返回上。,int A[ 9 ] ; bool check( int m ); /*檢查某格局是否合格的函數(shù) */ void out(void) ; /* 輸出函數(shù) */ void queen( int r ) { /* 試探法

43、 */ int i; for ( i=1; i1 ) queen(r-1) ; else out(); } } int main(void)

44、{ /* 主程序 */ queen(8) },分析檢驗(yàn)條件:縱向, 每列只有一個(gè)皇后: 由數(shù)據(jù)結(jié)構(gòu)保證每列只能放一個(gè)皇后。橫向，每行放置一個(gè)皇后: 顯然要求數(shù)組 A 中不能有重復(fù)的數(shù)值。設(shè)當(dāng)前為第m步，由于前m-1步是合格的, 所以只要檢驗(yàn)A[m]不等于所有的 A[1]、... 、A[m-1]。左高右低對(duì)角線(xiàn)(共有2*n-1即15條)：這樣對(duì)角線(xiàn)上不同位置的行列號(hào)之差相等。設(shè)

45、當(dāng)前為第m步，由于前m-1步是合格的，所以只要對(duì)一切i<m檢驗(yàn)：　　　　A[m]-m ≠A[i]-i 。左高右低對(duì)角線(xiàn): 與左高右低對(duì)角線(xiàn)類(lèi)似。只不過(guò)這里該檢查　A[m]+m ≠ A[i]+i 。,試探法檢驗(yàn)函數(shù) check 如下， bool check ( int m ) { int i ; for ( i=1; i<m; i++ ){ if

46、( A[m]==A[i] ) return false ; if ( A[m]-m == A[i]-i ) return false ; if ( A[m]+m == A[i]+i ) return false ; } return true; },窮舉法的檢驗(yàn)函數(shù)應(yīng)該多加一層循環(huán)。 bool check ( )

47、{ int i ,j; for ( i=1; i<8; i++ ){ for(j=i+1;j<=8;j++){ if ( A[j]==A[i] ) return false ; if ( A[j]-j == A[i]-i ) return false ; if ( A[j]+j == A[i]+i

48、 ) return false ; } } return true; },,Debruijn 問(wèn)題,如圖由 ８?jìng)€(gè)二進(jìn)制數(shù)字0、1組成一個(gè)環(huán)。使８ 個(gè)3位的二進(jìn)制數(shù): 000 0　　 001 1 010 2 011 3 100 4　 101 5　110

49、6 111 7正好在環(huán)中各出現(xiàn)一次。本例目前的順序是：0、1、2、5、3、7、6、4 。設(shè)計(jì)生成這樣環(huán)的程序。環(huán)由 2n個(gè)二進(jìn)制數(shù)字組成，恰好包含2n個(gè)互不相同的n位二進(jìn)制數(shù)。,解:還是分別用試探法和窮舉法來(lái)解該題。先考慮環(huán)的表示， 對(duì)任意n ，環(huán)上有2 n個(gè)0、1 。 用一維數(shù)組A保存環(huán)上的數(shù)據(jù)。 A的長(zhǎng)度nn=2 n 。 并且認(rèn)為A[nn-1]與A[0]相接構(gòu)成環(huán)。,De

50、bruijn 問(wèn)題 遞歸實(shí)現(xiàn)窮舉法,int nn,outnum=0 ; // 記錄環(huán)的長(zhǎng)度int A[ 256 ] ; /* 保存環(huán),限制輸入 n 最大為 8 */void next ( int m ) { /* 窮舉 */ int i ; if ( m < nn ) for ( i=0; i<=1; i++ ) {

51、 A[m] = i ; next( m+1 ) ; } else if ( check(nn-1) &&outnum==0){ // 檢驗(yàn)合格 out(); outnum++; }}int main(void) {/* 主程序 */ int n ;

52、 printf(“\n pleace input n=” ) ; scanf( “%d”, &n ) ; /* 輸入n<=8 */ nn=power(n); /* 求nn */ next(0);},Debruijn 問(wèn)題 試探法迭代實(shí)現(xiàn),環(huán)上一定有n個(gè)連續(xù)0組成的n位二進(jìn)制數(shù)0 。作為初值把n個(gè)0放在最前邊，從第m=n位開(kāi)始試探。找到一個(gè)解輸出后，令

53、m=nn , 使循環(huán)終止。算法如圖：,/* PROGRAM Debruijn2 */ /* 聲明部分同前，略 */void extend(int *m){ /* 延長(zhǎng)函數(shù)*/(*m)++;A[*m]=0;}void back(int *m){ /* 修正本位函數(shù) */ while(A[*m]==1) 　　　　　(*m)-

54、- ； 　　　　　/* 回朔 */ A[*m]=1； /* 修正本位 */},int main(void) { int n ,i ; int m; // m 記錄當(dāng)前處理位置。注意m是局部量， // 為了在子程序中修正它，使用指針參數(shù)。 printf(“\n please inp

55、ut n=” ) ; scanf( “%d”, &n ) ; /* 輸入n <=8 */ nn=power(n); /* 求nn */ for ( i=0; i<n; i++ ) A[i]=0; m=n;

56、 /* 以上試探初值 */ while ( m <nn ) if ( check(m) ) if ( m == nn-1 ) { //若A[0]到A[m]正確，且長(zhǎng)度夠 out(); // 輸出

57、 m=nn ; // 退出程序 } else extend(&m)； /* 延長(zhǎng) */ else back(&m);},Debruijn 問(wèn)題 試探法遞歸實(shí)現(xiàn),初始狀態(tài)仍用前 n 個(gè) 0 。從第 n+1 位開(kāi)始遞歸試探 。,/* PROGRAM Debru

58、ijn3 */void next( int m ) { if ( flag ) { /* 試探結(jié)束 */ if ( m<nn ) { A[m]=0; if ( check(m) ) next(m+1) ;/* 延長(zhǎng) */ A[m]=1; /* 修正本位

59、 */ if ( check(m) ) next(m+1) ; /* 延長(zhǎng) */ } else { out() ; flag=false; } }},int main(void) { printf(“\n pleace input n=” ) ; scanf( “%

60、d”, &n ) ; /* 輸入n<=8 */ nn=power(n); /* 求nn=*/ for ( i=0; i<n; i++ ) A[i]=0; /* 以上試探初值 */ flag=true; next(n);},檢驗(yàn)函數(shù) check為了檢驗(yàn)

61、環(huán)上已存在哪些n位二進(jìn)制數(shù)，用一個(gè)數(shù)組B ，保存已檢驗(yàn)過(guò)的互不相同的n位二進(jìn)制數(shù)。check的參數(shù)u為當(dāng)前放入數(shù)組A中的“0、1”個(gè)數(shù)。在窮舉法中用nn作實(shí)在參數(shù)對(duì)應(yīng)該u ，在試探法中用每步試探時(shí)的序列長(zhǎng)度m為實(shí)在參數(shù)對(duì)應(yīng)該u 。,check函數(shù)的兩種情況當(dāng)前所生成環(huán)長(zhǎng)度小于條件u<nn-1A[1]…… A[u]不能構(gòu)成環(huán)當(dāng)前所生成環(huán)長(zhǎng)度滿(mǎn)足條件u=nn-1A[1]…… A[nn-1]沒(méi)有扣圈扣圈,,A[0],A

62、[4],A[1],A[2]下標(biāo)是n-1,A[3],A[6],A[5],,,,,,,,,,,,,,b[0],b[1],b[2],b[3],b[4],A[7],u＝6,,A[0],A[4],A[1],A[2]下標(biāo)是n-1,A[3],A[6],A[5],,,,,,,,,,,,,,,b[0],b[1],b[2],b[3],b[4],b[5],下標(biāo)是(u+1)%nn,b[6],,,b[7],u＝nn-1 A[7],,A[0],A[4],A

63、[1],A[2]下標(biāo)是n-1,A[3],A[6],A[5],u＝nn-1 A[7],,,,,,,,,,,,,,,b[0],b[1],b[2],b[3],b[4],b[5],,v=0,for( i=n-1; i<=u; i++ ),,,return false,A[i-n+1]～A[i]翻譯成 10 進(jìn)制 => k ;,,,,,,,B中有k,B[v]=k; v++,r

64、eturn true,,,,,,u == nn-1,for( i=u+1; i<=u+n-1; i++ ),,return false,A[(i-n+1)%nn]～A[i%nn] 翻譯成 10 進(jìn)制 => k ;,,,,,,B中有k,B[v]=k; v++,int trans( int e , int f ){ /* A[e]～A[f] 翻譯成10進(jìn)制

65、整數(shù) */int kk , j ; kk=0; for ( j=e; j<=f; j++ ) kk = kk*2 + A[j%nn] ; return kk;}bool test_b( int kk, int b[], int v ){ /* 檢驗(yàn)b[0] ～b[v]中有kk */ int j ; for ( j