算法导论第十五章答案

j
j
w(i, j) = ∑ pl + ∑ ql
l =i
l =i −1
(5-5)
OPTIMAL-BST(p, q, n)
1 for i ← 1 to n + 1
2
do e[i, i-1] ←qi-1
3
w[i, i-1] ←qi-1
4 for l ← 1 to n
5
do for i ← 1 to n – l + 1
15-4 (5-19) Planning a company party. Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the supervisor relation forms tree rooted at the president. The personal office has ranked each employee with a conviviality rating, which is a real number. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.
To print out all the stations, call PRINT-STATIONS (l, l*, n)

26.1-2
26.2-1
26.2-4
14
《算法导论（第二版） 》参考答案 26.3-1 s–1–6–t s–2–8–t s–3–7–t 26.3-3
26.4-2 根据 26.22 对每个顶点执行 relabel 操作的次数最多为 2|V|-1 所以对每条边检测次数最多为 2*（2|V|-1）次 O（V） 在剩余网络中最多 2|E|条边 O（E） 所以为 O（VE）
f1[ j ] f 2 [ j 1] t2, j 1 a1, j f 2 [ j ] f1[ j 1] t1, j 1 a2, j
所以有：
f1[ j ] f 2 [ j ] f 2 [ j 1] t2, j 1 a1, j f1[ j 1] t1, j 1 a2, j
6
《算法导论（第二版） 》参考答案
最终答案：((A1A2)((A3A4)(A5A6))) 15.2-2
15.3-2 没有重叠的子问题存在 15.3-4 这题比较简单,由 P328 的(15.6)(15.7)展开两三步就可以看出来. 15.4-3 先初始化 c 数组元素为无穷大
7
《算法导论（第二版） 法， 最好是像书上画一颗递归树然后进行运算。
1
《算法导论（第二版） 》参考答案
注意题目中的要求使用递归树的方法，最好是像书上画一颗递归树然后进行运 算。 4.2.2 证略 4.2.3 由 2 i n 得 i=lgn
T (n) 2 i cn cn
i 0
由课本 P328（15.6） (15.7)式代入，可得：
min( f1[ j 1] a1, j , f 2 [ j 1] t2, j 1 a1, j ) min( f 2 [ j 1] a2, j , f1[ j 1] t1, j 1 a2, j ) min( f1[ j 1], f 2 [ j 1] t2, j 1 ) a1, j min( f 2 [ j 1], f1[ j 1] t1, j 1 ) a2, j f 2 [ j 1] t2, j 1 a1, j f1[ j 1] t1, j 1 a2, j

c(j) = min {c(i − 1) + linecost(i, j)} .
Three-hole punch your paper on submissions. You will often be called upon to “give an algorithm” to solve a certain problem. Your write-up should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of the essay should provide the following:
(a) Argue that this problem exhibits optimal substructure.
Solution: First, notice that linecost(i, j) is defined to be � if the words i through j do not fit on a line to guarantee that no lines in the optimal solution overflow. (This relies on the assumption that the length of each word is not more than M .) Second, notice that linecost(i, j) is defined to be 0 when j = n, where n is the total number of words; only the actual last line has zero cost, not the recursive last lines of subprob­ lems, which, since they are not the last line overall, have the same cost formula as any other line.

第1章算法在计算中的作用什么是算法?为什么要对算法进行研究?相对于计算机中使用的其他技术来说，算法的作用是什么?在本章中，我们就要来回答这些问题.1. 1算法简单来说，所谓抹法(also*llem)就是定义良好的计算过程，它取一个或一组值作为输入，并产生出一个或一组值作为输出。

亦即，算法就是一系列的计算步驭，用来将输人数据转换成输出结果。

我们还可以将算法看作是一种工具。

用来解决一个具有良好规格说明的计算问题。

有关该问题的表述可以用通用的语言，来规定所需的输人/输出关系。

与之对应的算法则描迷了一个特定的计算过程，用于实现这一输人/输出关系例如.假设需要将一列数按非降顺序进行排序。

在实践中，这一问皿经常山现。

它为我们引入许多标准的算法设计技术和分析工具提供了丰富的问题场景。

下面是有关该排序间题的形式化定义，输入:由n个数构成的一个序列编出:对输人序列的一个排列(重排)例如，给定一个输人序列(31. 41. 59. 26, 41, 58).一个排序算法返回的怕出序列是(26,31. 41. 41. 58, 59).这样的一个输人序列称为该排序问趣的一个实例G.-e)。

一般来说，某一个问题的实例包含了求解该间题所需的输人(它满足有关该同题的表述中所给出的任何限制)。

在计算机科学中，排序是一种基本的操作(很多程序都将它用作一种申间步骤)。

因此，迄今为止，科研人员提出了多种非常好的排序算法。

对于一项特定的应用来说，如何选择最佳的排序算法要考虑多方面的因素，其中最主要的是考虑待排序的数据项数、这些数据项已排好序的程度、对数据项取值的可能限制、打算采用的存储设备的类型〔内存、磁盘、磁带)等。

如果一个算法对其每一个输人实例，都能输出正确的结果并停止，则称它是正确的。

我们说一个正确的算法解决了给定的计算向题不正确的算法对于某些输人来说.可能根本不会停止或者停止时给出的不是预期的结果.然面，与人们对不正确算法的看法相反，如果这些算法的错误率可以得到控制的话，它们有时也是有用的.关子这一点，在第31章中研究用于寻找大质数的算法时介绍了一个例子。