版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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ǔ)言寫出程序,用計(jì)算機(jī)能接受的方式表述算
7、法。關(guān)鍵是如何找出算法。因?yàn)閷懗龀绦?,只是表述算法,?yīng)該沒(méi)有困難。,求精實(shí)例,測(cè)定字母偶的出現(xiàn)頻率三個(gè)齒輪嚙合問(wèn)題驗(yàn)證三角形外心定理,,編程序,測(cè)定字母偶的出現(xiàn)頻率,測(cè)定小寫字符串中相鄰字母偶出現(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)證三角形外心定理,三角形三條邊的垂直平分線交于一點(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確定的直線方程L12 ;判斷若p3在L12上,則 isTriange 為false ,否則isTriange為true 。,求兩點(diǎn)間直線方程可以寫一個(gè)函數(shù) line(x1,y1,x2,y2, *a,*b )并求精成下圖 。,驗(yàn)證外心定理可以如下進(jìn)行: 求每條邊的垂直平分線; 驗(yàn)證該三條
17、直線是否交于一點(diǎn); 若交于一點(diǎn), 則驗(yàn)證該點(diǎn)到三角形各頂點(diǎn)距離是否相等否則 錯(cuò)誤命題。,求每條邊的垂直平分線方程可以寫一個(gè)求一條線段的垂直平分線方程的函數(shù),然后分別三次調(diào)用該函數(shù) 。,求一條邊的垂直平分線方程可以先調(diào)用前述函數(shù) line,求該邊的直線方程;再求該邊的中點(diǎn),然后求過(guò)該中點(diǎn)的與該邊垂直的直線方程,得下圖,驗(yàn)證該三條直線是否交于一點(diǎn)編成一個(gè)函數(shù)isOnePoint ,可以先求兩條直線的交點(diǎn),然后再判斷第三
18、條直線是否過(guò)該點(diǎn)。,設(shè)有一個(gè)函數(shù) distance (x1,y1,x2,y2)可以計(jì)算兩點(diǎn)間距離,驗(yàn)證三條垂直平分線的交點(diǎn)到三角形各頂點(diǎn)距離是否相等,是一個(gè)布爾表達(dá)式。,,受限排列組合——窮舉法與試探法,有這樣一類問(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ó)際象棋棋盤上放置八個(gè)皇后,使任意兩個(gè)皇后都不能互相攻擊。 按國(guó)際象棋規(guī)則,兩個(gè)皇后可以互相攻擊。若在同一行上,或在同一列上,或在同一條斜線上(包括左高右低、右高左低),如圖放置的八個(gè)皇后便不能互相攻擊。編程序, 求出所有符合要求的布局。共有92種滿足條件的布局,若除去對(duì)稱的等類同布局, 完全不同者有12種。這里不考慮剔除類同布局,求出全部92種布局。,解這類問(wèn)題有兩
20、條途徑: 1. 窮舉法; 2. 試探法。下邊以八皇后問(wèn)題為例,分別介紹這兩種方法。,在具體介紹這兩種方法之前,先考慮八皇后問(wèn)題的表示方法。用一個(gè)一維數(shù)組表示棋盤。A[i]表示棋盤的第i列,若A[i]中存放有數(shù)k表示第i列中第k行上放置了皇后。例: A[3]=6表示在棋盤的第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ī)律,從一滿足條件的初始狀態(tài)出發(fā),逐步生成滿足條件的子排列, 不斷增加子排列長(zhǎng)度。增加子排列長(zhǎng)度過(guò)程中,每增加一位, 生成一個(gè)子排列后, 便檢驗(yàn)它是否滿足條件。不滿足條件, 則換一個(gè)子排列-即修改當(dāng)前位置滿足條件, 則延長(zhǎng)子排列, 增加子排列長(zhǎng)度。子排列的長(zhǎng)度滿足要求長(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)該滿足條件 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]滿足r, 則進(jìn)入
29、A的下一個(gè)位置。 m=m+1,若B[i]不能使A[1],A[2], ... ,A[m]滿足r, 則有兩種情況:i<k ,,若B[i]不能使A[1],A[2], ... ,A[m]滿足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), 使合格者入選,不合格者淘汰。試探法是從初始滿足條件的格局開(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)表示。 不論窮舉法還是試探法都可以寫成遞歸形式:,八皇后 窮舉法的遞歸實(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ī)律,從某一滿足條件的初始狀態(tài)出發(fā),逐步試探生成滿足條件的子排列,
40、不斷增加子排列長(zhǎng)度, 直到子排列的長(zhǎng)度滿足問(wèn)題的要求長(zhǎng)度n為止,便找到了一個(gè)解。設(shè)想, 如果有一個(gè)函數(shù)queen(r)能夠“合理的排列數(shù)組A后部的r個(gè)(從第n-r+1到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ì)角線(共有2*n-1即15條):這樣對(duì)角線上不同位置的行列號(hào)之差相等。設(shè)
45、當(dāng)前為第m步,由于前m-1步是合格的,所以只要對(duì)一切i<m檢驗(yàn): A[m]-m ≠A[i]-i 。左高右低對(duì)角線: 與左高右低對(duì)角線類似。只不過(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)題,如圖由 8?jìng)€(gè)二進(jìn)制數(shù)字0、1組成一個(gè)環(huán)。使8 個(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)度滿足條件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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 介紹一下結(jié)構(gòu)化程序設(shè)計(jì)方法和面向?qū)ο蟪绦蛟O(shè)計(jì)方法的區(qū)別
- 程序設(shè)計(jì)教案 程序設(shè)計(jì)——數(shù)據(jù)結(jié)構(gòu)
- 淺析結(jié)構(gòu)化程序的設(shè)計(jì)技巧
- 下列選項(xiàng)中不屬于結(jié)構(gòu)化程序設(shè)計(jì)方法的是
- 循環(huán)結(jié)構(gòu)程序設(shè)計(jì)
- 順序結(jié)構(gòu)程序設(shè)計(jì)
- 選擇結(jié)構(gòu)程序設(shè)計(jì)
- 基本結(jié)構(gòu)程序設(shè)計(jì)
- vb程序設(shè)計(jì)例題-程序改錯(cuò)程序填空程序設(shè)計(jì)
- 《高級(jí)語(yǔ)言程序設(shè)計(jì)》實(shí)驗(yàn)報(bào)告-循環(huán)結(jié)構(gòu)程序設(shè)計(jì)
- 結(jié)構(gòu)化面試的組織實(shí)施程序
- web程序設(shè)計(jì)課程設(shè)計(jì)--簡(jiǎn)易論壇程序開(kāi)發(fā)
- 五選擇結(jié)構(gòu)程序設(shè)計(jì)
- 語(yǔ)言順序結(jié)構(gòu)程序設(shè)計(jì)
- 順序結(jié)構(gòu)程序設(shè)計(jì)(2)
- 選擇結(jié)構(gòu)程序設(shè)計(jì)實(shí)驗(yàn)
- 四選擇結(jié)構(gòu)程序設(shè)計(jì)
- 初識(shí)python程序設(shè)計(jì)的順序結(jié)構(gòu)和循環(huán)結(jié)構(gòu)
- 實(shí)驗(yàn)4 循環(huán)結(jié)構(gòu)程序設(shè)計(jì)
- pascal 循環(huán)結(jié)構(gòu)的程序設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論