算法分析与设计陈慧南课后答案

第一章

1-3. 最大公约数为 1。快 1414 倍。

主要考虑循环次数，程序 1-2 的 while 循环体做了 10 次，程序 1-3 的 while 循环体做了 14141 次（14142-2

循环）

若考虑其他语句，则没有这么多，可能就 601 倍。

第二章

2-8.（1）画线语句的执行次数为 。 。划线语句的执行次数应该理解为一格整体。

（2）画线语句的执行次数为 。 。

，所以， 。

（3） 由（1）、（2）可知，取 ， ， ，当 时，有 ，

所以 。

2-11. (1) 当 时， ，所以 ， 。可

选 ， 。对于 ， ，即 。注意：是 f(n)和 g(n)的关系。

（ 2 ） 当 时 ， ， 所 以 ， 。 可 选

， 。对于 ， ，即 。

（ 3 ） 因 为 ， 。 当 时 ，

， 。所以，可选 ， ，对于 ， ，

即 。

第二章

当 时， 。所以， 。

第五章

5-4. SolutionType DandC1(int left,int right)

{

}

5-7. template <class T>

int SortableList<T>::BSearch(const T&x,int left,int right) const

{

if (left<=right)

{

9．