Fibonacci Number

Q: Какова временная сложность рекурсивной функции Фибоначчи?

Наивная рекурсия выполняет 2 × F(n+1) - 1 вызовов — это число растёт примерно как 1.618^n и обычно записывается как O(2^n) . При n = 45 это около 3.7 × 10^9 вызовов. Если сохранять каждый результат один раз — в таблице или в двух переменных, — количество вызовов сокращается до O(n) .

Q: Как решить задачу о числах Фибоначчи с помощью динамического программирования?

Начните с рекуррентного соотношения F(n) = F(n-1) + F(n-2) и вычисляйте значения в порядке возрастания n , сохраняя каждое из них. Можно заполнить таблицу снизу вверх или оставить рекурсивную функцию и кешировать её результаты — это называется мемоизацией. В любом случае каждое значение вычисляется один раз, поэтому общий объём работы составляет O(n) .

Q: Можно ли вычислить числа Фибоначчи с использованием O(1) памяти?

Да. Каждое число зависит только от двух предыдущих, поэтому достаточно двух переменных. Храни последние два значения и обновляй их на каждом шаге. Это обеспечивает время O(n) и дополнительную память O(1) .

Q: Есть ли способ быстрее, чем O(n)?

Да. Матрица [[1, 1], [1, 0]] , возведённая в степень n , содержит F(n) в верхнем правом углу, а возведение в квадрат с повторением вычисляет эту степень за O(log n) умножений матриц. Также существует замкнутая формула со степенями золотого сечения, но она работает с числами с плавающей точкой и теряет точность при росте n , поэтому предпочтительны целочисленные методы.

НовичокДинамическое программирование Рекурсия

+10

Числа Фибоначчи начинаются с F(0) = 0 и F(1) = 1, а каждое последующее число — это сумма двух предыдущих: F(n) = F(n-1) + F(n-2). Последовательность начинается так: 0, 1, 1, 2, 3, 5, 8, 13. Ваша функция получает n и возвращает F(n).

Функция

fib(n: integer) → integer

ninteger: позиция в последовательности Фибоначчи, начиная отсчёт с 0
Возвращаетinteger: число Фибоначчи F(n)

Ограничения

0 ≤ n ≤ 45
Ответ помещается в 32-битное целое число со знаком: F(45) = 1134903170.

Примеры

Ввод: n = 4
Вывод: 3
Пояснение: Считайте от начала: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, и F(4) = 2 + 1 = 3.

Ввод: n = 10
Вывод: 55
Пояснение: Последовательность с индексом 0 выглядит так: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Число с индексом 10 — это 34 + 21 = 55.

+13 скрытых тестов при отправке

Дополнительный вопрос

Можешь вычислить F(n) за O(log n)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Определение уже является рекурсивной функцией, и его запись в таком виде даёт правильный ответ. Подвох заключается во времени выполнения: два рекурсивных вызова повторно выполняют работу друг друга, и число вызовов растёт экспоненциально с n. Динамическое программирование решает эту проблему, вычисляя каждое число Фибоначчи только один раз, снизу вверх. На последнем шаге сохраняются только два числа, которые нужны для вычисления следующего.

Рекурсия прямо из определения

Верно, но не успевает на самых больших тестах

Идея

Переведём определение слово в слово. fib(0) равно 0, fib(1) равно 1, а для любого большего значения возвращается fib(n-1) + fib(n-2). Каждая цепочка вызовов заканчивается одним из двух базовых случаев, поэтому ответ верен.

Теперь посчитаем вызовы. fib(5) вызывает fib(4) и fib(3), но fib(4) снова вызывает fib(3). В итоге fib(3) выполняется дважды, fib(2) — три раза, а fib(1) — пять раз; всего fib(5) выполняет 15 вызовов. Одни и те же значения вычисляются снова и снова.

Количество вызовов следует числам Фибоначчи: вычисление F(n) выполняет 2 × F(n+1) - 1 вызовов. Для n = 45 это около 3.7 × 10^9 вызовов — слишком много для ограничения по времени. Эту оценку обычно записывают как O(2^n); точный рост составляет около 1.618^n. Рекурсия имеет глубину всего n уровней, поэтому стеку требуется O(n) памяти.

Алгоритм

Если n равно 0 или 1, верни n.
В противном случае вызови функцию для n-1 и для n-2.
Верни сумму двух результатов.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Заполните таблицу снизу вверх

Идея

Рекурсия работает медленно только потому, что забывает. Если записывать каждое число Фибоначчи при первом вычислении, для каждого потребуется всего одно сложение. Создай таблицу f с ячейками для индексов от 0 до n, задай f[0] = 0 и f[1] = 1, а остальные значения заполни слева направо по формуле f[i] = f[i-1] + f[i-2].

Именно порядок слева направо обеспечивает работу алгоритма: когда ты доходишь до f[i], оба нужных числа уже есть в таблице. Для n = 10 таблица заполняется значениями 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, и ответ находится в последней ячейке.

