程序設計實習(II)：算法設計-第15講-遞歸

1、程序設計實習程序設計實習(II)(II)：算法設計：算法設計- -第第1515講講- -遞歸遞歸2主要內容主要內容n遞歸遞歸p基本思想基本思想p關鍵問題關鍵問題n小游戲小游戲 (POJ2802)n棋盤分割棋盤分割 (POJ1191) n開關網絡開關網絡3給定給定n n，求階乘，求階乘n! n!#include int Factorial(int n) if (n = 0) return 1; else return n * Factorial(n - 1);求階乘的遞歸程序求階乘的遞歸程序4 主程序輸入參數為44*Factorial(3)輸入參數為3 3*Factorial(2)輸入參數為2

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

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

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

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

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

7、。p然后對每一組需要測試的游戲卡片輸出一行。這一行的開頭是“Pair m: ”，這里m是測試卡片的編號（對每個矩形板，編號都從1開始）。接下來，如果可以相連，找到連接這兩個卡片的所有路徑中包括線段數最少的路徑，輸出“k segments.”，這里k是找到的最優(yōu)路徑中包括的線段的數目；如果不能相連，輸出“impossible.”。p每組數據之后輸出一個空行。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一個迷宮求解問題，自相似性表現在每走一步的探測方式相同，可以用遞歸算法求解。n通過窮舉方式找到從起點到終點的路徑，朝一個方向走下去，如果走不通，則換個方向走；四個方向都走不通，則回到上一步的地方，換個方向走；依次走下去，直到走到終點。n計算路徑數目：普通迷宮問題的路徑數目是經過的格子數目，而該問題路徑只包含水平或者豎直的直線段，所以需要記錄每一步走的方向，如果上一步走的方向和這一步走的方向相同，遞歸搜索時路徑數不變，否則路徑數加1。15問題分析問題分析 (2)(1,3)(2,3)(5,3)(3,4)(4

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

10、寬度和高度17X XX XX XX XX XX XX XX XX XX XX XX XX X問題分析問題分析 (4)18n設置搜索方向順序是東、南、西、北(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,當前位置 /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構造遞歸函數構造遞歸函數 void Search(int now_x, int now_y, int end_x, int end_y, int step, int f) ; /now_x, now_y當前位置 /end_x,end_y結束位置 /step已經走過的路徑數目 /f從上一步走到(now_x,now_y)時的方向 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; /定義標記數組void Search(int now_x, int now_y, int end_x, int end_y, int step, int f)if(step minstep) return; /當前路徑數大于minstep，返回優(yōu)化策略if(now_x = end_x & now_y = end_y) /到達終點 if（minstep step) /更新最小路徑數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;/標記該位置已經經過 /上一步方向和當前方向相同， /則遞歸搜索時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) /讀入數據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) /讀入起點和終點count +;minstep = 100000; /初始化minstep為一個很大的值memset(mark, false, sizeof(mark);/遞歸搜索Search(begin_x, begin_y, end_x, end_y, 0, -1);/輸出結果if(minstep =16:是否可以走當前格子Value&8:是否從當前格子向北走Value&4:是否從當前格子向西走Value&2:是否從當前格子向南走Value&

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

17、 第1行為一個整數n (1 n 15)第2行至第9行每行為8個小于100的非負整數，表示棋盤上相應格子的分值。每行相鄰兩數之間用一個空格分隔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設fun(n,x1,y1,x2,y2)為以(x1, y1)為左上角，(x2, y2)為右下角的棋盤分割成n份后的最小平方和。n那么fun(n,x1,y1,x2,y2)=其中fun(1,x1,y1,x2,y2)等于該棋盤內分數和的平方且當x2-x1+y2-y1+2n 時，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只想到這個還不夠，TLE！n對于某個fun(n,x1,y1,x2,y2)來說，可能使用多次這個值，所以每次都計算太消耗時間n解決辦法：記錄

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

21、分數之和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存儲空間開銷分析存儲空間開銷分析int res159999;/fun的記錄表 存儲空間開銷105, 有多少空間是永遠也不會用的? 可否考慮用SET模板?39開關網絡開關網絡n問題描述問題描述p小明對電器與電路極感興趣，是一個很會動腦筋的人。一天，他在搗弄一塊電路板時突發(fā)奇想，可否用多個兩路比較器固化在電路板中，構成一個開關網絡，實現某種格式的數據輸出，如用硬件實現數據排序等？p兩路比較器是一個基本元件，由兩入兩出的比較元件構成，如圖：圖1 兩路比較器40n小明于是自己動手用若干組兩路比較器和導線組成整個開關網絡。他用這種開關網絡求4個數的最大值和最小值，如圖：圖2 求最大、最

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

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

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