程序設(shè)計(jì)實(shí)習(xí)(II)：算法設(shè)計(jì)-第15講-遞歸

1、程序設(shè)計(jì)實(shí)習(xí)程序設(shè)計(jì)實(shí)習(xí)(II)(II)：算法設(shè)計(jì)：算法設(shè)計(jì)- -第第1515講講- -遞歸遞歸2主要內(nèi)容主要內(nèi)容n遞歸遞歸p基本思想基本思想p關(guān)鍵問題關(guān)鍵問題n小游戲小游戲 (POJ2802)n棋盤分割棋盤分割 (POJ1191) n開關(guān)網(wǎng)絡(luò)開關(guān)網(wǎng)絡(luò)3給定給定n n，求階乘，求階乘n! n!#include int Factorial(int n) if (n = 0) return 1; else return n * Factorial(n - 1);求階乘的遞歸程序求階乘的遞歸程序4 主程序輸入?yún)?shù)為44*Factorial(3)輸入?yún)?shù)為3 3*Factorial(2)輸入?yún)?shù)為2

2、2*Factorial(1)輸入?yún)?shù)為1 1*Factorial(0)輸入?yún)?shù)為0 Factorial(0) 返回值為1返回值為6返回值為24階乘的棧階乘的棧返回值為2返回值為15遞歸的基本思想遞歸的基本思想n什么是遞歸什么是遞歸p遞歸是指某個(gè)函數(shù)直接或間接的調(diào)用自身。p問題的求解過程就是劃分成許多相同性質(zhì)的子問題的求解，而小問題的求解過程可以很容易的求出，這些子問題的解就構(gòu)成了原問題的解。n總體思想總體思想p待求解問題的解輸入變量x的函數(shù)f(x)p通過尋找函數(shù)g( )，使得f(x) = g(f(x-1)p且已知f(0)的值，就可以通過f(0)和g( )求出f(x)的值n推廣推廣p擴(kuò)展到多個(gè)輸

3、入變量x,y,z等，x-1也可以推廣到 x - x1，只要遞歸朝著“出口”的方向即可6n枚舉枚舉: 把一個(gè)問題劃分成一組子問題, 依次對(duì)這些子問題求解p子問題之間是橫向的、同類的橫向的、同類的關(guān)系n遞歸遞歸: 把一個(gè)問題逐級(jí)分解成子問題p子問題與原問題之間是縱向的、同類的縱向的、同類的關(guān)系p語法形式上：在一個(gè)函數(shù)的運(yùn)行過程中，調(diào)用這個(gè)函數(shù)自己l直接調(diào)用：在fun()中直接執(zhí)行fun()l間接調(diào)用：在fun1()中執(zhí)行fun2()；在fun2()中又執(zhí)行fun1()遞歸與枚舉的區(qū)別遞歸與枚舉的區(qū)別7遞歸的三個(gè)要點(diǎn)遞歸的三個(gè)要點(diǎn)n遞歸式遞歸式：如何將原問題劃分成子問題。n遞歸出口遞歸出口：遞歸終止

4、的條件，即最小子問題的求解，可以允許多個(gè)出口。n界函數(shù)界函數(shù)：?jiǎn)栴}規(guī)模變化的函數(shù)，它保證遞歸的規(guī)模向出口條件靠攏8遞歸解決問題的關(guān)鍵遞歸解決問題的關(guān)鍵n1) 找出遞推公式找出遞推公式n2) 找到遞歸終止條件找到遞歸終止條件n注意事項(xiàng)：注意事項(xiàng)：由于函數(shù)的局部變量是存在棧上的，如果有體積大的局部變量，比如數(shù)組，而遞歸層次又可能很深的情況下，也許會(huì)導(dǎo)致棧溢出，因此可以考慮使用全局?jǐn)?shù)組或動(dòng)態(tài)分配數(shù)組9POJ2802 小游戲小游戲n問題描述問題描述p一天早上，你起床的時(shí)候想“我編程序這么牛，為什么不能靠這個(gè)賺點(diǎn)小錢呢？”因此你決定編寫一個(gè)小游戲。p游戲在一個(gè)分割成w * h個(gè)正方格子的矩形板上進(jìn)行。如

