计算平方和与和的平方之间差值的函数

Question

我正在尝试写一个叫做 sum_square_difference 的函数，这个函数接收一个数字 n，并返回前 n 个自然数的平方和与它们的和的平方之间的差。

我觉得我知道怎么写一个计算平方和的函数。

def sum_of_squares(numbers):
    total = 0
    for num in numbers:
        total += (num ** 2)
    return(total)

我也尝试实现一个计算和的平方的函数：

def square_sum(numbers):  
    total = 0
    for each in range: 
        total = total + each
    return total**2

但是我不知道怎么把这两个函数结合起来计算差值，也不确定我的函数是否正确。

有什么建议吗？我正在使用 Python 3.3。

谢谢。

Answer 1

在这种情况下，提前算一下是很有必要的。你可以推导出封闭形式的解，也就是求平方和的公式和求和的平方的公式。这样一来，代码就变得简单多了（而且是O(1)的复杂度）。

需要帮助理解这两个公式吗？

Answer 2

就像beta说的，

计算这个公式很简单：(sum(i))^2 - (sum(i^2)) :)

A = sum(i) = i*(i+1)/2，这就是从1加到i的总和。

B = sum(i^2) = i*(i+1)*(2*i + 1)/6，这是从1到i的每个数的平方的总和。

然后，A^2 - B = i(i+1)(3(i^2) - i - 2) / 12。

:) 没有循环……只需要一个公式！**

Answer 3

这个函数可以用纯数学的方式写成这样：

用Python语言表示就是：

def square_sum_difference(n):
    return int((3*n**2 + 2*n) * (1 - n**2) / 12)

---

这个公式其实是两个其他公式的简化版：

def square_sum_difference(n):
    return int(n*(n+1)*(2*n+1)/6 - (n*(n+1)/2)**2)

n*(n+1)*(2*n+1)/6 这个公式在这里有介绍，它可以计算前n个自然数的平方和。

(n*(n+1)/2)**2 这个公式用的是三角形数公式，它是前n个自然数的和，然后再把这个和平方。

---

我们也可以用内置的sum函数来实现。代码如下：

def sum_square_difference(n):
    r = range(1, n+1)  # first n natural numbers
    return sum(i**2 for i in r) - sum(r)**2

range(1, n+1) 这个函数会生成前n个自然数的一个迭代器。

>>> list(range(1, 4+1))
[1, 2, 3, 4]

sum(i**2 for i in r) 会返回迭代器中所有数字的平方和，而sum(r)**2 则是返回这些数字和的平方。