Microsoft PowerPoint - 第17讲_递归.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 第17讲_递归.ppt [兼容模式]"

悉矢郦
7 years ago
Views:

1 程序设计实习 (II): 算法设计第十七讲递归

2 通知每堂一牛主讲征集结束请大家积极参加评分活动周日上机练习请务必参加请注意周日上机出勤会计为平时成绩助教安排调整 ACM 校内赛温馨提示 2

3 枚举的基本思想上一节内容回顾给出解空间, 建立简洁的数学模型减少搜索的空间采用合适的搜索顺序熄灯问题确定局部状态减小搜索空间讨厌青蛙问题根据先验知识提前结束搜索 5

4 递归基本思想关键问题小游戏 (POJ2802) 棋盘分割 (POJ1191) 主要内容 6

5 什么是递归递归的基本思想递归是指某个函数直接或间接的调用自身问题的求解过程划分成许多相同性质的子问题的求解, 而小问题的求解过程可以很容易的求出, 这些子问题的解就构成里原问题的解总体思想待求解问题的解输入变量 x 的函数 f(x) 通过寻找函数 g( ), 使得 f(x) = g(f(x-1)) 且已知 f(0) 的值, 就可以通过 f(0) 和 g( () 求出 f(x) ) 的值推广扩展到多个输入变量 x, y, z 等,x-1 也可以推广到 x - x 1, 只要递归朝着出口的方向即可 7

输入变量 x 的函数 f(x) 通过寻找函数 g( ), 使得 f(x) = g(f(x-1)) 且已知 f(0) 的值, 就可以通过 f(0) 和 g( ()

6 递归与枚举的区别枚举 : 把一个问题划分成一组子问题, 依次对这些子问题求解子问题之间是横向的同类的关系递归 : 把一个问题逐级分解成子问题子问题与原问题之间是纵向的同类的关系语法形式上 : 在一个函数的运行过程中, 调用这个函数自己直接调用 : 在 fun() 中直接执行 fun() 间接调用 : 在 fun1() 中执行 fun2(); 在 fun2() 中又执行 fun1() 8

7 递归的三个要点递归式 : 如何将原问题划分成子问题递归出口 : 递归终止的条件, 即最小子问题的求解, 可以允许多个出口界函数 : 问题规模变化的函数, 它保证递归的规模向出口条件靠拢 9

8 求阶乘的递归程序给定 n, 求阶乘 n! int n, m=1; #include <iostream.h> for (int i=2; i<=n; i++) int Factorial(int n){ m* *=i; printf( %d 的阶乘是 %d\n, if (n == 0) nm); n, return 1; else return n * Factorial(n - 1); } 10

$*=i; printf( %d 的阶乘是 %d\n, if (n == 0) nm); n,$

9 阶乘的栈参数 0 Factorial(0) 1 参数 1 1*Factorial(0) 1 参数 2 2*Factorial(1) 2 参数 3 3*Factorial(2) 6 参数 4 4*Factorial(3) 24 主程序 11

10 1) 找出递推公式 2) 找到递归终止条件递归解决问题的关键注意事项 : 由于函数的局部变量是存在栈上的如果有体积大的局部变量, 比如数组, 而递归层次又可能很深的情况下, 也许会导致栈溢出可以考虑使用全局数组或动态分配数组 12

11 POJ2802 小游戏问题描述一天早上, 你起床的时候想我编程序这么牛, 为什么不能靠这个赚点小钱呢? 因此你决定编写一个小游戏游戏在一个分割成 w * h 个正方格子的矩形板上进行如图所示, 每个正方格子上可以有一张游戏卡片, 当然也可以没有当下面的情况满足时, 我们认为两个游戏卡片之间有一条路径相连 : 路径只包含水平或者竖直的直线段路径不能穿过别的游戏卡片但是允许路径临时的离开矩形板 13

子上可以有一张游戏卡片, 当然也可以没有当下面的情况满足时, 我们认为两个游戏卡片之间有一条路

12 下面是一个例子 : 这里在 (1, 3) 和 (4, 4) 处的游戏卡片是可以相连的而在 (2, 3) 和 (3, 4) 处的游戏卡是不相连的, 因为连接他们的每条路径都必须要穿过别的游戏卡片你现在要在小游戏里面判断是否存在一条满足题意的路径能连接给定的两个游戏卡片 14

13 输入输入包括多组数据 : 一个矩形板对应一组数据第一行包括两个整数 w 和 h (1 <= w, h <= 75), 分别表示矩形板的宽度和长度下面的 h 行, 每行包括 w 个字符, 表示矩形板上的游戏卡片分布情况 : 使用 X 表示这个地方有一个游戏卡片使用空格表示这个地方没有游戏卡片之后每行上包括 4 个整数 x1, y1, x2, y2 (1 <= x1, x2 <= w, 1 <= y1, y2 <= h) 给出两个卡片在矩形板上的位置注意 : 矩形板左上角的坐标是 (1,1) 1) 输入保证这两个游戏卡片所处的位置是不相同的如果一行上有 4 个 0, 表示这组测试数据的结束如果一行上给出 w = h = 0, 那么表示所有的输入结束了 15