5、圖所示，每個(gè)正方格子上可以有一張游戲卡片，當(dāng)然也可以沒有。p當(dāng)下面的情況滿足時(shí)，我們認(rèn)為兩個(gè)游戲卡片之間有一條路徑相連：路徑只包含水平或者豎直的直線段。路徑不能穿過別的游戲卡片。但是允許路徑臨時(shí)的離開矩形板。10n下面是一個(gè)例子：n這里在 (1, 3)和 (4, 4)處的游戲卡片是可以相連的。而在 (2, 3) 和 (3, 4) 處的游戲卡是不相連的，因?yàn)檫B接他們的每條路徑都必須要穿過別的游戲卡片。你現(xiàn)在要在小游戲里面判斷是否存在一條滿足題意的路徑能連接給定的兩個(gè)游戲卡片11n輸入輸入p輸入包括多組數(shù)據(jù)。一個(gè)矩形板對(duì)應(yīng)一組數(shù)據(jù)。每組數(shù)據(jù)包括的第一行包括兩個(gè)整數(shù)w和h (1 = w, h = 7

6、5)，分別表示矩形板的寬度和長(zhǎng)度。下面的h行，每行包括w個(gè)字符，表示矩形板上的游戲卡片分布情況。使用X表示這個(gè)地方有一個(gè)游戲卡片；使用空格表示這個(gè)地方?jīng)]有游戲卡片。p之后的若干行上每行上包括4個(gè)整數(shù)x1, y1, x2, y2 (1 = x1, x2 = w, 1 = y1, y2 = h)。給出兩個(gè)卡片在矩形板上的位置(注意：矩形板左上角的坐標(biāo)是(1, 1)。輸入保證這兩個(gè)游戲卡片所處的位置是不相同的。如果一行上有4個(gè)0，表示這組測(cè)試數(shù)據(jù)的結(jié)束。p如果一行上給出w = h = 0，那么表示所有的輸入結(jié)束了。12n輸出輸出p對(duì)每一個(gè)矩形板，輸出一行“Board #n:”，這里n是輸入數(shù)據(jù)的編號(hào)

7、。p然后對(duì)每一組需要測(cè)試的游戲卡片輸出一行。這一行的開頭是“Pair m: ”，這里m是測(cè)試卡片的編號(hào)（對(duì)每個(gè)矩形板，編號(hào)都從1開始）。接下來，如果可以相連，找到連接這兩個(gè)卡片的所有路徑中包括線段數(shù)最少的路徑，輸出“k segments.”，這里k是找到的最優(yōu)路徑中包括的線段的數(shù)目；如果不能相連，輸出“impossible.”。p每組數(shù)據(jù)之后輸出一個(gè)空行。13n樣例輸入樣例輸入 5 4 XXXXX X X XXX X XXX 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0 0 0 n樣例輸出樣例輸出 Board #1: Pair 1: 4 segments. Pair 2: 3

8、 segments. Pair 3: impossible. 14問題分析問題分析 (1)n一個(gè)迷宮求解問題，自相似性表現(xiàn)在每走一步的探測(cè)方式相同，可以用遞歸算法求解。n通過窮舉方式找到從起點(diǎn)到終點(diǎn)的路徑，朝一個(gè)方向走下去，如果走不通，則換個(gè)方向走；四個(gè)方向都走不通，則回到上一步的地方，換個(gè)方向走；依次走下去，直到走到終點(diǎn)。n計(jì)算路徑數(shù)目：普通迷宮問題的路徑數(shù)目是經(jīng)過的格子數(shù)目，而該問題路徑只包含水平或者豎直的直線段，所以需要記錄每一步走的方向，如果上一步走的方向和這一步走的方向相同，遞歸搜索時(shí)路徑數(shù)不變，否則路徑數(shù)加1。15問題分析問題分析 (2)(1,3)(2,3)(5,3)(3,4)(4

9、,4)路徑只包含水平或者豎直的直線段。路徑不能穿過別的游戲卡片。但是允許路徑臨時(shí)的離開矩形板。所以在矩形板最外層增加一圈格子，路徑可以通過這些新增加的格子。16問題分析問題分析 (3)n描述迷宮：描述迷宮：1、設(shè)置迷宮為二維數(shù)組board，數(shù)組的值是：空格：代表這個(gè)地方?jīng)]有游戲卡片X：代表這個(gè)地方有游戲卡片2、在搜索過程中,用另外一個(gè)二維數(shù)mark標(biāo)記格子是否已經(jīng)走過了。 markij=0/格子（i，j）未走過 markij=1/格子（i，j）已經(jīng)走過3、int int minstep, w, h；/全局變量/minstep，記錄從起點(diǎn)到達(dá)終點(diǎn)最少路徑數(shù)，初始化為一個(gè)很大的數(shù)。/w,h矩形板的

