计算机算法设计与分析期末复习资料

3．按渐近阶排列表达式

按照渐近阶从低到高的顺序排列以下表达式：4n2，logn，3n，20n，2，n2/3。又n!应该排在哪一位？ 分析与解答：

按渐近阶从低到高，函数排列顺序如下：2，logn，n2/3，20n，4n2，3n，n！。

4.算法效率

n

(1)假设某算法在输入规模为n时计算时间为T(n)=3*2。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？

2

(2)若上述算法的计算时间改进为T(n)=n，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题？

(3)若上述算法的计算时间进一步改进为T(n)=8，其余条件不变，那么在新机器上用t秒时间能解输入规模为多大的问题？ 分析解答：

2n1

(1)设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有：t=3*2=3*2/64，解

得你n1=n+6。

22

(2)n1=64nn1=8n。

(3)由于T(n)=常数，因此算法可解任意规模的问题。

5．阶乘函数

阶乘函数可递归地定义为：

?1n?0

n!?? ?n(n?1)!n?0

int factorial(int n) {

if(n = = 0) return 1; return n * factorial(n-1); }

6．Fibonacci数列

无穷数列1，1，2，3，5，8，13，21，34，55，??，称为Fibonacci数列。它可以递归地定义为：

?1n?0

?F(n)?1n?1?

?F(n?1)?F(n?2)n?1 ?

请对这个无穷数列设计一个算法，并进行描述（自然语言描述和VC++描述）.

第n个Fibonacci数可递归地计算如下：

int fibonacci(int n) {

if (n <= 1) return 1;

returnfibonacci(n-1)+fibonacci(n-2); }

7．循环赛日程表

设有n=2k个运动员要进行兵乓球循环赛。现在要设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。

请设计一个算法解决以上问题，并进行描述（自然语言和C++语言）

按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。

8．有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 分析回答以下两个问题：

(1)分析以上最优装载问题具有贪心选择性质 (2)用C++程序进行正确的算法描述 分析与解答：

(1) 设集装箱已依其重量从小到大排序，(x1,x2,?,xn)是最有装载问题的一个最优解。

又设k=min{i|xi=1}。易知，如果给定的最有装载问题有解，则1≤k≤n。 ② 当k=1时，(x1,x2,?,xn)是满足贪心选择性质的最优解。 ②当k>1时，取y1=1;yk=0;yi=xi,1

因此，()是所给最有装载问题的可行解。

另一方面，由知，()是满足贪心选择性质的最优解。所以，最优装载问题具有贪心选择性质。

(2)最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下。

template

void Loading(int x[], Type w[], Type c, int n) {

int *t = new int [n+1]; Sort(w, t, n);

for (int i = 1; i <= n; i++) x[i] = 0;

for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];} }