Это динамическое программирование в самой простой форме: рекуррентное соотношение плюс таблица ответов для меньших случаев. Потребуется n-1 сложений, время O(n), а таблица содержит n + 1 чисел и занимает O(n) памяти. Для n = 45 теперь потребуется 44 сложения вместо миллиардов вызовов.

Алгоритм

Если n равно 0 или 1, верните n.
Создайте таблицу из n + 1 чисел, где f[0] = 0 и f[1] = 1.
Для i от 2 до n задайте f[i] = f[i-1] + f[i-2].
Верните f[n].

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Оставьте только два последних числа

Идея

Посмотри, что читает цикл по таблице. Чтобы заполнить f[i], ему нужны f[i-1] и f[i-2], а больше ничего из предыдущих значений, поэтому все более ранние ячейки — лишний груз. Вместо таблицы используй две переменные: prev хранит число, отстающее на два шага, а curr — число, отстающее на один шаг.

Начни с prev = 0 и curr = 1 — это F(0) и F(1). На каждом шаге вычисляй next = prev + curr, затем сдвигай пару вперёд: prev принимает прежнее значение curr, а curr принимает next. Для n = 4 пара изменяется с (0, 1) на (1, 1), (1, 2) и (2, 3), и curr = 3 — это ответ.

Выполняются те же n-1 сложений, время — O(n), а в памяти хранятся три целых числа; затраты памяти — O(1). Порядок обновлений имеет значение: если перезаписать prev до сложения, сумма будет вычислена с неправильным значением.

Алгоритм

Если n равно 0 или 1, верните n.
Задайте prev = 0 и curr = 1.
Повторите n-1 раз: вычислите next = prev + curr, затем задайте prev = curr и curr = next.
Верните curr.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Ловушки и крайние случаи

Числа Фибоначчи — классическая первая задача на динамическое программирование, и большинство ошибок связано с рекурсией или первыми двумя значениями.

Сдавать решение с наивной рекурсией. Оно проходит небольшие тесты, а затем для n = 45 требует миллиарды вызовов. Сохраняйте результаты в таблице или двух переменных.
Неправильно задавать начальные значения. Здесь F(0) = 0 и F(1) = 1, поэтому F(2) = 1 и F(10) = 55. Если начать последовательность с 1, 1, каждый ответ сдвинется на один индекс.
Создавать таблицу, не предусмотрев особые случаи для малых значений n. При n = 0 в таблице размером n + 1 = 1 нет места для f[1], и запись туда выходит за границы. Сразу возвращайте n, если n < 2.
Обновлять пару в неправильном порядке. Сначала prev = curr, а затем curr = prev + curr — это прибавляет новое значение prev и удваивает curr. Сначала вычислите сумму в next или используйте одновременное присваивание, если оно есть в языке.
Выполнять на один шаг больше. Цикл, который также вычисляет F(n+1), при достижении предельного значения доходит до F(46) = 1836311903; оно всё ещё помещается в 32 бита, но лишь по счастливой случайности. F(47) уже не помещается.

Частые вопросы4

Какова временная сложность рекурсивной функции Фибоначчи?

Наивная рекурсия выполняет 2 × F(n+1) - 1 вызовов — это число растёт примерно как 1.618^n и обычно записывается как O(2^n). При n = 45 это около 3.7 × 10^9 вызовов. Если сохранять каждый результат один раз — в таблице или в двух переменных, — количество вызовов сокращается до O(n).

Как решить задачу о числах Фибоначчи с помощью динамического программирования?

Начните с рекуррентного соотношения F(n) = F(n-1) + F(n-2) и вычисляйте значения в порядке возрастания n, сохраняя каждое из них. Можно заполнить таблицу снизу вверх или оставить рекурсивную функцию и кешировать её результаты — это называется мемоизацией. В любом случае каждое значение вычисляется один раз, поэтому общий объём работы составляет O(n).

Можно ли вычислить числа Фибоначчи с использованием O(1) памяти?

Да. Каждое число зависит только от двух предыдущих, поэтому достаточно двух переменных. Храни последние два значения и обновляй их на каждом шаге. Это обеспечивает время O(n) и дополнительную память O(1).

Есть ли способ быстрее, чем O(n)?

Да. Матрица [[1, 1], [1, 0]], возведённая в степень n, содержит F(n) в верхнем правом углу, а возведение в квадрат с повторением вычисляет эту степень за O(log n) умножений матриц. Также существует замкнутая формула со степенями золотого сечения, но она работает с числами с плавающей точкой и теряет точность при росте n, поэтому предпочтительны целочисленные методы.

Python

def fib(n):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

n = 4

Ожидается

Fibonacci Number

Функция

Ограничения

Примеры

Подсказки

Решение

Рекурсия прямо из определения

Заполните таблицу снизу вверх

Оставьте только два последних числа

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи