现有Hanoi塔问题的递归方程为：???h(n)?2h(n?1)?1h(1)?1 ，求h(n)的非递归表
达式。
解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n递推到1，有：
n?1h(n)?cb?2n?1n?1??i?1bn?1?ig(i)?2n?2?...?2?2?1
2?2?1n
3. 单源最短路径的求解。
问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。
迭代
S {1}
u -
dist[2] dist[3] dist[4] dist[5] 10
maxint
30
100
初始 1 2 3 4
4. 请写出用回溯法解装载问题的函数。
装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，
n其中集装箱i的重量为wi，且
?i?1wi?c1?c2。装载问题要求确定是否有一个合理
的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。
解：void backtrack (int i)
{// 搜索第i层结点
if (i > n) // 到达叶结点
更新最优解bestx,bestw;return; r -= w[i];
if (cw + w[i] <= c) {// 搜索左子树 x[i] = 1; cw += w[i];
backtrack(i + 1); cw -= w[i]; } if (cw + r > bestw) {
x[i] = 0; // 搜索右子树 backtrack(i + 1); } r += w[i]; }
5. 用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。
// 检查左儿子结点 Type wt = Ew + w[i]; // 左儿子结点的重量 if (wt <= c) { // 可行结点 if (wt > bestw) bestw = wt; // 加入活结点队列 if (i < n) Q.Add(wt); } // 检查右儿子结点 if (Ew + r > bestw && i < n) Q.Add(Ew); // 可能含最优解 Q.Delete(Ew); // 取下一扩展结点
解答：斜线标识的部分完成的功能为：提前更新bestw值；
这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。
为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。
7. 最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，
Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立
?0?c[i?1][j?1]?1递归关系如下：c[i][j]???max{c[i][j?1],c[i?1][j]}?i?0,j?0i,j?0;xi?yi,j?0;xi?yjj
在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。
（1） 请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。
void LCSLength(int m，int n，char *x，char *y，int **c，int **b) { int i，j; for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3; }
（2） 函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填
写程序中的空格，以使函数LCS完成构造最长公共子序列的功能（请将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。
8.对下面的递归算法，写出调用f(4)的执行结果。
void f(int k) { if( k>0 ) { printf(\ f(k-1); f(k-1); void LCS(int i，int j，char *x，int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { LCS(i-1，j-1，x，b); cout< 3.某一问题可用动态规划算法求解的显著特征是____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 5.设S=｛X1，X2，···，Xn｝是严格递增的有序集，利用二叉树的结点来存储S中的元素，在表示S的二叉搜索树中搜索一个元素X，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=Xi，其概率为bi。（2）在二叉搜索树的叶结点中确定X∈（Xi，Xi+1），其概率为ai。在表示S的二叉搜索树T中，设存储元素Xi的结点深度为Ci；叶结点（Xi，Xi+1）的结点深度为di，则二叉搜索树T的平均路长p为多少？假设二叉搜索树T[i][j]=｛Xi，Xi+1，···，Xj｝最优值为m[i][j]，W[i][j]= ai-1+bi+···+bj+aj，则m[i][j](1<=i<=j<=n)递归关系表达式为什么？ 6.描述0-1背包问题。 三、简答题（30分） 1.流水作业调度中，已知有n个作业，机器M1和M2上加工作业i所需的时间分别为ai和bi，请写出流水作业调度问题的johnson法则中对ai和bi的排序算法。（函数名可写为sort(s,n)） 2.最优二叉搜索树问题的动态规划算法（设函数名binarysearchtree)） 答案： 一、填空 1．确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.时间复杂性 空间复杂性 时间复杂度高低 3. 该问题具有最优子结构性质 4.{BABCD}或{CABCD}或{CADCD｝ 5.一个（最优）解 6.子问题 子问题 子问题 7.回溯法 8. o(n*2n) o(min{nc,2n}) 9.最优子结构 重叠子问题