个整数 x1, y1, x2, y2 (1 <= x1, x2 <= w, 1 <= y1, y2 <= h) 给出两个卡片在矩形板上的位置注意 : 矩形板左上角的坐标是 (1,1) 1) 输入保

14 输出对每一个矩形板, 输出一行 Board #n:, 这里 n 是输入数据的编号然后对每一组需要测试的游戏卡片输出一行这一行的开头是 Pair m:,, 这里 m 是测试卡片的编号 ( 对每个矩形板, 编号都从 1 开始 ) 如果可以相连, 找到连接这两个卡片的所有路径中包括线段数最少的路径, 输出 k segments., 这里 k 是找到的最优路径中包括的线段的数目 ; 如果不能相连, 输出 impossible. 每组数据之后输出一个空行 16

果可以相连, 找到连接这两个卡片的所有路径中包括线段数最少的路径, 输出 k segments.

15 样例输入 5 4 XXXXX X X XXX X XXX 样例输出 Board #1: Pi Pair 14 1: segments. Pair 2: 3 segments. Pair 3: impossible. 17

16 问题分析 (1) 迷宫求解问题, 自相似性表现在每走一步的探测方式相同, 可以用递归方法求解通过穷举方式找到从起点到终点的路径, 朝一个方向走下去 : 如果走不通, 则换个方向走四个方向都走不通, 则回到上一步的地方, 换个方向走依次走下去, 直到走到终点计算路径数目 : 普通迷宫问题的路径数目是经过的格子数目, 而该问题路径只包含水平或者竖直的直线段, 所以需要记录每一步走的方向如果上一步走的方向和这一步走的方向相同, 递归搜索时路径数不变, 否则路径数加 1 18

下去, 直到走到终点计算路径数目 : 普通迷宫问题的路径数目是经过的格子数目, 而该问题路径只包含水平或者竖直的直

17 问题分析 (2) 路径只包含水平或者竖直的直线段路径不能穿过别的游戏卡片但是允许路径临时的离开矩形板 (1,3) (2,3) (5,3) (3,4) (4,4) 所以在矩形板最外层增加一圈格子, 路径可以通过这些新增加的格子 19

18 描述迷宫 : 问题分析 (3) 1 设置迷宫为二维数组 board[][], 数组的值是 : 空格 : 代表这个地方没有游戏卡片 X : 代表这个地方有游戏卡片 2 在搜索过程中, 用另外一个二维数 mark[][] 标记格子是否已经走过了 mark[i][j]=0 // 格子 (i, j) 未走过 mark[i][j]=1 // 格子 (i, j) 已经走过 3 int minstep, w, h;// 全局变量 //minstep, 记录从起点到达终点最少路径数, // 初始化为一个很大的数 //w, h 矩形板的宽度和高度 20

mark[i][j]=0 // 格子 (i, j) 未走过 mark[i][j]=1 // 格子 (i, j) 已经走过 3 int minstep, w, h;// 全

19 问题分析 (4) X X X X X X X X X X X X X 21

