第十四周递归与动态规划三.ppt
《第十四周递归与动态规划三.ppt》由会员分享,可在线阅读,更多相关《第十四周递归与动态规划三.ppt(28页珍藏版)》请在三一文库上搜索。
1、第十四讲,递归与动态规划(三),ACM算法与程序设计,2/28,Help Jimmy,1、问题描述,“Help Jimmy“ 是在下图所示的场景上完成的游戏:,3/28,问题描述,场景中包括多个长度和高度各不相同的平台。地面是最低的平台,高度为零,长度无限。 Jimmy 老鼠在时刻0 从高于所有平台的某处开始下落,它的下落速度始终为1 米/秒。当Jimmy 落到某个平台上时,游戏者选择让它向左还是向右跑,它跑动的速度也是1 米/秒。当Jimmy 跑到平台的边缘时,开始继续下落。Jimmy 每次下落的高度不能超过MAX 米,不然就会摔死,游戏也会结束。 设计一个程序,计算Jimmy 到地面时可能
2、的最早时间。,4/28,问题描述,输入数据 第一行是测试数据的组数t(0 = t = 20)。每组测试数据的第一行是四个整数N,X,Y,MAX,用空格分隔。N 是平台的数目(不包括地面),X 和Y 是Jimmy 开始下落的位置的横竖坐标,MAX 是一次下落的最大高度。接下来的N 行每行描述一个平台,包括三个整数,X1i,X2i和Hi。Hi表示平台的高度,X1i和X2i表示平台左右端点的横坐标。1= N = 1000,-20000 = X, X1i, X2i = 20000,0 Hi Y = 20000(i = 1N)。所有坐标的单位都是米。 Jimmy 的大小和平台的厚度均忽略不计。如果Jim
3、my 恰好落在某个平台的边缘,被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy 一定能安全到达地面。,5/28,问题描述,输出要求 对输入的每组测试数据,输出一个整数,Jimmy 到地面时可能的最早时间。 输入样例 1 3 8 17 20 0 10 8 0 10 13 4 14 3 输出样例 23,6/28,2、解题思路,此题目的“子问题”是什么呢? Jimmy 跳到一块板上后,可以有两种选择,向左走或向右走。走到左端和走到右端所需的时间,容易算出。 如果我们能知道,以左端为起点到达地面的最短时间,和以右端为起点到达地面的最短时间,那么向左走还是向右走,就很容选择了。 因此,整
4、个问题就被分解成两个子问题,即Jimmy 所在位置下方第一块板左端为起点到地面的最短时间,和右端为起点到地面的最短时间。这两个子问题在形式上和原问题是完全一致的。 将板子从上到下从1 开始进行无重复的编号(高度相同的板子,哪块编号在前无所谓),那么,和上面两个子问题相关的变量就只有板子的编号。,7/28,2、解题思路,所以,本题目的“状态”就是板子编号,而一个“状态”对应的“值”有两部分,是两个子问题的解,即从该板子左端出发到达地面的最短时间,和从该板子右端出发到达地面的最短时间。 不妨认为Jimmy 开始的位置是一个编号为0,长度为0 的板子,假设LeftMinTime(k)表示从k 号板子
5、左端到地面的最短时间,RightMinTime(k)表示从k 号板子右端到地面的最短时间,那么,求板子k 左端点到地面的最短时间的方法如下: if ( 板子k 左端正下方没有别的板子) if( 板子k 的高度 h(k) 大于Max) LeftMinTime(k) = ; else LeftMinTime(k) = h(k); else if( 板子k 左端正下方的板子编号是m ) LeftMinTime(k) = h(k)-h(m) + Min(LeftMinTime(m)+Lx(k)-Lx(m), RightMinTime(m)+Rx(m)-Lx(k);,8/28,2、解题思路,上面,h(i
6、)就代表i 号板子的高度,Lx(i)就代表i 号板子左端点的横坐标,Rx(i)就代表i号板子右端点的横坐标。那么 h(k)-h(m) 当然就是从k 号板子跳到m 号板子所需要的时间,Lx(k)-Lx(m) 就是从m 号板子的落脚点走到m 号板子左端点的时间,Rx(m)-Lx(k)就是从m号板子的落脚点走到右端点所需的时间。 求RightMinTime(k)的过程类似。 不妨认为Jimmy 开始的位置是一个编号为0,长度为0 的板子,那么整个问题就是要求LeftMinTime(0)。 输入数据中,板子并没有按高度排序,所以程序中一定要首先将板子排序。,9/28,3、参考程序,#include #
7、include #include #define MAX_N 1000 #define INFINITE 1000000 int t, n, x, y, max; struct Platform int Lx, Rx, h; ; Platform aPlatformMAX_N + 10; int aLeftMinTimeMAX_N + 10; int aRightMinTimeMAX_N + 10; int MyCompare( const void * e1, const void * e2 ) Platform * p1, * p2; p1 = (Platform * ) e1; p2 =
8、 (Platform * ) e2; return p2-h - p1-h; /从大到小排列 ,10/28,3、参考程序,int MinTime( int L, bool bLeft ) int y = aPlatformL.h; int i, x; if( bLeft ) x = aPlatformL.Lx; else x = aPlatformL.Rx; for( i = L + 1;i = x) break; if( i max )/太高 return INFINITE; ,11/28,3、参考程序,else /没找到 if( y max )/离地面太高 return INFINITE;
9、 else return y; /特殊情况处理完毕 int nLeftTime = y - aPlatformi.h + x - aPlatformi.Lx; int nRightTime = y - aPlatformi.h + aPlatformi.Rx - x; if( aLeftMinTimei = -1 )/还没有存储值 aLeftMinTimei = MinTime(i, true); if( aRightMinTimei = -1 ) aRightMinTimei = MinTime(i, false); nLeftTime += aLeftMinTimei; nRightTim
10、e += aRightMinTimei; if( nLeftTime nRightTime ) return nLeftTime; return nRightTime; ,12/28,3、参考程序,int main(void) scanf(“%d“, ,思考题:重新编写此程序,要求不使用递归函数,13/28,最长公共子序列,1、问题描述,我们称序列Z = 是序列X = 的子序列当且仅当存在严格上升的序列,使得对j = 1, 2, . ,k, 有xij = zj。比如Z = 是X = 的子序列。 现在给出两个序列X 和Y,你的任务是找到X 和Y 的最大公共子序列,也就是说要找到一个最长的序列Z,
11、使得Z 既是X 的子序列也是Y 的子序列。 输入数据 输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200 的字符串,表示两个序列。两个字符串之间由若干个空格隔开。,14/28,问题描述,输出要求 对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。 输入样例 abcfbc abfcab programming contest abcd mnp 输出样例 4 2 0,15/28,2、解题思路,用字符数组s1、s2存放两个字符串,用s1i表示s1中的第i 个字符,s2j表示s2中的第j个字符(字符编号从1 开始),用s1i表示s1的前i个字符所构成的子串,s2j表示s2的前
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 四周 递归 动态 规划
链接地址:https://www.31doc.com/p-2584841.html