algorithm - 如果我们将 12 扩展到任意数字，圣诞节的十二天总共有多少礼物？

Question

今天面试遇到这样一个问题:写一个函数，计算圣诞歌曲12天中任意一天收到的礼物总数。我在 c#ish 代码中使用 for() 循环编写了一个简单的函数，该函数有效。然后面试官让我延长到任意天数。然后话题转向了如何优化循环。显然有一个很酷的数学技巧可以在你的整数范围内做到这一点。有谁知道它是什么以及它叫什么？任何语言都可以，并且对算法的引用会很棒。

使用递归的答案不是我要找的。

编辑:第 2 天的答案是总共 4 件礼物，而不是 3 件，因为我将有 2 棵树(今天 1 棵，昨天 1 棵)和 2 只鹧鸪。在第 12 天，我将总共收到 364。我想要让我输入 12 并得到 364 的公式。

Answer 1

• 第一天，你得到 1。
• 第二天，你得到 1 + 2。
• 第三天，你得到 1 + 2 + 3。
• ...
• 关于 n第 天，你得到 1 + 2 + 3 + ... + n .

总和1 + 2 + ... + n是n(n+1)/2 .所以总数，T(N)是 n(n+1)/2 的总和对于 n在1..N , 其中N是天数。

现在，n(n+1)/2 = n^2 / 2 + n / 2 , 和 n^2 的总和对于 n在1..N是N(N+1)(2N+1)/6 ，所以你得到:

T(N) = N(N+1)(2N+1)/12 + N(N+1)/4
     = N(N^2 + 3N + 2) / 6

没有循环。没有递归。