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

算法分析：

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

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

不能再拆。

解题算法:

题型三：

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

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

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

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