### 3.6.1 几种解题策略 如前所述，对于复杂问题，能够设计出多种多样的算法，并且这些算法各有好坏的不同。 下面我们将对上述最大值问题给出四种解决方法，并讨论每一种策略的好坏。 策略 1：将每个数值与其他两个数值进行比较 由于最大值比其他所有数值都大，所以求最大值的最直接的思路就逐一检查 x1、x2 和x3，看看哪个数值比另外两个数值大。又由于 x1、x2 和 x3 都有可能是最大值，我们可以用 一个三路分支的 if-elif 语句来求解： ``` if x1 >= x2 and x1 >= x3: max = x1 elif x2 >= x1 and x2 >= x3: max = x2 else: max = x3 ``` 分析一下这条 if 语句，可以看出它用到了两个布尔表达式，而每个布尔表达式又是用 and 联结起来的两个比较运算式，因此可能要经过四次比较运算才能得出最大值。看上去没什么 复杂，但这个算法其实是很不好的。考虑从 4 个数值中求最大值的问题，用这个算法就会需 要 3 个布尔表达式，每个表达式都包含用 and 联结的 3 个比较运算式，可能要经过 9 次比较 运算才能得出最大值。对于 n 很大的情形，这个算法最坏需要(n-1)2 次比较才能得到结果， 效率很差，另外在代码形式上也会很难看（用 and 联结起来的 n-1 个比较运算式的长度远远 超出了屏幕上一行的宽度）。 上述算法的问题在于：对每个数据的检测是独立设计的，一个数据的测试信息不会被后 面的测试利用。例如，假设第一个分支发现 x1 大于 x2 但小于 x3，这时我们能够推知 x3 是 最大值。但是上述代码却完全忽略这个信息，只是进入第二个分支继续检测，直至到第三个 分支才得出 x3 是最大值。 策略 2：判定树 执行比较运算 a>b 后，也许不能得出最大值是哪个数据，但肯定可以推知某个数据不是 最大值。因为若 a 大于 b，则 b 不可能是最大值；否则 a 不可能是最大值。后续的比较测试 可以充分利用这个信息，以避免冗余测试。根据这个思路，我们可以将所有测试安排一个合 理的顺序，以便排在后面的测试能够利用前面测试的信息。判定树方法就是这么一种安排测 试顺序的常用方法。假设我们从测试 x1>=x2 开始，如果这个比较运算结果为真，那么接下 去只需要测试 x1 与 x3 的大小，否则只需要比较 x2 和 x3 的大小。可见，每一次测试都产生 两个分支，每个分支又是一次测试，又产生两个分支。如此继续下去，最终形成一个层次结 构，称为判定树（见图 3.12）。  图 3.12 判定树 我们很容易根据判定树作出程序的流程图，并进而转化成 if-else 语句： ``` if x1 >= x2: if x1 >= x3: max = x1 else: max = x3 else: if x2 >= x3: max = x2 else: max = x3 ``` 分析一下图 3.12 中的判定树（或者分析上面的 if 语句也一样）即可发现，为了求得最大 值，只需沿着自顶向下的某一条测试路径走到底即可，而任一路径上的比较运算次数都是两 次。所以，不管三个数值的大小次序是什么，上述算法都只进行两次比较运算，就能得出最 大值。效率与第一种策略要高。但是，这个方法导致的代码结构更加复杂，仍然不适合处理 较大的 n。例如，如果是求 4 个数据中的最大值，就会导致 3 重嵌套的 if-else 语句。 策略 3：顺序处理 前面两种策略都不适合对很多数据求最大值。还有更好的方法吗？ 在为一个问题设计算法时，建议读者可以先问问自己：如果是你，你会如何解决该问题。 就此例而言，对于找三个数的最大值问题，你可能不会费脑筋多想，因为只需看看三个数值 就知道最大值了。但是如果交给你一本数据记录，其中有成千上万的数据，而且没有特定顺 序，你又会怎么找出其中的最大值呢？ 相信你一定会想出这个简单的策略：从头到尾逐一检查每个数值，心中记住当前见过的 最大值；每当遇到更大的数值，就用它替换心中所记的数值。这样，等到所有数据都检查过 了，最后记在心里的就是最大值。 将这个策略写成计算机算法，只需用一个变量（用 max 就好）来记录当前见过的最大值。 当处理完所有数据，max 中存放的就是全体数据中的最大值。下面的代码是三个数据的版本： ``` max = x1 if x2 > max: max = x2 if x3 > max: max = x3 ``` 分析一下这个顺序处理策略可知，它只需要进行两次比较运算就能得到最大值，这一点和第二种策略一样。但是顺序处理策略的代码比第二种策略简单得多，不需要嵌套的 if 语句。 更重要的是，这个策略是可扩展的，能够推广到任意 n 个数据的情形而不降低效率。例如， 如果有 4 个数据，我们只需增加一行语句： ``` max = x1 if x2 > max: max = x2 if x3 > max: max = x3 if x4 > max: max = x4 ``` 或者更简洁地用一个循环来表示，那样连数据变量也可以公用，无需使用 4 个独立变量。 将上述算法推广到对任意 n 个数据求最大值的情形，即可得到一般的求最大值的程序。 代码如下： 【程序 3.12】maxn.py ``` n = input("How many numbers? ") max = input("Input a number: ") for i in range(n-1): x = input("Input a number: ") if x > max: max = x print "max =", max ``` 不难看出，为了从 n 个数据中求得最大值，这个程序只需要执行 n-1 次比较运算。 策略 4：利用现成代码 最后值得一提的是，Python 其实有一个内建函数 max，其功能就是返回若干个数据中的 最大值。如果使用这个函数，代码就简单到了极致，在交互环境下就能方便地解决问题： ``` >>> x1,x2,x3 = input("Input three numbers: ") >>> print "max =", max(x1,x2,x3) ``` 当然，这简直已称不上是一个算法，对我们学习程序设计没什么帮助。