20 问题分析 (5) 设置搜索方向顺序是东南西北 int to[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; {1 0} {0 { 10}} //now_x, now_y, 当前位置 //x, y 下一步位置 for(i = 0; i < 4; i ++){ (x,y-1) int x = now_x + to[i][0]; int y = now_y + to[i][1]; f=i; // 方向, 0,1,2,3 分别表示东南西北 } (x-1,y) (x,y) (x+1,y) 北东 (x,y+1) 22

$y 下一步位置 for(i = 0; i < 4; i ++){ (x,y-1) int x = now_x + to[i][0]; int$

21 问题分析 (6) 判断新位置 (x,y) 是否有效 T1:(x, y) 在边界之内 (x > -1) && (x < w + 2) && (y > -1) && (y < h + 2) T2: 该位置没有游戏卡片并且未曾走过 ((board[y][x] == ' ') && (mark[y][x] == false)) T3: 已经到达终点 (x == end_x) && (y == end_y) && (board[y][x] == 'X') 综上,(x,y) 有效的条件是 T1 && (T2 T3) ((x > -1) && (x < w + 2) && (y > -1) && (y < h + 2) && (((board[y][x] == ' ') && (mark[y][x] == false)) ((x == end_x) && (y == end_y) && (board[y][x] == 'X')))) 23

22 构造递归函数递归方法 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) 时的方向 24

23 #include <stdio.h> 参考程序 #include <memory.h> #define MAXIN 75 char board[maxin + 2][MAXIN + 2]; // 定义矩形板 int minstep, w, h, to[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; // 定义方向 bool mark[maxin + 2][MAXIN + 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) // 更新最小路径数 return; minstep = step; 25

24 } for(int i = 0; i < 4; i ++){ // 枚举下一步的方向 int x = now_x + to[i][0]; // 得到新的位置 int y = now_y + to[i][1]; if ((x > -1) && (x < w + 2) && (y > -1) && (y < h + 2) && (((board[y][x] == ' ') && (mark[y][x] == false)) ((x==end_x) && (y == end_y) && (board[y][x] == X )))){ // 如果新位置有效 mark[y][x] = true; // 标记该位置已经经过 // 上一步方向和当前方向相同, // 则递归搜索时 step 不变, 否则 step+1 if(f == i) Search(x, y, end_x, end_y, step, i); else Search(x,,y, end_ x, end_y, step + 1, i); mark[y][x] = false; // 回溯, 该位置未曾走过 } } 26

25 int 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 ++)board[0][i] = board[i][0] =''; for(i = 1; i <= h; i ++){ // 读入矩形板的布局 getchar(); for(j = 1; j <= w; j ++) board[i][j] = getchar(); } // 在矩形板最外层增加一圈格子 for (i = 0; i <= w; i ++) board[h + 1][i + 1] = ' '; for(i=0;i<=h;i++) i i board[i + 1][w + 1] = ' '; 27

26 } int begin_x, begin_y, end_x, end_y, count = 0; while(scanf("%d %d %d %d", &begin_x, &begin_y, &end_x, &end_y) && begin_x > 0){ // 读入起点和终点 count ++; minstep = ; // 初始化 minstep 为一个很大的值 memset(mark, false, sizeof(mark)); // 递归搜索 Search(begin_x, begin_y, end_x, end_y, 0, -1); // 输出结果 if(minstep < )printf("Pair %d: %d segments.\n", count, minstep); else printf("pair %d: impossible.\n", count); } printf("\n"); } return 0; 28

27 递归的条件问题小结自相似性表现在每走一步的探测方式相同, 可以用递归算法求解定义并记录路径方向判断下一步的位置是否符合要求搜索过程 Search( ) 朝一个方向走下去, 如果走不通, 则换个方向走 ; 四个方向都走不通, 则回到上一步的地方, 换个方向走 ; 依次走下去, 直到走到终点计算路径数目需要记录每一步走的方向, 如果上一步走的方向和这一步走的方向相同, 递归搜索时路径数不变, 否则路径数加 1 29

28 POJ1191: 棋盘分割将一个 8*8 的棋盘进行如下分割 : 将原棋盘割下一块矩形棋盘并使剩下部分也是矩形, 再将剩下的部分继续如此分割, 这样割了 (n-1) 次后, 连同最后剩下的矩形棋盘共有 n 块矩形棋盘 ( 每次切割都只能沿着棋盘格子的边进行 ) 允许的分割方案不允许的分割方案 30

29 原棋盘上每一格有一个分值, 一块矩形棋盘的总分为其所含各格分值之和现在需要把棋盘按上述规则分割成 n 块矩形棋盘, 并使各矩形棋盘总分的均方差最小 n n i 1 x 2 i x xi i 1 均方差, 其中平均值 x, n x i 为第 i 块矩形棋盘的总分请编程对给出的棋盘及 n, 求出 σ 的最小值 n 31

30 输入第 1 行为一个整数 n (1 < n < 15) 第 2 行至第 9 行每行为 8 个小于 100 的非负整数, 表示棋盘上相应格子的分值每行相邻两数之间用一个空格分隔输出仅一个数, 为 σ ( 四舍五入精确到小数点后三位 ) 32

31 样例输入样例输出

32 问题分析 (1) 每一次分割有以下 4 种方法 : f (k, 棋盘 ) = {f{ f (1, 割下的棋盘 )+f f (k-1, 待割的棋盘 )} (k 2) 34

33 问题分析 (2) n i 1 x 2 i n x 如右式, 若要求出最小方差, 只需要 2 求出最小的 x i ( ( xi x ) ( xi 2 xi x x ) x 2 x x nx 2 i 2 i i 2 2 x 2nx nx 2 xi nx

34 问题分析 (3) 设 fun(n,x1,y1,x2,y2) 1 2) 为以 (x1, y1) 为左上角,(x2,( 2 y2) 为右下角的棋盘分割成 n 份后的最小平方和那么 fun(n,x1,y1,x2,y2)= x2 1 min{min{ { fun ( n 1, x1, y1, i, y2) fun (1, i 1, y1, x2, y2)}, i x1 x2 1 min{ fun(1, x1, y1, i, y2) fun( n 1, i 1, y1, x2, y2)}, i x1 y2 1 min{ fun( n 1, x1, y1, x2, i) fun(1, x1, i 1, x2, y2)}, i y1 y2 1 min{ fun(1, x1, y1, x2, i) fun( n 1, x1, i 1, x2, y2)}} i y1 其中 fun(1x1y1x2y2) fun(1,x1,y1,x2,y2) 等于该棋盘内分数和的平方 36

35 问题分析 (3) 只想到这个还不够,TLE! 对于某个 fun(n,x1,y1,x2,y2) y 来说, 可能使用多次这个值, 所以每次都计算太消耗时间解决办法 : 记录表用 res[n][x1][y1][x2][y2] 来记录 fun(n,x1,y1,x2,y2) res 初始值统一为 -1 当需要使用 fun(n,x1,y1,x2,y2) 时, 查看 res[n][x1][y1][x2][y2] 如果为 -1, 那么计算 fun(n,x1,y1,x2,y2), 并保存于 res[n][x1][y1][x2][y2] 如果不为 -1, 直接返回 res[n][x1][y1][x2][y2] 37

36 参考程序 int s[9][9]; // 每个格子的分数 int sum[9][9]; //(1,1) 到 (i,j) 的矩形的分数之和 int res[15][9][9][9][9]; //fun 的记录表 int calsum(int x1,int y1,int x2,int y2)//(x1,y1) 到 (x2,y2) 的矩形的分数之和 { return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; } 38

37 int fun(int n,int x1,int y1,int x2,int y2) { int t, a, b, c, e, MIN= ; if(res[n][x1][y1][x2][y2]!=-1) return res[n][x1][y1][x2][y2]; ][y ][y ]; if(n==1) { } t=calsum(x1,y1,x2,y2); x2 y2); res[n][x1][y1][x2][y2]=t*t; return t*t; 39

38 } for(a=x1;a<x2;a++) { c=calsum(a+1,y1,x2,y2); e=calsum(x1,y1,a,y2); t=min(fun(n-1,x1,y1,a,y2)+c*c, fun(n-1,a+1,y1,x2,y2)+e*e); if(min>t) MIN=t; } for(b=y1;b<y2;b++) { c=calsum(x1,b+1,x2,y2); e=calsum(x1y1x2b); calsum(x1,y1,x2,b); t=min(fun(n-1,x1,y1,x2,b)+c*c, fun(n-1,x1,b+1,x2,y2)+e*e); if(min>t) MIN=t; } res[n][x1][y1][x2][y2]=min; return MIN; 40

39 int main() { memset(sum, 0, sizeof(sum)); memset(res, -1, sizeof(res)); // 初始化记录表 int n; cin>>n; for (int i=1; i<9; i++) for (int j=1, rowsum=0; j<9; j++) { cin>>s[i][j]; rowsum +=s[i][j]; sum[i][j] += sum[i-1][j] + rowsum; } double result = n*fun(n,1,1,8,8)-sum[8][8]*sum[8][8]; cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(result/(n*n))<<endl; } return 0; 41

40 递归的优缺点小结优点 : 直接算法程序结构清晰思路明了缺点 : 递归函数的每一次调用都要把分配的相应空间保存起来递归运行过程大致如下 : 1) 计算当前函数的实参的值 2) 分配空间, 并将首地址压栈, 保护现场 3) 转到函数体, 执行各语句, 此前部分会重复发生 ( 递归调用 ) 4) 直到出口, 从栈顶取出相应数据, 包括, 返回地址, 返回值等等, 收回空间, 恢复现场, 转到上一层的调用位置继续执行本次调用未完成的语句 42

41 思考题趣味思考题 : 菲波那契数列的计算递归 :O(N) 递推 :O(N) 问题 : 给出一种时间复杂度 < O(N) 的解法, 例如 O(log 2 N) 甚至 O(1)? 当 N=2 60 次方时如何计算? 选自编程之美微软技术面试心得 43

类似地, 又可定义变下限的定积分 : ( ). 与 ψ 统称为变限积分. f ( ) d f ( t) dt,, 注在变限积分 (1) 与 () 中, 不可再把积分变量写成的形式 ( 例如 ) 以免与积分上下限的

类似地, 又可定义变下限的定积分 : ( ). 与 ψ 统称为变限积分. f ( ) d f ( t) dt,, 注在变限积分 (1) 与 () 中, 不可再把积分变量写成的形式 ( 例如 ) 以免与积分上下限的 5 ( 一 ) 微积分学基本定理当函数的可积性问题告一段落, 并对定积分的性质有了足够的认识之后, 接着要来解决一个以前多次提到过的问题在定积分形式下证明连续函数必定存在原函数. 一变限积分与原函数的存在性设 f 在 [,] 上