如果我们将12个延伸到任何数字,在圣诞节的十二天内会有多少礼物？

Question

我今天在一次采访中得到了这个问题:写一个函数来计算12天圣诞歌曲中任何一天收到的礼物总数.我在c#'ish代码中使用for()循环编写了一个简单的函数.然后面试官让我把它延长到任意天数.然后谈话转向如何优化循环.显然有一个很酷的数学技巧,可以在你的整数范围内做到这一点.任何人都知道它是什么以及它叫什么？任何语言都可以,并且算法的参考将是fabuloso.

使用递归的答案不是我正在寻找的.

编辑:第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)/2for 的总和,n在1..N哪里N是天数.

现在,n(n+1)/2 = n^2 / 2 + n / 2和之和n^2为n在1..NIS 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 $ -th类型的礼物(其中$ 1 $ st是鹧,, $ 2 $ nd是龟鸠等)的数量为$P = \sum_{X = 1}^{P} 1$.

在$ D $当天,您会收到$ 1 $到$ D $类型的$\sum_{P = 1}^{D} \sum_{X = 1}^{P}礼物,当天共有1美元的礼物.

因此,如果日期从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}$.