10、寬度和高度17X XX XX XX XX XX XX XX XX XX XX XX XX X問題分析問題分析 (4)18n設(shè)置搜索方向順序是東、南、西、北(x,y)(x-1,y)(x,y-1)(x,y+1)(x+1,y)東北int to42 = 0,1,1,0,0,-1,-1,0;/now_x,now_y,當(dāng)前位置 /x,y下一步位置for(i = 0;i -1) & (x -1) & (y -1) & (x -1) & (y h + 2) & (boardyx = ) & (markyx = false) | (x = end_x) &

11、 (y = end_y) & (boardyx = X)20遞歸方法遞歸方法n構(gòu)造遞歸函數(shù)構(gòu)造遞歸函數(shù) void Search(int now_x, int now_y, int end_x, int end_y, int step, int f) ; /now_x, now_y當(dāng)前位置 /end_x,end_y結(jié)束位置 /step已經(jīng)走過的路徑數(shù)目 /f從上一步走到(now_x,now_y)時(shí)的方向 21參考程序參考程序#include #include #define MAXIN 75char boardMAXIN + 2MAXIN + 2; /定義矩形板int minstep,

12、w, h, to42 = 0,1,1,0,0,-1,-1,0; /定義方向bool markMAXIN + 2MAXIN + 2; /定義標(biāo)記數(shù)組void Search(int now_x, int now_y, int end_x, int end_y, int step, int f)if(step minstep) return; /當(dāng)前路徑數(shù)大于minstep，返回優(yōu)化策略if(now_x = end_x & now_y = end_y) /到達(dá)終點(diǎn) if（minstep step) /更新最小路徑數(shù)minstep = step;return; 22for(int i = 0;

13、i -1) & (x -1) & (y h + 2) & (boardyx = ) & (markyx = false)|(x=end_x) & (y = end_y) & (boardyx = X) /如果新位置有效markyx = true;/標(biāo)記該位置已經(jīng)經(jīng)過 /上一步方向和當(dāng)前方向相同， /則遞歸搜索時(shí)step不變，否則step+1if(f = i) Search(x, y, end_x, end_y, step, i);else Search(x, y, end_x, end_y, step + 1, i);markyx = false

