动态规划教案

吉林师范大学计算机学院教案课程名称C程序设计(算法部分)院系级计算机学院计算机科学与技术09级教研室(系、实验室)计算机基础教研室5101授课班级09计算机科学与技术3班实习生郑言系指导教师滕国文吉林师范大学计算机学院二○一二年四月二十五日（星期三5，6节）课型章节：动态规划基本思想基要本参教考材资和料主：算法设计与分析》教学目的：本课程以C语言为专家程序设计的描述语言，结合语言介绍程序设计的基本原理、技巧和办法。重要讲授内容涉及程序设计动态规划基本概念，动态规划的基本环节，动态规划问题的特性。通过本课程的学习，为算法更加好的学习，以及能用计算机解决某些实际问题打下坚实的基础。教学基本规定：掌握C语言中动态规划的基本概念，动态规划的基本环节，动态规划问题的特性。并能纯熟使用C语言动态规划思想解决某些简朴程序问题；掌握某些基本算法构造及有关办法；熟悉程序设计的思想和编程技巧。重点：动态规划基本概念，动态规划的基本环节，动态规划问题的特性。难点: 动态规划的基本环节课型： 理论课教法：1.多媒体解说2.举例解说教学内容及过程：课前回想：枚举法: 在进行归纳推理时，如果逐个考察了某类事件的全部可能状况，因而得出普通结论，那么这结论是可靠的，这种归纳办法叫做枚举法．2.数塔问题有形以下图所示的数塔，从顶部出发，在每一结点能够选择向左走或是向右走，始终走终究层，规定找出一条途径，使途径上的值最大。简朴的进行选举办法的引导，让同窗们主动思考到动态规划的思想上了。考虑一下：从顶点出发时终究向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道途径上的最大值求出来了才干作出决策。同样，下一层的走向又要取决于再下一层上的最大值与否已经求出才干决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大值的结点19迈进就能够了。因此实际求解时，可从底层开始，层层递进，最后得到最大值。 结论：自顶向下的分析，自底向上的计算。#include<stdio.h>#include<math.h>intmax(intx,inty){ if(x>y) returnx; else returny;}main(){ inta[100][100]; inti,j,n; scanf("%d",&n); for(i=0;i<n;i++) for(j=0;j<=i;j++) scanf("%d",&a[i][j]); for(i=n-2;i>=0;i--) for(j=0;j<=i;j++) { a[i][j]+=max(a[i+1][j],a[i+1][j+1]); } printf("%d\n",a[0][0]);}3.总结“动态规划的基本思想”如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就能够避免大量的重复计算。由此而来的基本思路是，用一种表统计全部已解决的子问题的答案，不管该问题后来与否被用到，只要它被计算过，就将其成果填入表中。4.总结“动态规划的基本环节”动态规划算法普通用于求解含有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一种解都对应于一种值，我们但愿找到含有最优值（最大值或最小值）的那个解。设计一种动态规划算法，普通能够按下列几个环节进行：（1）找出最优解的性质，并刻画其构造特性。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一种最优解。 其中（1）——（3）步是动态规划算法的基本环节。在只需规定出最优值的情形，环节（4）能够省去。若需规定出问题的一种最优解，则必须执行环节（4）。此时，在环节（3）中计算最优值时，普通需统计更多的信息，方便在环节（4）中，根据所统计的信息，快速构造出一种最优解。5.总结“动态规划问题的特性”动态规划算法的有效性依赖于问题本身所含有的两个重要性质： 1、最优子构造：当问题的最优解包含了其子问题的最优解时，称该问题含有最优子构造性质。 2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被重复计算多次。动态规划算法正是运用了这种子问题的重叠性质，对每一种子问题只解一次，而后将其解保存在一种表格中，在后来尽量多地运用这些子问题的解。6.思考：《免费馅饼》题目描述:都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范畴内。馅饼如果掉在了地上固然就不能吃了，因此gameboy立刻卸下身上的背包去接。但由于小径两侧都不能站人，因此他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，即使在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超出一米的范畴内接住坠落的馅饼。现在给这条小径如图标上坐标：

为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中期中一种位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包能够容纳无穷多个馅饼）#include<iostream>

usingnamespacestd;

inta[100001][11];

intmax(intx,inty,intz)

{

if(x>y)

if(x>z)

returnx;

else

returnz;

else

if(y>z)

returny;

else

returnz;

}

intmain()

{

inti,j,f,n,x,y;

while(cin>>n)

{

if(n==0)

break;

memset(a,0,sizeof(a));

f=0;

for(i=0;i<n;i++)

{

cin>>y>>x;

a[x][y]++;

if(x>f)

f=x;

}

for(i=f-1;i>=0;i--)

{

for(j=0;j<11;j++)

if(j>0&&j<10)

a[i][j]+=max(a[i+1][j-1],a[i+1][j],a[i+1][j+1]);

elseif(j==0)

a[i][j]+=max(0,a[i+1][j],a[i+1][j+1]);

else

a[i][j]+=max(0,a[i+