算法分析与设计作业参考答案

算法分析与设计作业参考答案

《算法分析与设计》作业参考答案

作业⼀

⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。

2.程序：程序是算法⽤某种程序设计语⾔的具体实现。

⼆、简答题：1.算法需要满⾜哪些性质？简述之。

答：算法是若⼲指令的有穷序列，满⾜性质：

（1）输⼊：有零个或多个外部量作为算法的输⼊。（2）输出：算法产⽣⾄少⼀个量作为输出。 （3）确定性：组成算法的每条指令清晰、⽆歧义。

（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：

（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；

（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质； （3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；

（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。 答：将递归算法转化为⾮递归算法的⽅法主要有：

（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。该⽅法通⽤性强，但本质上还是递归，

只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。（2）⽤递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。

后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。

三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]

交换a[j]、a[j+1]；

分析该算法的时间复杂性。

答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。

（1）设⽐较⼀次花时间1；

（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=i

n j i n 1

)(1

（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。答：算法思想：对于⼆叉树T ，若为空树，则其⾼度为0；否则，分别求其左⼦树和右⼦树的⾼度，最

⼤者加1 即为树T 的⾼度。其描述如下：)

1(2)()(1

-=-=∑=n n

i n n T n

i

int BTLength(BT T)

//为了便于描述，假定⼆叉树类型为BT。T 的左⼦树为T.lchild，右⼦树为T.rchild。

{

if(T= =NULL) return 0; //T为空树

return max(BTLength(T.lchild),BTLength(T.rchild)) +1

}

3.设计⼀个分治算法来判定给定的两棵⼆叉树T1 和T2 是否相同。

答：算法思想：对于两棵⼆叉树T1 和T2，若其根结点值相同，且其左右⼦树分别对应相同，则T1＝T2；否则T1≠T2。其描述如下：boolean BTEQUAL(BT T1，BT T2)

//为了便于描述，假定⼆叉树类型为BT。⼆叉树T的左⼦树为T.lchild，右⼦树为T.rchild。

⼆叉树T的根结点值T.data。{

if(T1= =NULL&& T2= =NULL) return True; //均为空树

if(T1&&T2&&T1.data==T2.data&&BTEQUAL(T1.lchild,T2.lchild)&&BTEQUAL (T1.rchild, T2.rchild))

return True;

return False;

}

4.给出⼀个分治算法来找出n 个元素的序列中的第2⼤元素，并分析算法的时间复杂度。

答：算法思想：当序列A[1..n]中元素的个数n=2 时，通过直接⽐较即可找出序列的第2 ⼤元素。当n>2 时，先求出序列A[1..n-1]中的第1 ⼤元素x1 和第2 ⼤元素x2；然后，通过2次⽐较即可在三个元素x1x2 和A[n]中找出第2 ⼤元素，该元素即为A[1..n]中的第2 ⼤元素。

算法描述如下：SecondElement(A[low..high],max1,max2)

{//假设主程序中调⽤该过程条件为high-low>=2

if(hight-low= =2)

{

if(A[low]

else {max2= A[high];max1=A[low];}

}else

{

SecondElement(A[low..high],x1,x2);

if(x1<=A[n]) { max2=max1; max1=A[n];}

else if(x2>=A[n]) { max2=x2; max1=x1; }

else { max2=A[n]; max1=x1; }

}

}

该算法的时间复杂度满⾜如下递归⽅程：T(n)=T(n-1)+2；T(2)=1。解得T(n)=2n-3。

作业⼆

⼀、名词解释：1.MST 性质：G=(V,E)是连通带权图，U 是V 的真⼦集。如果(u,v)∈E ，且u ∈U ，v ∈V-U ，且在所有这样的边中，(u,v)的权c[u][v]最⼩，那么⼀定存在G 的⼀棵最⼩⽣成树，它以(u,v)为其中⼀条边。这个性质称为MST 性质。

2.⼦问题的重叠性质：递归算法求解问题时，每次产⽣的⼦问题并不总是新问题，有些⼦问题被反复计算多次，这种性质称为⼦问题的重叠性质。

⼆、简答题：1.简述动态规划算法求解的基本要素。 动态规划算法求解的基本要素包括：

（1）最优⼦结构是问题能⽤动态规划算法求解的前提；

（2）动态规划算法，对每⼀个⼦问题只解⼀次，⽽后将其解保存在⼀个表格中，当再次需要解此⼦问

题时，只是简单地⽤常数时间查看⼀下结果，即重叠⼦问题。2.备忘录⽅法和动态规划算法相⽐有何异同？简述之。

备忘录⽅法是动态规划算法的变形。与动态规划算法⼀样，备忘录⽅法⽤表格保存已解决的⼦问题的答案，在下次需要解此问题时，只要简单地查看该⼦问题的解答，⽽不必重新计算。

备忘录⽅法与动态规划算法不同的是，备忘录⽅法的递归⽅式是⾃顶向下的，⽽动态规划算法则是⾃底向上递归的。因此，备忘录⽅法的控制结构与直接递归⽅法的控制结构相同，区别在于备忘录⽅法为每个解过的⼦问题建⽴了备忘录以备需要时查看，避免了相同的⼦问题的重复求解，⽽直接递归⽅法没有此功能。3.贪⼼算法求解的问题主要具有哪些性质？简述之。

贪⼼算法求解的问题⼀般具有⼆个重要的性质：⼀是贪⼼选择性质，这是贪⼼算法可⾏的第⼀个基本要素；另⼀个是最优⼦结构性质，问题的最优⼦结构性质是该问题可⽤贪⼼算法求解的关键特征。

三、算法编写及算法应⽤分析题：1.设计求解如下最⼤⼦段和问题的动态规划算法。只需给出其递推计算公式即可。

最⼤⼦段和问题：给定由n 个整数（可能为负整数）组成的序列a 1a 2 … an ，求该序列形如Σi ≤k ≤j ak 的⼦段和的最⼤值。当所有整数均为负整数时定义其最⼤⼦段和为0。依次定义，所求的最优值为max{0, max1≤i ≤j ≤n Σi ≤k ≤j ak }。

答：下⾯给出求解该问题的动态规划算法中的递推计算公式。

记 b (j )=max1≤i ≤j {Σi ≤k ≤j ak }，1≤j ≤n ，则所求最⼤⼦段和为max1≤j ≤nb (j )。⽽计算b [j ]的递推计算公式为：b (0)=0 b (j )=max{b (j -1)+aj , aj }， 1≤j ≤n 。

该算法的时间复杂度为O(n )；空间复杂度为O(n )。2.关于多段图问题。设G ＝(V ，E)是⼀个赋权有向图，其顶点集V 被划分成k>2个不相交的⼦集V i ：1i k ≤≤，其中，V 1和V k分别只有⼀个顶点s （称为源）和⼀个顶点t （称为汇），图中所有的边（u,v ），i u V ∈，1i v V +∈。求由s 到t 的最⼩成本路径。

（1）给出使⽤动态规划算法求解多段图问题的基本思想。

（2）使⽤上述⽅法求解如下多段图问题。

s t

V1V2V3V4V5

解：（1）基本思想：设P(i,j)是从Vi 中的节点j 到汇点t 的最⼩成本路径，Cost(i,j)是其成本。则i+1Cost(i,j)=min{c(j,h)+Cost(i+1,h)|h V ,(j,h)E}∈∈。

边界条件是（1）若h=t ，则Cost(h,t)

＝0；（2）Cost(k-1,j)＝c(j,t)。

（2）求解过程可以表⽰为：

s t

V1V2V3V4V5

其中每个节点标⽰的序偶(p,q)中，p 表⽰节点到t 的成本，q 表⽰后继节点的编号。从⽽，最优路径为：1→2→7→10→12和1→3→6→10→12，成本为16。

3.最优⼆元归并问题：已知将两个分别包含 a 个和b 个记录的已分类⽂件归并在⼀起得到⼀个分类⽂件需作a +b 次记录移动。现有n 个已分类⽂件F 1,F 1,?,Fn ，它们的记录个数分别为l 1, l 2,?, ln 。现在考虑使⽤⼆元归并模式将这n 个⽂件归并成⼀个分类⽂件，要求记录移动次数最少。设计⼀个贪⼼算法来求解⼀种最优的⼆元归并（即记录移动次数最少的⼆元归并）。

答：（1）贪⼼准则：依次将⽂件序列中记录最少的两个⽂件进⾏归并成⼀个⽂件，直到⽂件序列中只

剩下⼀个⽂件为⽌。 （2）贪⼼算法：Algorithm BINARYTREE

输⼊：n 个单结点⼆元树列表L ，这些棵树的根结点的权分别为l 1, l 2,?, ln 。 输出：⼀棵最优⼆元归并树L BeginFor i ←1 To n -1 Do

GETNODE(T ) //该过程产⽣⼀个新结点T

LCHILD(T)←LEAST(L) //将表L 中其根权最⼩的树取出并作为T 的左孩⼦

RCHILD(T)←LEAST(L) ////将表L 中其根权最⼩的树取出并作为T的右孩⼦

WEIGHT(T)←WEIGHT(LCHILD(T))+WEIGHT(RCHILD(T))

Repeat

Return(L)

End.

4.带限期的作业调度问题：n 个作业需要在⼀台机器上处理，每个作业可在单位时间内完成。每个作业i

都有⼀个截⽌期限di>0(di 为整数)，当且仅当作业i 在它的截⽌期限之前被完成，获得pi>0 的效益。

⼀种可⾏的调度⽅案为n 个作业的⼀个⼦集J，其中J 中的每个作业都能在各⾃的截⽌期限内完成。

该可⾏调度⽅案的效益是J 中作业的效益之和。试设计贪⼼算法求效益最⼤的可⾏调度⽅案（即最优调度⽅案）。

答：（1）贪⼼准则：从J=开始，不断添加作业到J 中。每次加⼊J 的作业是保证J 是可⾏的

前提下使得J 中效益达到最⼤。即，按照pi 由⼤到⼩的次序来考虑作业。