14、; /回溯，該位置未曾走過 23int main()int Boardnum = 0;while(scanf(“%d %d”, &w, &h) /讀入數(shù)據(jù)if(w = 0 & h = 0)break;Boardnum +;printf(Board #%d:n, Boardnum);int i, j;for (i = 0;i MAXIN + 2;i +)board0i = boardi0 = ;for(i = 1;i = h;i +) /讀入矩形板的布局getchar();for(j = 1;j = w;j +)boardij = getchar();/在矩形板最外層增加

15、一圈格子for (i = 0;i = w;i +)boardh + 1i + 1 = ;for (i = 0;i 0) /讀入起點(diǎn)和終點(diǎn)count +;minstep = 100000; /初始化minstep為一個(gè)很大的值memset(mark, false, sizeof(mark);/遞歸搜索Search(begin_x, begin_y, end_x, end_y, 0, -1);/輸出結(jié)果if(minstep =16:是否可以走當(dāng)前格子Value&8:是否從當(dāng)前格子向北走Value&4:是否從當(dāng)前格子向西走Value&2:是否從當(dāng)前格子向南走Value&

16、;1:是否從當(dāng)前格子向東走FTNWSE27POJ1191: 棋盤分割棋盤分割n將一個(gè)8*8的棋盤進(jìn)行如下分割：將原棋盤割下一塊矩形棋盤并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了(n-1)次后，連同最后剩下的矩形棋盤共有n塊矩形棋盤。(每次切割都只能沿著棋盤格子的邊進(jìn)行)允許的分割方案不允許的分割方案28n原棋盤上每一格有一個(gè)分值，一塊矩形棋盤的總分為其所含各格分值之和?，F(xiàn)在需要把棋盤按上述規(guī)則分割成n塊矩形棋盤，并使各矩形棋盤總分的均方差最小。均方差 ，其中平均值 ， xi為第i塊矩形棋盤的總分。請(qǐng)編程對(duì)給出的棋盤及n，求出的最小值。21niinxx1niixxn29n輸入輸入

17、 第1行為一個(gè)整數(shù)n (1 n 15)第2行至第9行每行為8個(gè)小于100的非負(fù)整數(shù)，表示棋盤上相應(yīng)格子的分值。每行相鄰兩數(shù)之間用一個(gè)空格分隔n輸出輸出 僅一個(gè)數(shù)，為 （四舍五入精確到小數(shù)點(diǎn)后三位）30n樣例輸入樣例輸入31 1 1 1 1 1 1 31 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 01 1 1 1 1 1 0 3n樣例輸出樣例輸出1.63331問題分析問題分析 (1)2222222222()(2)22iiiiiiixxxx xxxx xnxxnxnx

18、xnx如右式，若要求出最小方差，只需要求出最小的 21niinxx211212112121121221212222nxnxnxxxxnxxxxnxxxxnxxnxxniiniininiiniininiiniiniiiniiniiniix1232問題分析問題分析 (2)n設(shè)fun(n,x1,y1,x2,y2)為以(x1, y1)為左上角，(x2, y2)為右下角的棋盤分割成n份后的最小平方和。n那么fun(n,x1,y1,x2,y2)=其中fun(1,x1,y1,x2,y2)等于該棋盤內(nèi)分?jǐn)?shù)和的平方且當(dāng)x2-x1+y2-y1+2n 時(shí)，fun(n,x1,y1,x2,y2)= +2 112 112

19、 112 11minmin(1, 1, 1, , 2)(1,1, 1, 2, 2),min(1, 1, 1, , 2)(1,1, 1, 2, 2),min(1, 1, 1, 2, )(1, 1,1, 2, 2),min(1, 1, 1, 2, )(1xi xxi xyi yyi yfun nxy i yfuniy xyfunxy i yfun niy xyfun nxy xifunx ixyfunxy xifun n , 1,1, 2, 2)x ixy33n只想到這個(gè)還不夠，TLE！n對(duì)于某個(gè)fun(n,x1,y1,x2,y2)來說，可能使用多次這個(gè)值，所以每次都計(jì)算太消耗時(shí)間n解決辦法：記錄

20、表p用resnx1y1x2y2來記錄fun(n,x1,y1,x2,y2)p res初始值統(tǒng)一為-1p當(dāng)需要使用fun(n,x1,y1,x2,y2)時(shí)，查看resnx1y1x2y2n如果為-1，那么計(jì)算fun(n,x1,y1,x2,y2)，并保存于resnx1y1x2y2n如果不為-1，直接返回resnx1y1x2y2問題分析問題分析 (3)34int s99;/每個(gè)格子的分?jǐn)?shù)int sum99;/(1,1)到(i,j)的矩形的分?jǐn)?shù)之和int res159999;/fun的記錄表int calSum(int x1,int y1,int x2,int y2)/(x1,y1)到(x2,y2)的矩形的

21、分?jǐn)?shù)之和return sumx2y2-sumx2y1-1-sumx1-1y2+sumx1-1y1-1; 參考程序參考程序35int fun(int n,int x1,int y1,int x2,int y2) int t,a,b,c,e,MIN=10000000; if(resnx1y1x2y2 !=-1) return resnx1y1x2y2;if(n=1) t=calSum(x1,y1,x2,y2); resnx1y1x2y2=t*t; return t*t; 36 for(a=x1;at) MIN=t; for(b=y1;bt) MIN=t; resnx1y1x2y2=MIN; ret

