logo标签列表

如何获取Python算法的数学方程？

pythonalgorithmmath
5
好的，我感觉有点傻不愚钝，不知道这个问题的答案，但是我的同事问了，所以我在这里问：我编写了一个解决他问题的Python算法。给定x>0，将从1到x的所有数字相加。
def intsum(x):
  if x > 0:
    return x + intsum(x - 1)
  else:
    return 0

intsum(10)
55

首先，这是什么类型的方程？以及获得答案的正确方法是什么？显然，使用其他方法会更容易一些。
8个回答
15

这是递归，但因某种原因你把它当做阶乘来标记。

无论如何，从1到n的总和也可以简单地表示为：

n * ( n + 1 ) / 2

(如果需要，您可以针对负值进行特殊处理。)

谢谢，我只是使用了最接近的数学术语作为函数名，并将其更改以反映。现在它的名称是“算术序列”。感谢您的协助。 - Gabriel
3
高斯在9岁时发现这个定理的故事是我最喜欢的轶事之一 :-) - Jochen Ritzel
每个随机黑客的电锯实现 asciify 或去掉重音符号的时候，都会把 Gauß 这个名字改成 Gau :-(。 - John Machin
@THC4k，你应该提供一个链接给这个故事，我很想读一下。 - Gabriel
@Gabriel，starblue的文章末尾有一个链接http://www.americanscientist.org/issues/pub/2006/3/gausss-day-of-reckoning - Unreason
8
将递归定义的整数序列转换为可以用封闭形式表示的序列是离散数学的一个迷人部分 - 我强烈推荐《具体数学：计算机科学基础》，作者是Ronald Graham，Donald Knuth和Oren Patashnik（例如，请参见wikipedia关于它的条目）。
然而，您展示的特定序列fac(x) = fac(x - 1) + x，据著名轶事称，高斯在一年级时就解决了这个问题 - 老师让学生们将从1到100的数字相加，以使他们安静一会儿，但两分钟后，小高斯就拿出了答案5050，并解释道：“我注意到我可以将第一个数字1和最后一个数字100相加，得到101；第二个数字2和倒数第二个数字99也是101；显然这样重复50次，所以是50乘以101，5050”。虽然不够严谨，但对于一个六岁的孩子来说是非常正确和合适的;-)。
同样地（加上非常基础的代数），您可以看到通用情况是，正如许多人已经说过的那样，(N * (N+1)) / 2（乘积始终为偶数，因为其中一个数字必须是奇数，另一个数字必须是偶数；因此除以二将始终产生所需的整数，没有余数）。
2
这是一个严谨的证明，只是没有使用我们通常与“严谨”相关联的符号混乱（在我看来，这使得它成为了更好的证明）。 - Stephen Canon
@Stephen，这不是严谨的，因为有“明显”的手波——很容易就可以做到这一点（没有符号，那只会使它更长； -)。 - Alex Martelli
除了在证明的第一学期课程中，我认为它足够“清晰”以至于可以被视为严谨的。 - Stephen Canon
对于大多数程序员来说，具体数学可能太难了。而求和问题我认为非常简单，通常小学生就能理解。 - xiao 啸
@Turtle，我不同意Graham-Knuth-Patashnik的书对大多数程序员来说太难了--我是个乐观主义者，我相信人们和他们的大脑潜力，他们只需要被激发和挑战才能使用和发展它！当然，我确实提到求和问题是由一个一年级学生首先解决的（虽然不是一个普通的孩子;-)。 - Alex Martelli
1
那里有一个小错别字：应该是 n * (n+1) / 2。 - Pin
4

下面是如何证明等差数列的通项公式

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
3

Larry的公式非常准确，也是计算所有整数总和最快的方法，直到n。

但为了完整起见，Python内置了一些函数来执行您所做的操作，适用于具有任意元素的列表。例如：

  • sum()

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

  • or more general, reduce()

    >>> import operator
>>> reduce(operator.add, range(11))
55
有趣的是，sum() 函数实际上给了我一个无效的结果。我尝试了你输入的语法，得到的是 45 而不是 55。 - Gabriel
1
这是因为 range(10) 的范围是从0到9。 - Dingle
@Gabriel：糟糕，我的错。当然应该是range(11)...我写这个时已经太晚了... - Felix Kling
3

我还没有评论的权限，所以我只想说，在使用range()时要小心，因为它是从0开始计数的。你需要使用range(n+1)才能达到预期效果。

对于重复造成的不便，深表歉意...

sum(range(10)) != 55

sum(range(11)) == 55

我在测试我的Python时也注意到了这一点。+1，希望你很快能得到评论。 - Gabriel
3

OP在评论中要求提供有关高斯小时候的故事的链接。

他可能想看看Brian Hayes撰写的这篇引人入胜的文章。它不仅相当有说服力地表明了高斯的故事可能是现代捏造的，而且概述了如何很难不看到从1加到100的数字总和中涉及的模式。事实上，忽略这些模式的唯一方法是通过编写程序来解决问题。

该文章还讨论了计算等差数列总和的不同方法，这是OP问题的核心。这里还有一个无广告版本here。

1
考虑到N+1， N-1+2， N-2+3等所有加起来的总和相同，并且大约有N/2个这样的实例（如果N为偶数，则恰好为N/2）。
1

你那里的东西被称为等差数列，正如建议的那样，你可以直接计算它，而不会因递归引起额外开销。

我会说这是一份家庭作业，无论你怎么说。

哈哈，不是的，如果我不知道这个东西（我常常帮助我的妻子完成她的数学作业），她会笑话我的。这个问题其实是为我的同事准备的。谢谢你提供了这个名字。 - Gabriel
嗯，看起来太简单了，但我也会遇到这种情况 :) - Gabriel Ščerbák
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接