Добывайте n граммов минерала с помощью робота - JPM C Вопрос для интервью

Question

Добывайте n граммов минерала с помощью робота, который может проводить свой день, добывая 1 г в день или создавая другого робота в день - JPM C Вопрос на интервью

• недавно созданный робот может запустить работают только через один день.
• сколько дней / сколько роботов требуется для добычи n граммов минерала?

пример: вход 1 выход 1 вход 4 выход 3

Answer 1

Оптимальная производительность робота определяется только тем, сколько дней ему осталось работать. Мы можем довольно легко дать оптимальное повторение:

def optimal_output(days):
    if days == 0: return 0
    if days == 1: return 1
    return max(optimal_output(days - 1) + 1,  # Mine.
               optimal_output(days - 1) + optimal_output(days - 2)) # Create robot.

Мы можем взглянуть на первую пару членов:

>>> [optimal_output(n) for n in range(10)]
[0, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Эй, это просто Фибоначчи. Это имеет смысл, потому что после дня 3 у нас это optimal_output(days - 1) + 1 никогда не может быть выше, чем optimal_output(days - 1) + optimal_output(days - 2), и остается только повторение Фибоначчи.

---

Выше предполагается, что робот построенный в день 1 может начать работу только в день 3. Если он может начать работу во второй день, мы получим следующее повторение:

def optimal_output(days):
    if days == 0: return 0
    if days == 1: return 1
    return max(optimal_output(days - 1) + 1,  # Mine.
               optimal_output(days - 1) + optimal_output(days - 1)) # Create robot.

Что упрощается до f(1) =, f(n) = 2f(n-1) или, другими словами, степени двойки.