22、urn MIN; 37int main() memset(sum ,0 ,sizeof(sum); memset(res ,-1 ,sizeof(res); /初始化記錄表int n; cinn; for (int i=1;i9;i+) for (int j=1,rowsum=0;jsij; rowsum +=sij; sumij += sumi-1j + rowsum; double result = n*fun(n,1,1,8,8)-sum88*sum88; coutsetiosflags(ios:fixed)setprecision(3)sqrt(result/(n*n)endl; re

23、turn 0;38存儲(chǔ)空間開銷分析存儲(chǔ)空間開銷分析int res159999;/fun的記錄表 存儲(chǔ)空間開銷105, 有多少空間是永遠(yuǎn)也不會(huì)用的? 可否考慮用SET模板?39開關(guān)網(wǎng)絡(luò)開關(guān)網(wǎng)絡(luò)n問題描述問題描述p小明對(duì)電器與電路極感興趣，是一個(gè)很會(huì)動(dòng)腦筋的人。一天，他在搗弄一塊電路板時(shí)突發(fā)奇想，可否用多個(gè)兩路比較器固化在電路板中，構(gòu)成一個(gè)開關(guān)網(wǎng)絡(luò)，實(shí)現(xiàn)某種格式的數(shù)據(jù)輸出，如用硬件實(shí)現(xiàn)數(shù)據(jù)排序等？p兩路比較器是一個(gè)基本元件，由兩入兩出的比較元件構(gòu)成，如圖：圖1 兩路比較器40n小明于是自己動(dòng)手用若干組兩路比較器和導(dǎo)線組成整個(gè)開關(guān)網(wǎng)絡(luò)。他用這種開關(guān)網(wǎng)絡(luò)求4個(gè)數(shù)的最大值和最小值，如圖：圖2 求最大、最

24、小值圖3 四路開關(guān)網(wǎng)絡(luò)41n上述開關(guān)網(wǎng)絡(luò)可表示為：(1, 2) (2, 3) (3, 4) (1, 2) (2, 3) (1, 2)n用12個(gè)數(shù)簡(jiǎn)單記為1 2 2 3 3 4 1 2 2 3 1 2n受此啟發(fā)，小明在n條線路上安裝了若干個(gè)比較器，想將整個(gè)開關(guān)網(wǎng)絡(luò)變成一個(gè)n位分類網(wǎng)絡(luò)，但他沒有成功，于是就想請(qǐng)你幫助他解決這個(gè)問題。42n輸入輸入從輸入文件讀入若干組測(cè)試數(shù)據(jù)。每一組測(cè)試數(shù)據(jù)的第一行是二個(gè)整數(shù)n, m (0=nyi+1 令k=yi+1則有h(yi)h(yi+1) 根據(jù)h(x)的保序性， h(x1), h(x2) , , h(xN)的輸出是h(y1), h(y2) , , h(yN)

25、因此，如果一個(gè)N輸入的開關(guān)網(wǎng)絡(luò)不是分類網(wǎng)絡(luò)，一定存在一個(gè)0和1構(gòu)成的輸入序列h(x1), h(x2) , , h(xN)，使得其輸出序列h(y1), h(y2) , , h(yN)中存在逆序 反之，對(duì)于一個(gè)N輸入的開關(guān)網(wǎng)絡(luò)，如果對(duì)任意一個(gè)0和1構(gòu)成的輸入序列h(x1), h(x2) , , h(xN)，其輸出序列h(y1), h(y2) , , h(yN)中一定不存在逆序，則該開關(guān)網(wǎng)絡(luò)是分類網(wǎng)絡(luò)49解題思路解題思路 枚舉長(zhǎng)度為N的全部0/1序列, 判斷是否都可正確排序 用遞歸的辦法枚舉,遞歸的深度是N,如此構(gòu)造一個(gè)深度為N的完全二叉樹. 樹上每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)長(zhǎng)度為N的0/1序列 遞歸的出口

26、到達(dá)葉子節(jié)點(diǎn):判斷對(duì)應(yīng)的0/1序列是否可以正確分類(出口1)開關(guān)網(wǎng)絡(luò)在處理前面已經(jīng)達(dá)到的某個(gè)葉子節(jié)點(diǎn)時(shí),不能正確工作(出口2)50n搜索樹搜索樹p考慮2n個(gè)長(zhǎng)為n的0-1序列x1, x2, , xn ，其全體構(gòu)成如下的完全二叉樹?，F(xiàn)只要對(duì)該樹每一支對(duì)應(yīng)的0-1序列，判斷分類網(wǎng)絡(luò)是否合乎排序要求。p實(shí)現(xiàn)過程中，先考慮最左邊的一支，然后逐漸從第n個(gè)數(shù)位開始往前進(jìn)行替換，這實(shí)際上是進(jìn)行回溯操作，只要發(fā)現(xiàn)對(duì)某個(gè)0-1序列，分類網(wǎng)絡(luò)未達(dá)到排序目的，那么結(jié)束搜索。51nn=3時(shí)的搜索過程11111110000000 x1x2x352參考程序參考程序(此程序未考慮出口此程序未考慮出口2)#include using namespace std;#define MAX 5000#define MAXN 100int xMAX, sMAX, tMAX; / x用于存放0-1序列，s和t分別記 /數(shù)據(jù)比較器編號(hào)bool flag;int n, m, k, lev=1;可讀性不好, 最好用一個(gè)對(duì)象表示一個(gè)比較器53void comput (int lev) /遞歸程序，