《算法分析与设计》期末考试复习题纲(完整版)(4)

六、算法设计题 使用贪心算法求解。 题型一： 开会问题：

某公司的会议很多，以至于全公司唯一的会议室不够用。现在给出这段时期的会议时间表，要求你适当删除一些会议，使得剩余的会议在时间上互不冲突，要求删除的会议数最少。 解题算法:

template

void GS (int n, Type s[], Type f[], bool A[]) {

A[1]=false; int j=1; int sum=0;

for (int i=2;i<=n;i++) {

if (s[i]>=f[j]) { A[i]=false; j=i; } else {A[i]=true; sum++;} } } 题型二：

试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，写出该算法。先看看几个n比较小的例子，看能否从中找出规律：

16

算法分析：

? 猜想一下是不是将n拆成尽量多的数乘积最大？（拆出的数中最小为2）。 ? 为了使因数个数尽可能多，我们用n减2、3?i，直到n0，则均匀地分给前面各项。

? 因此我们可以得到一个贪心策略，即将n不停地拆分开来，使得所有的数都不同且

不能再拆。

解题算法:

17

题型三：

田忌赛马：如果3匹马变成n匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子。已知国王和田忌的所有马的奔跑速度，并且所有马奔跑的速度均不相同，现已经对两人的马分别从快到慢排好序，请设计一个算法，帮助田忌赢得最多的银子。 解题思路：

? 先对两组马按速度排序。

? 如果田忌(A)最快的马比齐王(B)最快的马快,直接赢; ? 如果A最快的马比B慢,用A最慢的马拼B最快的马; ? 如果A最慢的马比B最慢的马快,直接拼掉;

? 如果A最慢的马比B最慢的马慢,用A最慢的马拼B最快的马; ? 如果A和B最快和最慢的马都速度相同,用A最慢的马拼B最快的马 算法分析:

18