计算前1000个阶乘的累计和？

Question

我之前问过类似的问题，但这次有点不同。以下是我的计算过程。我得到的结果和使用Python内置函数得到的结果不一致。请告诉我我哪里做错了，我相信内置函数的结果一定是正确的。

我的计算过程：

def fact_cum(n):
    f = 1
    for x in range(1, n +1):
        f *= x
    print f

fact_cum(1000) 

---

Python的内置函数：

import math
def cumFact(): 
    x = sum(math.factorial(f) for f in range(1000))
    print x

cumFact()

Answer 1

首先，大家都提到的一个大问题是：你并没有真正计算阶乘的和，或者返回一个可以传给 sum 的值，你只是把阶乘的结果打印出来而已。

即使你解决了这个问题，你实际上计算的也不是 sum(math.factorial(i) for i in range(1000))，而是 sum(math.factorial(i) for i in range(1, 1001))。如果你想要前者，你需要从 0! 开始，而不是 1!。

正如 mgilson 指出的，你不需要每次计算阶乘时都重新开始。做累积阶乘的关键在于，你可以同时计算阶乘和它们的和，这样你只需要生成每个阶乘一次：

import itertools

def factorials():
    fact = 1
    for i in itertools.count(1):
        yield fact
        fact *= i

def cum_factorials():
    cum = 0
    for fact in factorials():
        cum += fact
        yield cum

def cum_factorial(n):
    cf = cum_factorials()
    consume(cf, 1000)
    return next(cf)

（这需要使用 itertools 中的 consume 函数，或者从 more-itertools 导入……或者你应该能自己写出来。）

---

显然，你不需要通过生成一个无限的累积阶乘列表来挑选第 n 个，但这样可以避免让 Haskell 程序员嘲笑你的语言选择，这难道不是最重要的吗？

说得更严肃一点，想象一下你在纸上怎么做这个。首先，你会写下一列阶乘：

1
1 * 1 = 1
1 * 2 = 2
2 * 3 = 6
6 * 4 = 24
...

然后，你会在旁边再写一列，逐步累加这些阶乘的和。

1             1
1 * 1 = 1     1 + 1 = 2
1 * 2 = 2     2 + 2 = 4
2 * 3 = 6     4 + 6 = 10
6 * 4 = 24    10 + 24 = 34
24 * 5 = 120  34 + 120 = 154
...           ...

那么，如何在 Python 中做到这一点呢？

一种方法是把算法重新组织成可以顺序书写的样子，像这样：

def cum_fact(n):
    cumulative_sum = 1
    latest_factorial = 1
    for i in range(1, n):
        latest_factorial *= i
        cumulative_sum += latest_factorial
    return cumulative_sum

但这实际上比你在纸上做的更难理解，也更容易出错。

另一种选择是想办法让 Python 做你在纸上做的事情：取一个无限序列 (1, 2, 3, 4, …)，对这个序列应用一个简单的变换 *=，得到一个新的序列 (1, 1, 2, 6, 24, …)，然后再对这个序列应用另一个简单的变换 +=，得到另一个新序列 (1, 2, 4, 10, 34, …)。最后，你只需要这个序列中的第 1001 个值，所以……丢掉前 1000 个，取下一个。

itertools.count(1) 就给你提供了第一个序列 (1, 2, 3, …)。你可以这样写：

def count(n):
    while True:
        yield n
        n += 1

这就是一个生成器函数。我不认为我能在一段话里解释这个概念，但基本的想法是：它不是返回一个值，而是生成一系列值。每次遇到 yield 时，调用者就会得到一个值。每次你请求下一个值时，它会从上次停止的地方继续，直到下一个 yield。如果你在交互式解释器中玩一会儿这个概念，可能会更容易理解——不过，更好的办法是去网上找一些教程。

接下来，虽然你可以使用折叠函数来应用每个变换，但这可能对现在的你来说有点复杂，所以我用两个生成器函数把它们写得很明确。

最后，consume 本身有点不同——它不是一个生成器，而是一个接受并修改迭代器的函数，像这样：

def consume(iter, n):
    for i in range(n):
        next(iter)

所以，如果你有 [1, 2, 3, 4, 5, 6, …]，并且你 consume 前 3 个元素，你就会得到 [4, 5, 6, …]。

Answer 2

你的阶乘函数从来没有返回任何东西。把那个 print 改成 return 吧：

def fact(n):
    f = 1

    for x in range(1, n +1):
        f *= x

    return f

现在你可以把结果加起来了：

sum(fact(n) for n in range(1, 1000 + 1))

因为你在用 Python 2，所以要用 xrange 代替 range。range 会在内存中创建一个列表，而 xrange 只是创建一个迭代器。