By

文章目錄

编写一个程序, 读入一个正整数, 把所有那些连续的和为给定的正整数的正整数找出来。例如,如果输入27, 发现2~7、8~10、13与14的和是27, 这就是解答:如果输入的是10000, 应该有18~142、297~1328、388~412、1998~2002这4组。注意, 不见得一定会有答案,譬如说4、16就无解; 另外, 排除只有一个数的情况, 否则每一个输入就都至少有一个答案, 就是它自己.

说明: 任何人看到这个题目都会马上想到一个办法, 把所有的和算出来, 与输入比较。曾经看到过如下的一个解法, 如下程序所示

1
2
3
4
5
6
7
8
9
10
def bad_given_sum(n):
    result = []
    mid = int(n / 2)
    for i in range(1, mid + 1):
        s = i
        for j in range(i + 1, mid + 1 + 1):
            s += j
            if s == n:
                result.append((i, j))
    return result

它的做法是先固定一个i, sum变量, 接着令j 从i + 1起变化, 每次都把j的值加到sum 中，
因此sum中的值就是i, i + 1,…,这些连续整数的和. 因此令i 从1 编导n / 2(n是给定的数), 而j从计1变到n / 2 + 1, 如果有一个和与n相同, 就显示i与j,表示n的值是i到j这一串连续的正整数的和。为什么i要从1到n / 2? 很简单, 如果i是n / 2,下一个数就是n / 2 + 1, 于是这两个(连续的)数的和n / 2 + (n / 2 + 1) = n + 1就大于n, 所以i最多只能到n / 2; 同理可以说明j 不可以大过n / 2 + 1

这个程序当然是对的, 但运行太慢了! 用10000作为输入, 它一共执行了311.71秒, 也就是5分钟多: 但事实上, 这个题目可以在不到一秒之内得出答案, 而且当输入1000000(100万)时,也不过用178.12秒(3分钟)左右而已,相比之下bad_given_sum的效率实在太低了。(本书写于1988年，那时候计算机性能还不够好)

问题出在什么地方? 加法次数太多了。在上面的程序中, i与j的关系永远满足1 <= i <= n / 2, i + 1 <= j <= n / 2 + 1, i < j, 每一组i与j都会做一次加法,所以就一共做了大约n ^ 2 / 8个加法(这是个近似值); 当n = 10000时,就大约是1250万个。

不过, 一个好程序员应该研究是否有更好的方法存在, 事实上就有一个, 大约需要2n
个加法就足够了, 能想得出来吗? 下面是几点有用的提示:

  1. 如果在求和时是用i + (i + 1) + … + j表示, 那么 i <= n / 2; 这是上面提过的。
  2. 如果某个和i + (i + 1) + … + j比给定的值大, 那么把和变小, 但仍然维持是一串连
    续整数的和时, 拿掉j变成i + (i + 1) + … + (j - 1),不如拿掉i变成(i + 1) + … + j。为什么? 因为j比i大, 拿掉j, 和就下降太快了, 不如拿掉i, 再慢慢降低(能用数学来证明吗?)
  3. 如果和i + (i + 1) + … + j比给定值小, 加上j + 1变成的i + … + j + j + 1; 道理同前。

有了这几点, 编程应该不会是件难事了。

解答见given_sum.py

打赏作者

文章目錄