《算法设计与分析》复习题

}

4．用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限） 。 private static boolean ok( int k ){ for(int j=1;j<=n;j++)

if( a[k][j] && x[j]==x[k] )

return false;

return true; }

5．Hanoi算法 Hanoi ( n, a, b, c ){

if ( n==1 )

move(a,c) ; else{

Hanoi(n-1,a,c,b) ; Move(a,c) ; Hanoi ( n-1, b, a, c ); }

}

// 检查颜色可用性

算法应用

1．给定多项式p(x) = anxn + an-1xn-1 + … + a1x + a0，假设使用以下方法求解： p = a0; xpower = 1; for ( i=1; i<=n; i++ ){

xpower = x * xpower; p = p + ai * xpower; }

（1）该算法最坏情况下使用的加法和乘法分别为多少次？ （2）能不能对算法的性能进行提高？如果可以，请写出改进算法。 （1）该算法最坏情况下使用的加法n次，乘法2n次

第 5 页 共 9 页

（2）改进的算法为： float Horner(A, float x) { p=A[n+1];

for (j=1; j<=n; j++) p=x*p+A[n-j]; return p; }

该算法中使用加法n次，乘法n次

2．假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。

物品 重量 价值

3．已知在如下所示的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。

4．设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表： ① 每个选手必须与其他n-1名选手比赛各一次； ② 每个选手一天至多只能赛一次； ③ 循环赛要在最短时间内完成。

（1）如果n=2k，循环赛最少需要进行多少天； 如果n≠2k，循环赛最少需要进行多少天。 （2）当n=23=8时，请画出循环赛日程表：

第 6 页 共 9 页

A 35 10 B 30 40 C 60 30 D 50 50 E 40 35 F 10 40 G 25 30 a b

5．已知Ak?(aij(k))ri*ri?1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。 使用 算法进行求解。 最优值数组为： 1 2 3 4 5 6

最优断开位置数组为： 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 因此，最佳乘积序列为 。共执行乘法 次。

6．棋盘覆盖问题。

（1）将下图特殊棋盘进行L型骨牌填充。

（2）算法时间复杂性。

7．用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分。试说明划线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。

第 7 页 共 9 页

// 检查左儿子结点

int wt = ew + w[i]; // 左儿子结点的重量 if ( wt <= c ) { // 可行结点 if ( wt > bestw ) bestw = wt ; // 加入活结点队列

if ( i < n ) queue.put( new Integer( wt ) );

}

// 检查右儿子结点

if ( ew + r > bestw && i < n )

queue.put( new Integer( wt ) ); // 可能含最优解

ew=( ( Integer )queue.remove( ) ).intValue( ); // 取下一扩展结点

8．单源最短路径的求解。给定带权有向图（如下图所示）G = ( V，E )，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 请用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。

迭代 初始 1 2 3 4

S {1}

u -

dist[2] dist[3] dist[4] dist[5] 10

maxint

30

100

算法设计

1．用分治算法求给定二叉树的高度。 2．用合适算法求解装载问题。

第 8 页 共 9 页

3．用贪心法求解部分背包问题，已知n=3，C=40，（w1，w2，w3）=（28，15，24），（p1，p2，p3）=（35，25，24）。

4．给定a，用二分法设计出求an的算法。

5．用回溯法求解{ 1，2，3，4，5 }，这5个自然数中任取3个数的组合。

第 9 页 共 9 页