Сколько всего подарков за двенадцать дней Рождества, если мы продлим 12 на любое число?

Question

Я получил этот вопрос сегодня в интервью: напишите функцию, чтобы вычислить общее количество подарков, полученных за любой день в 12-дневной рождественской песне. Я написал простую функцию, используя цикл for () в c # 'ish коде, который работал. Затем интервьюер попросил меня продлить его на любое количество дней. Затем разговор перешел к тому, как оптимизировать цикл. Очевидно, есть крутой математический трюк, который сделает это в пределах вашего целого числа. Кто-нибудь знает, что это такое и как оно называется? Любой язык в порядке, и ссылка на алгоритм будет 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)/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

Без петель. Нет рекурсии.

Answer 2

Подарок $ P $ -го типа (где $ 1 $ - это куропатки, $ 2 $ - это горлицы и т. Д.) В количестве $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}$.

Answer 3

В n день мы получаем 1 + 2 + 3 + ... + n подарки.

Или ... (1 + n) + (2 + n-1) + ...

Другими словами, (n + 1) * n/2.