中华中学动态规划讲义.pptx
《中华中学动态规划讲义.pptx》由会员分享,可在线阅读,更多相关《中华中学动态规划讲义.pptx(73页珍藏版)》请在咨信网上搜索。
1、中中华中学中学动态规划划讲义周默介介绍动态规划是NOIP中非常重要的一类题型。在动态规划中,算法是最难想到的,当你想到了算法,实现也就迎刃而解。今天,我们将强调算法的研究,不作上机实践递推推递推是动态规划的根本,我们首先花一点时间进行递推训练 递推关系是一种简洁高效的常见数学模型,递推关系是一种简洁高效的常见数学模型,递推关系是一种简洁高效的常见数学模型,递推关系是一种简洁高效的常见数学模型,比如我们熟悉的比如我们熟悉的比如我们熟悉的比如我们熟悉的FibonacciFibonacciFibonacciFibonacci数列问题。在这种类数列问题。在这种类数列问题。在这种类数列问题。在这种类型的
2、问题中,每个数据项都和它前面的若干个型的问题中,每个数据项都和它前面的若干个型的问题中,每个数据项都和它前面的若干个型的问题中,每个数据项都和它前面的若干个数据项(或后面的若干个数据项)有一定的关数据项(或后面的若干个数据项)有一定的关数据项(或后面的若干个数据项)有一定的关数据项(或后面的若干个数据项)有一定的关联,这种关联一般是通过一个联,这种关联一般是通过一个联,这种关联一般是通过一个联,这种关联一般是通过一个“递推关系式递推关系式递推关系式递推关系式”来表示的。求解问题时我们从初始的一个或若来表示的。求解问题时我们从初始的一个或若来表示的。求解问题时我们从初始的一个或若来表示的。求解问
3、题时我们从初始的一个或若干个数据项出发,通过递推关系逐步推进,从干个数据项出发,通过递推关系逐步推进,从干个数据项出发,通过递推关系逐步推进,从干个数据项出发,通过递推关系逐步推进,从而得到最终结果,这种求解问题的方法叫而得到最终结果,这种求解问题的方法叫而得到最终结果,这种求解问题的方法叫而得到最终结果,这种求解问题的方法叫“递递递递推法推法推法推法”。其中,初始的若干数据项称为。其中,初始的若干数据项称为。其中,初始的若干数据项称为。其中,初始的若干数据项称为“边界边界边界边界”。解决递推问题有三个重点:解决递推问题有三个重点:一、如何建立正确的递推关系一、如何建立正确的递推关系二、递推关
4、系有何性质二、递推关系有何性质三、递推关系式如何求解三、递推关系式如何求解递推按照我们推导问题的方向,常分为顺推法和递推按照我们推导问题的方向,常分为顺推法和倒推法。倒推法。例例1、有一只经过训练的蜜蜂只能爬向右侧相邻的、有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。试求出蜜蜂从蜂房蜂房,不能反向爬行。试求出蜜蜂从蜂房a爬到蜂爬到蜂房房b的可能路线数。的可能路线数。问题分析:这是一道很典型的问题分析:这是一道很典型的Fibonacci数列类题目,其中的递推关系很明显。由于数列类题目,其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房,不能反向蜜蜂只能爬向右侧相邻的蜂房,不能反向
5、爬爬行行”的限制,决定了蜜蜂到的限制,决定了蜜蜂到b点的路径只能是点的路径只能是从从b-1点或点或b-2点到达的,故点到达的,故fn=fn-1+fn-2(a+2=n=b),边界条件,边界条件fa=1,fa+1=1。例例2 2、打印杨晖三角形的前、打印杨晖三角形的前1010行。杨晖三角形的行。杨晖三角形的前前5 5行如左下图所示。行如左下图所示。问题分析:我们观察左上图不太容易找问题分析:我们观察左上图不太容易找到规律,但如果将左上图转化为右上图就不难到规律,但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表(数组)发现杨辉三角形其实就是一个二维表(数组)的下三角部分。的下三角部分
6、。假设用二维数组假设用二维数组yhyh存储,每行首尾元素都为存储,每行首尾元素都为1 1,且,且其中任意一个非首尾元素其中任意一个非首尾元素yhi,jyhi,j的值其实就是的值其实就是yhi-1,j-1yhi-1,j-1与与yhi-1,jyhi-1,j的和,另外每一行的的和,另外每一行的元素个数刚好等于行数。有了这些规律,给数元素个数刚好等于行数。有了这些规律,给数组元素赋值就不难了,而要打印杨晖三角形,组元素赋值就不难了,而要打印杨晖三角形,只需控制一下每行输出的起始位置即可。只需控制一下每行输出的起始位置即可。例例3 3、猴子第、猴子第1 1天摘下若干个桃子天摘下若干个桃子,当即吃了一半又
7、当即吃了一半又一个。第一个。第2 2天又把剩下的桃吃了一半又一个天又把剩下的桃吃了一半又一个,以后以后每天都吃前一天剩下的桃子的一半又一个每天都吃前一天剩下的桃子的一半又一个,到第到第1010天猴子想吃时天猴子想吃时,只剩下一个桃子。只剩下一个桃子。问猴子第问猴子第1 1天一天一共摘了多少桃子共摘了多少桃子?问题分析:问题分析:已知条件第已知条件第 10 10 天剩下天剩下 1 1 个桃子,隐含个桃子,隐含条件每一次前一天的桃子个数等于后一天桃子的条件每一次前一天的桃子个数等于后一天桃子的个数加个数加 1 1 的的 2 2 倍。倍。我们采取逆向思维的方法我们采取逆向思维的方法,从后往前推,从后
8、往前推,可用倒推法求解。可用倒推法求解。VarVar S,I:LongInt;S,I:LongInt;BeginBegin S:=1;S:=1;第第1010天只有一个桃子天只有一个桃子 For I:=9 DownTo 1 Do For I:=9 DownTo 1 Do S:=(S+1)*2;S:=(S+1)*2;第第1010天依次求前一天的桃天依次求前一天的桃 Writeln(S);Writeln(S);子数子数 End.End.程序填空:设有一个程序填空:设有一个n n级的楼梯级的楼梯(1=n=12),(1=n=12),编号编号从下到上依次为从下到上依次为1 1至至n,n,其中有若干级为坏的
9、。有其中有若干级为坏的。有一个人上楼梯时一步可走一个人上楼梯时一步可走1 1级、或级、或2 2级、或级、或3 3级级(坏坏级只能跨过不能踏上级只能跨过不能踏上,但级数照算但级数照算)。问。问:这个人这个人从楼下走到第从楼下走到第n n级级,共有多少种不同的走法共有多少种不同的走法?例如例如:当当n=ln=l时时(无坏级情况下无坏级情况下),),仅有仅有1 1种走法种走法n=2n=2时时(无坏级情况下无坏级情况下),),有有:1:1级级+l+l级级 或或 2 2级级 共共2 2种种走法走法n=3n=3时时(第二级为坏级情况下第二级为坏级情况下),),有有:1:1级级+2+2级级,直接直接3 3级
10、级,共共2 2种走法种走法【程序说明程序说明】用递推方法求解。用集合记录坏级。用递推方法求解。用集合记录坏级。var x,i,n,fl,f2,f3,f4:longint;s:set of 0.30;begin readln(n);s:=readln(x);x:坏级坏级,以以0结束结束 while(xO)do begin s:=readln(x);end;If(1 in s)then f1:=0 else fl:=1;If(2 in s)then f2:=0 else f2:=If(3 in s)then f3:=0 else f3:=1+f1+f2;if n=1 then f4:=f1 els
11、e if n=2 then f4:=f2 else if n=3 then f4:=f3 else begin for i:=4 to n do begin if(i in s)then f4:=0 else f4:=fl:=f2;f2:=f3;f3:=f4;end;end;writeln(f4);readln;end.例例4、棋盘上、棋盘上A点有一个过河卒,需要走到目标点有一个过河卒,需要走到目标B点。点。卒行走的规则:可以向下、或者向右。同时在棋盘卒行走的规则:可以向下、或者向右。同时在棋盘上上C点有一个对方的马,该马所在的点和所有跳跃点有一个对方的马,该马所在的点和所有跳跃一步可达的点称
12、为对方马的控制点。因此称之为一步可达的点称为对方马的控制点。因此称之为“马马拦过河卒拦过河卒”。棋盘用坐标表示,。棋盘用坐标表示,A点点(0,0)、B点点(n,m)(n,m为不超过为不超过15的整数的整数),同样马的位置坐标是,同样马的位置坐标是需要给出的。现在要求你计算出卒从需要给出的。现在要求你计算出卒从A点能够到达点能够到达B点的路径的条数,假设马的位置是固定不动的,并点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。不是卒走一步马走一步。【样例样例】knight.in knight.out6 6 3 36 分析:本题可用搜索算法,但分析:本题可用搜索算法,但N,M=15
13、就会超时。就会超时。再分析题意会发现:要到达棋盘上的一个点,只能再分析题意会发现:要到达棋盘上的一个点,只能从左边过来或是从上面过来。根据加法原理,到达从左边过来或是从上面过来。根据加法原理,到达某一点的路径数目,就等于到达其相邻的上点和左某一点的路径数目,就等于到达其相邻的上点和左点的路径数目之和,因此我们可以使用逐列(或逐点的路径数目之和,因此我们可以使用逐列(或逐行)递推的方法来求出从起点到终点的路径数目。行)递推的方法来求出从起点到终点的路径数目。障碍点(马的控制点)也完全适用,只要将到达该障碍点(马的控制点)也完全适用,只要将到达该点的路径数目设置为点的路径数目设置为0即可。即可。假
14、设用假设用fi,j表示到达点(表示到达点(i,j)的路径数目,用)的路径数目,用gi,j表示点表示点(i,j)是否是对方马的控制点,是否是对方马的控制点,gi,j=0表示表示不是对方马的控制点,不是对方马的控制点,gi,j=1表示是对方马的控制表示是对方马的控制点。则,我们可以得到如下的递推关系式:点。则,我们可以得到如下的递推关系式:递推边界为递推边界为f0,0=1,f0,0=1,考虑到最大情况下:考虑到最大情况下:n=20,m=20n=20,m=20,路径条数可能会超出长整数范围所以要,路径条数可能会超出长整数范围所以要使用使用CompComp类型或高精度运算。类型或高精度运算。fi,j=
15、0 gx,y=1fi,j=0 gx,y=1fi,0=fi-1,0 i0,gx,y=0fi,0=fi-1,0 i0,gx,y=0f0,j=f0,j-1 j0,gx,y=0f0,j=f0,j-1 j0,gx,y=0fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0fi,j=fi-1,j+fI,j-1 i0,j0,gx,y=0 例例5 5、(NOIP(NOIP普及组第四题)给定普及组第四题)给定A,B,CA,B,C三根足够长的三根足够长的细柱,在细柱,在A A柱上放有柱上放有2n2n个中间有空的圆盘,共有个中间有空的圆盘,共有n n个不同的尺寸,每个个不同的尺寸,每个尺寸都有两个相同的圆
16、盘,注意这两个圆盘是不加尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的区分的(下图为下图为n=3n=3的情形)。现要将的情形)。现要将 这些国盘移到这些国盘移到C C柱上,在移动过程中可放在柱上,在移动过程中可放在B B柱上暂存。要求柱上暂存。要求:(1)(1)每次只能移动一个圆盘;每次只能移动一个圆盘;(2)A(2)A、B B、C C三根细柱上的圆盘都要保持上小下大的三根细柱上的圆盘都要保持上小下大的顺序;顺序;任务任务:设设AnAn为为2n2n个圆盘完成上述任务所需的最少移动个圆盘完成上述任务所需的最少移动次数,对于输入的次数,对于输入的n n,输出,输出AnAn。【输入输入】输入文件
17、输入文件hanoi.inhanoi.in为一个正整数为一个正整数n n,表示,表示在在A A柱上放有柱上放有2n2n个圆盘。个圆盘。【输出输出】输出文件输出文件hanoi.outhanoi.out仅一行,包含一个正仅一行,包含一个正整数,为完成上述任务所需的最少移动次数整数,为完成上述任务所需的最少移动次数AnAn。【输入输出样例输入输出样例1 1】hanoi.in hanoi.outhanoi.in hanoi.out1 21 2问题分析:如果每个尺寸只有一个圆盘,共问题分析:如果每个尺寸只有一个圆盘,共n n个个圆盘,也就是常见的汉诺塔问题。则设圆盘,也就是常见的汉诺塔问题。则设h hn
18、n为为n n 个盘子个盘子从从a a柱移到柱移到c c柱所需移动的盘次。显然,当柱所需移动的盘次。显然,当n=1n=1时,只时,只需把需把a a 柱上的盘子直接移动到柱上的盘子直接移动到c c柱就可以了,故柱就可以了,故h h1 1=1=1。当当n=2n=2时,先将时,先将a a柱上面的小盘子移动到柱上面的小盘子移动到b b柱上去;然柱上去;然后将大盘子从后将大盘子从a a柱移到柱移到c c 柱;最后,将柱;最后,将b b柱上的小盘子柱上的小盘子移到移到c c柱上,共记柱上,共记3 3个盘次,故个盘次,故h h2 2=3=3。以此类推,当。以此类推,当a a柱上有柱上有n(n=2)n(n=2)
19、个盘子时,总是先借助个盘子时,总是先借助c c柱把上面的柱把上面的n-n-1 1个盘子移动到个盘子移动到b b柱上,然后把柱上,然后把a a柱最下面的盘子移动柱最下面的盘子移动到到c c柱上;再借助柱上;再借助a a柱把柱把b b柱上的柱上的n-1n-1个盘子移动到个盘子移动到c c柱柱上;总共移动上;总共移动h hn-1n-1+1+h+1+hn-1n-1个盘次。个盘次。h hn n=2h=2hn-1n-1+1 +1 边界条件:边界条件:h hn-1n-1=1=1该题若仔细观察,很容易发现是该题若仔细观察,很容易发现是hanoi塔的变形塔的变形(只不过多了几个盘子),操作过程中,可以(只不过多
20、了几个盘子),操作过程中,可以将两个相同尺寸的盘子看成一个整体,这样就将两个相同尺寸的盘子看成一个整体,这样就成了典型的成了典型的hanoi塔问题。再运用公式:塔问题。再运用公式:fn=2n-1来做,最后只要乘来做,最后只要乘2就行了。由于数据就行了。由于数据较大,须用到高精度运算。较大,须用到高精度运算。题型大型大类简单线性dp背包最长XX子序列最长公共子序列LCS区间dp树dp坐标dp。1.数塔数塔738810277455265如图,有一数字三角形。数字三角形中的数字为不超过100的正整数。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层,每一步可沿左斜线向下或右斜线向下
21、走。假设三角形行数100,编程求解从最顶层走到最底层的一条路径,使得沿着该路径所经过的数字的总和最大,输出最大值。此数塔输出为30是否可以用前两次课所用的深搜呢。显然前两次课的深搜写数塔这道题的时候程序简明易懂。但是当行数很大时,当三角形的行数等于100时,其枚举量之大是可想而知的,用枚举法肯定超时,甚至根本不能得到计算结果,必须用动态规划法来解。constmaxn=10;vara:array1.maxn,1.maxnofinteger;max:longint;n,i,j:integer;proceduretry(x,y,dep:integer;sum:longint);beginif(dep
22、=n)thenbeginifsummaxthenmax:=sum;exitend;try(x+1,y,dep+1,sum+ax+1,y);try(x+1,y+1,dep+1,sum+ax+1,y+1);end;beginreadln(n);fori:=1tondoforj:=1toidoread(ai,j);max:=0;try(1,1,1,a1,1);writeln(max);end.那我们又该如何实现动态规划呢?1.逆推法:按三角形的行划分阶段,若行数为n,则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和,再依次求出第n-2阶段、第n-3阶
23、段第1阶段(起始点)各决策点至第n行的最佳路径。设:fi,j为从第i阶段中的点j至第n行的最大的数字和;则:fn,j=an,j1=j=nfi,j=maxai,j+fi+1,j,ai,j+fi+1,j+11=jfi+1,j+1 then fi,j:=ai,j+fi+1,j else fi,j:=ai,j+fi+1,j+1;writeln(f1,1);end.2.顺推法按三角形的行划分阶段,若行数为n,则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和,再依次求出第3,4,5,.,.n-1,n到起点的最大和,最后找第n行的最大值设fi,j为第i行第j列上点到起点的最大和则f1
24、,1=a1,1;fi,1=ai,1+fi-1,1;fi,j=maxai,j+fi-1,j-1,ai,j+fi-1,j2=jfi-1,j then fi,j:=ai,j+fi-1,j-1 else fi,j:=ai,j+fi-1,j;end;maxsum:=0;for i:=1 to n do if fn,imaxsum then maxsum:=fn,i;writeln(maxsum);end.2.最最长不下降子序列不下降子序列设有由n个不相同的整数组成的数列,记为:a(1)、a(2)、a(n)例如3,18,7,14,10,12,23,41,16,24。若存在i1i2i3ie且有a(i1)a(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中华 中学 动态 规划 讲义
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。