Сколько общих подарков за двенадцать дней рождества, если мы расширяемся 12 на какое-либо число?
Я получил этот вопрос сегодня в интервью: запишите функцию для вычисления общего количества подарков, полученных на любой день за 12 дней рождественской песни. Я записал простую функцию с помощью для () цикл в коде c#'ish, который работал. Затем интервьюер попросил, чтобы я расширил его до любого количества дней. Разговор затем обратился к тому, как оптимизировать цикл. По-видимому, существует прохладный математический прием, который сделает это в рамках того, что Ваше целое число. Кто-либо знает то, что это и чем это называют? Любой язык в порядке, и ссылка на алгоритм была бы fabuloso.
Ответы, которые используют рекурсию, не то, что я ищу.
Править: Ответ в течение дня 2 является 4 общими количествами подарков, не 3, так как у меня будет 2 Дерева (1 с сегодняшнего дня, 1 со вчерашнего дня) и 2 куропатки. В день 12 я получу в общей сложности 364. Я хочу формулу, которая позволяет мне ввести 12 и добраться 364.
2 ответа
- В первый день вы получите 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 in 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
Без циклов. Без рекурсии.
В n -й день мы получаем 1 + 2 + 3 + ... + n подарков.
Или ... (1 + n) + (2 + n-1) + ...
Другими словами, (n + 1) * n / 2 .