3.6.1 几种解题策略

优质

小牛编辑

133浏览

2023-12-01

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 &gt;= x2:
    if x1 &gt;= x3: 
        max = x1
    else:
        max = x3
else:
    if x2 &gt;= 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 &gt; 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)

当然，这简直已称不上是一个算法，对我们学习程序设计没什么帮助。