代码之家 › 专栏 › 技术社区 › Gabriel

如何得到python算法的数学方程?

math algorithm python

Gabriel · 技术社区 · 14 年前

好吧,我有点傻,因为我不知道这个,但一个同事问我,所以我在这里问:我写了一个解决他的问题的Python算法。给定x>0,将1到x之间的所有数字相加。

def intsum(x):
  if x > 0:
    return x + intsum(x - 1)
  else:
    return 0

intsum(10)
55

首先,这是什么类型的方程?正确的方法是什么?因为使用其他方法显然更容易得到答案?

8 回复 | 直到 14 年前

Larry 14 年前

这是递归,但出于某种原因,您将其标记为阶乘。

在任何情况下,从1到n的总和也很简单:

n * ( n + 1 ) / 2

(如果愿意,可以对负值进行特殊的大小写。)

Alex Martelli 14 年前

将递归定义的整数序列转换成可以用封闭形式表示的整数序列是离散数学中一个迷人的部分——我衷心推荐 混凝土数学:计算机科学的基础 ,作者:罗纳德·格雷厄姆、唐纳德·克努斯和奥伦·帕塔什尼克(见。例如 wikipedia 关于它的条目)。

但是,您显示的特定序列, fac(x) = fac(x - 1) + x 根据一个著名的轶事,高斯在一年级的时候解决了这个问题——老师给学生们一个塔克斯,让他们把数字从1和100相加,让他们保持一段时间,但两分钟后,有一个年轻的高斯给出了答案5050,并解释道:“我注意到我可以把第一个、一个和最后一个100相加,thaT是101,第二个是2,下一个是99,这又是101,显然重复了50次,所以50次是101,5050“。没有严格的证据,但非常正确,适合6岁的孩子;-)。

以同样的方式(加上真正的初等代数),你可以看到一般情况,正如许多人已经说过的, (N * (N+1)) / 2 (乘积总是偶数,因为其中一个数字必须是奇数和一个偶数;因此,按需要,除以2总是产生一个整数,没有余数)。

Rob Rolnick 14 年前

下面是如何证明 arithmetic progression

S  = 1 +   2   + ... + (n-1) + n
S  = n + (n-1) + ... +   2   + 1
2S = (n+1) + (n+1) + ... + (n+1) + (n+1)
     ^ you'll note that there are n terms there.
2S = n(n+1)
S = n(n+1)/2

edstafford 14 年前

我还不允许评论,所以我只想补充一点,在使用range()时要小心,因为它是0基。你需要使用范围(n+1)来获得想要的效果。

抱歉重复了…

总和(范围(10))!= 55

总和(范围(11))=55

brainjam 14 年前

OP在一篇评论中要求链接到高斯作为一个小学生的故事。

他可能想退房 this fascinating article by Brian Hayes . 它不仅令人信服地表明高斯的故事可能是一个现代的编造,而且概述了如果不看到将数字从1到100求和所涉及的模式是多么困难。事实上,错过这些模式的唯一方法就是通过编写一个程序来解决问题。

本文还讨论了算术级数求和的不同方法,这是运算问题的核心。还有一个无广告版本 here .

Felix Kling 14 年前

拉里对他的公式非常正确,它是计算所有整数和的最快方法。 n .

但是为了完整性,有一些内置的python函数可以在列表中执行您所做的操作。 任意的 元素。例如。

sum()

>>> sum(range(11))
55
>>> sum([2,4,6])
12

或者更一般, reduce()

>>> import operator
>>> reduce(operator.add, range(11))
55

Jerry Coffin 14 年前

假设n+1、n-1+2、n-2+3等等加起来都是同一个数,大约有n/2个这样的实例(如果n是偶数,则正好是n/2)。

Gabriel Å Äerbák 14 年前

您所拥有的被称为算术序列,正如建议的那样,您可以直接计算它,而不需要递归产生的开销。

我会说这是一个家庭作业,不管你说什么。