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)

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