[理學(xué)]第08章遞歸與搜索上-資料下載頁(yè)
2024-10-16 21:20本頁(yè)面
【正文】 mp。n )!=EOF ) { if( f0[n%8]==0 ) printf( yes\n )。 else printf( no\n )。 } return 0。 } 33 例 分形 (Fractal) 題目來(lái)源： Asia 2021, Shanghai (Mainland China), Preliminary 題號(hào)： ZOJ2423， POJ2083 題目描述： 分形 是存在“自相似”的一個(gè)物體或一種量，從某種技術(shù)角度來(lái)說(shuō)，這種“自相似”是全方位的。 盒形分形 定義如下： 度數(shù)為 1的分形很簡(jiǎn)單，為： X 度數(shù)為 2的分形為： X X X X X 如果用 B(n1)代表度數(shù)為 n1的盒形分形，則度數(shù)為 n的盒形分形可以遞歸 地定義為： B(n1) B(n1) B(n1) B(n1) B(n1) 你的任務(wù)是 輸出度數(shù)為 n的盒形分形 。 34 輸入描述： 輸入文件包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)占一行，包含一個(gè)正整數(shù) n， n≤7。 輸入文件的最后一行為 1，代表輸入結(jié)束 。 第二種輸入方式 !!!!! 輸出描述： 對(duì)每個(gè)測(cè)試數(shù)據(jù)，用符號(hào)“ X”輸出盒形分形。在每個(gè)測(cè)試數(shù)據(jù)對(duì)應(yīng)的輸出之后輸出一個(gè)短劃線(xiàn)符號(hào)“ ”， 在每行的末尾不要輸出任何多余的空格 ，否則得到的是“格式錯(cuò)誤”的結(jié)果。 注意： 這道題目在 ZOJ和 POJ上對(duì)輸出的要求不一樣；在 ZOJ上要求在每行的末尾不要輸出多余的空格，而在 POJ上要求每行的寬度一樣，這樣某些行末尾有若干個(gè)空格。 35 樣例輸出： X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 樣例輸入： 1 2 3 1 36 分析： 首先注意到度數(shù)為 n的盒形分形，其大小是 3n1 3n1。 可以用字符數(shù)組來(lái)存儲(chǔ)盒形分形中各字符。因?yàn)?n≤7， 而 36 = 729，因此可以 定義一字符數(shù)組 Fractal[730][730]來(lái)存儲(chǔ)度數(shù)不超過(guò) 7的盒形分形 。 其次，度數(shù)為 n的盒形分形可以由以下 遞推式子 表示： B(n1) B(n1) B(n) = B(n1) B(n1) B(n1) 37 B(n1) B(n1) B(n) = B(n1) B(n1) B(n1) 因此，可以用一個(gè) 遞歸函數(shù) 來(lái)設(shè)置度數(shù)為 n的盒形分形。假設(shè) 需要在 (startX, startY)位置開(kāi)始設(shè)置度數(shù)為 n的盒形分形 ，它由 5個(gè)度數(shù)為 n1的盒形分形組成，其起始位置分別為： (startX+0, startY+0)、 (startX+2*L0, startY+0)、 (startX+L0, startY+L0)、 (startX+0, startY+2*L0)和 (startX+2*L0, startY+2*L0)， 其中 L0 = 3n2。 該遞歸函數(shù)的 結(jié)束條件 是： 當(dāng) n = 1時(shí)，即度數(shù)為 1的盒形分形，只需在 (startX, startY)位置設(shè)置一個(gè)“ X”字符 。 另外，題目中提到“ 在每行的末尾不要輸出任何多余的空格 ”，因此在字符數(shù)組 Fractal每行最后一個(gè)“ X”字符之后，應(yīng)該設(shè)置串結(jié)束符標(biāo)志 39。\039。 38 include include define MAXSCALE 730 //n為最大值 7時(shí)，分形的大小是 3^6 3^6，而 3^6 = 729 //函數(shù)功能：從 (startX,startY)位置開(kāi)始設(shè)置度數(shù)為 n的盒形分形， //即對(duì)盒形分形中的每個(gè) X， 在字符數(shù)組 Frac的相應(yīng)位置設(shè)置字符 X //其中第 1個(gè)形參為二維數(shù)組名，其第 2維不能省略 void SetFractal( char Frac[ ][730], int startX, int startY, int n ) { if( n==1 ) Frac[startX][startY] = 39。X39。 else { int L0 = (int)pow(3,n2)。 SetFractal( Frac, startX+0, startY+0, n1 )。 SetFractal( Frac, startX+2*L0, startY+0, n1 )。 SetFractal( Frac, startX+L0, startY+L0, n1 )。 SetFractal( Frac, startX+0, startY+2*L0, n1 )。 SetFractal( Frac, startX+2*L0, startY+2*L0, n1 )。 } } 39 int main( ) { int n。 //分形的大小 int i, j。 //循環(huán)變量 char Fractal[MAXSCALE][MAXSCALE]。 while( scanf(%d, amp。n) ) { if( n==1 ) break。 int measure = (int)pow(3,n1)。 //盒形 分形大小 SetFractal( Fractal, 0, 0, n )。 for( i=0。 imeasure。 i++ )//保證每行最后的 39。X39。后是 39。\039。 { int max = 0。 for( j=0。 jmeasure。 j++ ) //找到每行最后的 39。X39。 if(Fractal[i][j]==39。X39。) max = j。 for( j=0。 jmax。 j++ ) //非 39。X39。的位置上為空格 if(Fractal[i][j]!=39。X39。) Fractal[i][j] = 39。 39。 Fractal[i][max+1] = 0。 //在每行最后的 39。X39。后添上 39。\039。 } for( i=0。 imeasure。 i++ ) printf( %s\n, Fractal[i] )。 printf( \n )。 } return 0。 }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1