王建德5动态程序设计(免费阅读).ppt

主程序 { fillchar(hash,sizeof(hash),0); fillchar(used,sizeof(used),false); fillchar(did,sizeof(did),false); /*哈希表、表元素访问标志和方案已计算标志初始化*/ read(n,h,m); /*输入积木数、层数、最底层的积木数*/ writeln(search(n,h,m)); /*计算和输出塔的不同种数*/ }./*main*/ 例题 汉诺塔问题 N个盘子和M个塔的汉诺塔问题，要求输出最少步数和步骤。 【输入】盘子数N和塔数M （ ＜ n, M 65 ）； ?【输出格式】第1行为移动步数；接下来若干行为移动方案。其中每行为一个盘子的移动情况，格式为 move 盘子序号 from 起始柱号 to 目标柱号 使用动态规划计算方案数 data[i,j]代表i个盘子，通过j个柱子，需要最少多少步，才能完成移动。一般需要通过三个步骤： 1、把i个盘子中的k个移动到中间柱子，移动步数为data[k，j]； 2、把i-k个盘子移动到最后一个柱子，移动步数为data[i-k，j-1]； 3、把k个盘子移动到最后一个柱子，移动步数为data[k，j] 因此状态转移方程为： 数据结构 Const Limit=65; /*柱子数和盘子数的上限*/ Type Tdata = array[1..Limit , 1..Limit] of ext}ed; Tstrategy = array[1..Limit , 1..Limit] of longint; Tstack= array[1..Limit] of /*柱子序列类型*/ record tot : longint; /*长度*/ data : array[1..Limit] of longint;/*自下而上的盘子序列*/ end; Var data : Tdata; /*状态转移方程*/ strategy : Tstrategy; /* strategy[i，j]为i个盘子通过j个柱子移动的过程中，过渡阶段被移到中间柱子的盘子数*/ stack : Tstack; /*柱子序列*/ 计算移动方案 procedure work; var i , j : longint; { for i ← 1 to N do /*状态转移方程初始化*/ for j ← 1 to M do data[i , j] ← -1; dfs(N，M); /*递归计算n个盘、 m个塔的移动方案*/ };/* work */ procedure dfs(N,M:longint);/*递归计算盘子数为n、塔数为m的移动方案*/ var k : longint; { if data[N,M]=0 then exit; /*若得出移动方案数，则回溯*/ if N = 1 /*盘子数为1，则只有一种移动方案*/ then data[N,M] ←1 else if M=3 then{dfs(N-1,M); /*先计算N-1个盘子移动到中间柱子的方案*/ data[N , M]←data[N-1, M]*2+1; /*计算状态转移方程*/ strategy[N,M]←N-1 }; /*记下被移到中间柱子的盘子数*/ else{dfs(1,M); dfs(N-1, M-1); /*先计算1个盘子移动到中间柱子的方案，然后计算N-1个盘子移动到目标柱子的方案*/ data[N,M]←data[1,M]*2+data[N-1,M-1]; /*计算状态转移方程*/ strategy[N,M]←1; /*被移到中间柱子的