算法复习题(4)

显然ERT??也是最优解，将原来的最优解中所有这样类似于反序对的程序互换位置，得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按fi/li的非增次序来存放得到的顺序。命题得证。 27.假定要把长为l1,l2,?, ln的n个程序分布到两盘磁带T1和T2上，并且希望按照使最大检索时间取最小值的方式存放，即，如果存放在T1和T2上的程序集合分别是A和B，那么就希望所选择的A和B使得max{?i?Ali,?i?Bli}取最小值。一种得到A和B的贪心方法如下：开始将A和B都初始化为空，然后一次考虑一个程序，如果?i?Ali=min{?i?Ali,?i?Bli}，则将当前正在考虑的那个程序分配给A，否则分配给B。证明无论是按l1≤l2≤?≤ln或是按l1≥l2≥?≥

ln的次序来考虑程序，这种方法都不能产生最优解。

证明：按照l1≤l2≤?≤ln存放不会得到最优解，举例如下：

3个程序（a,b,c）长度分别为（1,2,3），根据题中的贪心算法，产生的解是A={a,c}B={b}，则max{?i?Ali,?i?Bli}=4，而事实上，最优解应为3，所以得证.

按照l1≥l2≥?≥ln的次序存放也不会得到最优解，举例如下：

5个程序（a,b,c,d,e）长度分别为（10,9,8,6,4）根据题中的贪心算法，产生的解是A={a,d,e}B={b,c}，则max{?i?Ali,?i?Bli}=20，而事实上，最优解应为19，所以得证。

（p1,.....p7）（d1,.....d7）28.①当n=7，=(3,5,20,18,1,6,30) 和=(1,3,4,3,2,1,2)

时，算法5.4所生成的解是什么？

② 证明即使作业有不同的处理时间定理5.3亦真。这里，假定作业I的效益pi>0，要用的处理时间ti>0，限期di≥ti.

解：①根据pi的非增排序得到(p7,p3,p4,p6,p2,p1,

p5)=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2)，按照算法5.4生

成的解为：

a.J(1)=7 b.J(1)=7,J(2)=3

c.J(1)=7,J(2)=4,J(3)=3

d.J(1)=6, J(2)=7,J(3)=4,J(4)=3；

②证明：显然即使ti>0（di≥ti），如果J中的作业可以按照?的次序而又不违反任何一个期限来处理，即对?次序中的任一个作业k，应满足dk ≥?tj，

j?1k则J就是一个可行解。

下面证明如果J是可行解，则使得J中的作业可以按照di1,di2,?, din排列的序列?处理而又不违反任何一个期限。

因为J是可行解，则必存在??=r1r2?rn，使得对任意的rk，都有dk≥

?tj?1kj，我们设?是按照di1≤di2≤,?,≤din排列的作业序列。假设????，那么

令a是使ra?ia的最小下标，设rb=ia，显然b>a，在??中将ra与rb相交换，因为drb≤dra，显然ra和rb可以按期完成作业。

还要证明ra和rb之间的作业也能按期完成。因为drb≤dra，而显然二者之间的所有作业rt，都有drt>drb，又由于?是可行解，所以?tk≤drb≤drt。所以

k?1b作业ra和rb交换后，所有作业可依新产生的排列???==s1s2?sn的次序处理而不违反任何一个期限，连续使用这种方法，??就可转换成?且不违反任何一个期限，定理得证。

29．① 已知n-1个元素已按min-堆的结构形式存放在A(1),?,A(n-1)。现要将另一存放在A(n)的元素和A(1:n-1)中元素一起构成一个具有n个元素的min-堆。对此写一个计算时间为O(logn)的算法。

② 在A(1:n)中存放着一个min-堆，写一个从堆顶A(1)删去最小元素后将其余元素调整成min-堆的算法，要求这新的堆存放在A(1:n-1)中，且算法时间为O(logn).

③ 利用②所写出的算法，写一个对n个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。

解：① procedure INSERT(A,n)

integer i, j, k

j←n ; i←?n/2? while i≥1 and A[i]>A[j] do k←A[j];

A[j]←A[i]; A[i]←k

j←i ;

i←?i/2?

repeat end INSERT

② procedure RESTORE(A,l,n) integer i, j, k x←A[n];

A[n]←A[l]

i←1 j←2*i

while j≤n-1 do

if (j< n-1) and (A[j]> A[j+1])

then j←j+1 endif

if (x>A[j])

then A[i]←A[j]; i←j;j←2*i else i←n endif

repeat end RESTORE

③ procedure HEAPSORT(A,n) integer i, k

for i=?n/2? to 1 step –1 do RESTORE(A, i, n) repeat

for i=n to 2 step –1 do k←A[1]; A[1]←A[i]; A[i]←k RESTORE(A, 1, i-1) repeat end HEAPSORT

30．① 证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足n mod (k-1)=1.

② 证明对于满足 n mod (k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k.

证明：① 设某棵树内部节点的个数是m，外部结点的个数是n，边的条数是e，

则有

e=m+n-1和 e=mk

mk=m+n-1 ? (k-1)m=n-1 ? n mod (k-1)=1 ② 利用数学归纳法。

当n=1时，存在外部结点数目为1的k元树T，并且T中内部结点的度为k；

假设当 n≤m，且满足n mod (k-1)=1时，存在一棵具有n个外部结点的k元树T，且所有内部结点的度为k；

我们将外部结点数为n(n为满足n≤m，且n mod (k-1)=1的最大值)的符合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点，易知新生成的树T’中外部结点的数目为n+(k-1)，显然n为满足n mod (k-1)=1，且比m大的最小整数，而树T’每个内结点的度为k，即存在符合性质的树。

综合上述结果可知,命题成立。

31．① 证明如果n mod (k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,q2,?, qn）生成一棵最优的k元归并树。

② 当（q1,q2,?, q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。 解：①通过数学归纳法证明：

对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。 假定该算法对于（q1,q2,?, qm），其中m =(k-1)s+1 (0 ≤ s)，都生成一棵最优树.

则只需证明对于(q1,q2,?, qn)，其中n=(k-1)(s+1)+1，也能生成最优树即可。

不失一般性，假定q1≤q2≤?≤qn，且q1,q2,?, qk是算法所找到的k棵树的WEIGHT信息段的值。于是q1,q2,?, qk棵生成子树T，设T?是一棵对于（q1,q2,?, qn）的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是q1,q2,?, qk，则可以用q1,q2,?, qk和P现在的儿子进行交换，这样不增加T?的带权外部路径长度。因此T也是一棵最优归并树中的子树。于是在T?中如果用其权为q1+q2+?+qk的一个外部结点来代换T，则所生成的树T??是关于(q1+q2+?+qk,qk?1,?,qn)的一棵最优归并树。由归纳假设，在使用其权为q1+q2+?+qk的那个外部结点代换了T以后，过程TREE转化成去求取一棵关于(q1+q2+?+qk,qk?1,?,qn)的最优归并树。因此TREE生成一棵关于(q1,q2,?, qn)的最优归并树。

32．对n=7, ( p1,...,p7)=(35，30，25，20，15，10，5) 和( d1,...,d7)=(4，2，4，3，4，8，3)的有限期作业调度问题使用教材中作业排序的更快算法求解最优解。（要求描述时间片数组F（i）和对应集合的变化过程）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法复习题(4)在线全文阅读。