资源描述：
《高中信息技术 全国青少年奥林匹克联赛教案 动态规划实例分析及程序实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、全国青少年信息学奥林匹克联赛动态规划实例分析及程序实现一、数字三角形 （图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 ●每一步可沿左斜线向下或右斜线向下走； ●1＜三角形行数≤100； ●三角形中的数字为整数0，1，…99；输入数据：由INPUT.TXT文件中首先读到的是三角形的行数。在例子中INPUT.TXT表示如下：5738810274445265输出数据：把最大总和（整数）写入OUTPUT.TXT文件。上例为：30
2、 ７ ３ ８ ８ １ ０ ２ ７ ４ ４ ４ ５ ２ ６ ５ （图３.１－１） 二、算法分析 只要对该题稍加分析，就可以得出一个结论： 如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。 我们采用动态规划中的顺推解法。
3、按三角形的行划分阶段。若行数为n,则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，……，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。 设： ｆk（Ｕk）━━从第ｋ阶段中的点Ｕk至三角形顶点有一条最佳路径，该路径所经过的数字的总和最大，ｆk（Ｕk）表示为这个数字和； 由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设 Ｕk1━━ｋ－１阶段中某点Ｕk沿左斜线向下的点； Ｕk2━━ｋ－１阶段中某点Ｕk沿右斜线向下的点；
4、ｄk（Ｕk1）━━ｋ阶段中Ｕk1的数字； ｄk（Ｕk2）━━ｋ阶段中Ｕk2的数字； 因而可写出顺推关系式 ｆk（Ｕk）＝ｍａｘ｛ｆk-1（Ｕk）＋ｄk（Ｕk1），ｆk-1（Ｕk）＋ｄk（Ｕk2）｝ ｆ0（Ｕ0）＝０； Ｋ＝１，２，３，４，……ｎ 经过一次顺推，便可分别求出由顶至底Ｎ个数的Ｎ条路径，在这Ｎ条路径所经过的Ｎ个数字和中，最大值即为正确答案。 三、程序分析 根据上述顺推关系，我们编写程序如下：ProgramID1P1;ConstMaxn=100;Ty
5、peNode=RecordVal,Tot:Integer{当前格数字;从[1,1]到当前格的路径所经过的数字和}End;VarList:Array[1..Maxn,1..Maxn]ofNode;{计算表}N,Max,{行数,最大总和}I,J:Integer;{辅助变量}Fi:Text;{文件变量}ProcedureInit;BeginAssign(Fi,'INPUT.TXT');{文件名和文件变量连接}Reset(Fi);{文件读准备}Readln(Fi,N);{读三角形行数}Fori:=1toNDo
6、{读入三角形各格的数字}Forj:=1toiDoRead(Fi,List[i,j].Val);Close(Fi)End; {init}ProcedureMain;BeginList[1,1].Tot:=List[1,1].Val;{从[1,1]位置开始往下顺推}Fori:=2toNDoForj:=1toiDoBeginList[i,j].Tot:=-1;{从[1,1]至[i,j]的数字和初始化}If(j<>1)And(List[i-1,j-1].Tot+List[i,j].Val>List[i,j].
7、Tot)ThenList[i,j].Tot:=List[i-1,j-1].Tot+List[i,j].Val;{若从[i-1,j-1]选择右斜线向下会使[1,1]至[i,j]的数字和最大,则决策该步}If(j<>i)And(List[i-1,j].Tot+List[i,j].Val>List[i,j].Tot)ThenList[i,j].Tot:=List[i-1,j].Tot+List[i,j].Val{若从[i-1,j]选择左斜线向下会使[1,1]至[i,j]的数字和最大,则决策该步}End;{f
8、or}Max:=1;{[1,1]至底行各点的N条路径所经过的数字和中,选择最大的一个输出}Fori:=2toNDoIfList[N,i].Tot>List[N,Max].TotThenMax:=i;Writeln(List[N,Max].Tot){输出最大总和}End;{main}BeginInit;{读入数字三角形}Main{求最大总和}End.{main}二、Problem:打鼹鼠Contents:有个n*n个格子，在m个时间点上的不定格子里有数量不
