在圣诞节的12天里，如果我们把12加到任何一个数字上，总共有多少礼物？

Question

我今天在一次面试中得到了这个问题:写一个函数来计算12天圣诞歌曲中任何一天收到的礼物总数。我用c#的代码写了一个简单的for()循环函数。然后面试官让我把它扩展到任意天数。然后谈话转向如何优化这个循环。显然，有一个很酷的数学技巧可以在你的整数的范围内做到这一点。有人知道它是什么吗?它叫什么?任何语言都可以，算法的参考应该是fabuloso。

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

编辑:第二天的答案是总共4份礼物，而不是3份，因为我会有2棵树(1棵来自今天，1棵来自昨天)和2只山鸡。到了第12天，我总共收到了364封邮件。我想要让我输入12并得到364的公式。

Answer 1

第一天，你会得到1。第二天，你会得到1+2。

• ，第三天，你会得到1+2+ n.

• ，你会得到1+2+3+ ... +

• ，第一天，你会得到1+2+3+...+n.

，第二天，你会得到1+2+2+

• ，你会得到1+2+3+...+n.

1 + 2 + ... + n的总和是n(n+1)/2。因此，总数T(N)是n在1..N中的n(n+1)/2总和，其中N是天数。

现在，对于1..N中的n，n(n+1)/2 = n^2 / 2 + n / 2和n^2的和是N(N+1)(2N+1)/6，因此您得到：

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

没有循环。没有递归。

Answer 2

第$P$类型的礼物(其中$1$st是山燕子，$2$th是斑鸽，等等)提供了大量的$P = \sum_{X = 1}^{P} 1$。

在$D$当天，您将通过$D$收到$1$类型的礼物，这一天您将收到总计$ 1$ $\sum_{P = 1}^{D} \sum_{X = 1}^{P}的礼物。

因此，如果日期从$1$运行到$N$ (规范上，$N$是12，但我们现在关心的是允许它变化)，您将获得总体$\sum_{D = 1}^{N} \sum_{P = 1}^{D} \sum_{X = 1}^{P} 1$。

这会计算非递减三元组的数量$1 \leq X \leq P \leq D \leq N$.

这与递增的三元组$1 \leq X < P + 1 < D + 2 \leq N + 2$.的数量相同

所以答案是$\binom{N + 2}{3} = \frac{(N + 2)(N + 1)N}{6}$.

Answer 3

在第n天，我们收到了1 + 2 + 3 + ... + n的礼物.

或者... (1 + n) + (2 + n-1) + ...

换句话说，就是(n + 1) * n/2。