程序设计实习(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()中直接执行fun()l间接调用：在fun1()中执行fun2()；在fun2()中又执行fun1()递归与枚举的区别递归与枚举的区别7递归的三个要点递归的三个要点n递归式递归式：如何将原问题划分成子问题。n递归出口递归出口：递归终止

4、的条件，即最小子问题的求解，可以允许多个出口。n界函数界函数：问题规模变化的函数，它保证递归的规模向出口条件靠拢8递归解决问题的关键递归解决问题的关键n1) 找出递推公式找出递推公式n2) 找到递归终止条件找到递归终止条件n注意事项：注意事项：由于函数的局部变量是存在栈上的，如果有体积大的局部变量，比如数组，而递归层次又可能很深的情况下，也许会导致栈溢出，因此可以考虑使用全局数组或动态分配数组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是找到的最优路径中包括的线段的数目；如果不能相连，输出“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，返回优化策略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的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)允许的分割方案不允许的分割方案28n原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成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初始值统一为-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小明对电器与电路极感兴趣，是一个很会动脑筋的人。一天，他在捣弄一块电路板时突发奇想，可否用多个两路比较器固化在电路板中，构成一个开关网络，实现某种格式的数据输出，如用硬件实现数据排序等？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受此启发，小明在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的完全二叉树. 树上每个叶子节点对应一个长度为N的0/1序列 递归的出口

26、到达叶子节点:判断对应的0/1序列是否可以正确分类(出口1)开关网络在处理前面已经达到的某个叶子节点时,不能正确工作(出口2)50n搜索树搜索树p考虑2n个长为n的0-1序列x1, x2, , xn ，其全体构成如下的完全二叉树。现只要对该树每一支对应的0-1序列，判断分类网络是否合乎排序要求。p实现过程中，先考虑最左边的一支，然后逐渐从第n个数位开始往前进行替换，这实际上是进行回溯操作，只要发现对某个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) /递归程序，