- Заполняется
- Читается
- Ответ
Числа Фибоначчи и динамическое программирование
Числа Фибоначчи — классический первый пример динамического программирования. Обычная рекурсия снова и снова запрашивает одни и те же члены, а с таблицей, которая запоминает каждый член, объем работы растет только вместе с n. Выберите член, метод снизу вверх или сверху вниз и пройдите по шагам, чтобы увидеть, как каждая ячейка заполняется ровно один раз. Нажмите Пуск, чтобы посмотреть, как заполняется таблица, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Выберите n — номер члена, который нужно вычислить, — и метод: снизу вверх заполняет таблицу слева направо, сверху вниз сохраняет рекурсию, но сначала заглядывает в таблицу, и тогда ряд под таблицей — это стек незавершенных вызовов. Кнопка Новый пример выбирает другое n. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.
Как это работает
- Введите в поле Член n номер члена, который нужно вычислить, и выберите Снизу вверх или Сверху вниз.
- Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
- Следите, как каждая ячейка читает две ячейки перед ней. В режиме сверху вниз ряд под таблицей — это стек незавершенных вызовов.
Снизу вверх и сверху вниз
Метод снизу вверх, его еще называют табуляцией, начинает с F(0) = 0 и F(1) = 1 и заполняет таблицу слева направо: каждая новая ячейка — сумма двух ячеек перед ней. Метод сверху вниз, его еще называют мемоизацией, сохраняет рекурсивное определение: чтобы найти F(n), запрашиваем F(n − 1) и F(n − 2). Отличие от обычной рекурсии в том, что каждый вызов сначала заглядывает в таблицу и вычисляет член, только если его ячейка еще пуста. Оба метода заполняют каждую ячейку один раз и делают n − 1 сложений.
Почему обычная рекурсия такая медленная
Без таблицы F(n) вызывает F(n − 1) и F(n − 2), оба они вызывают F(n − 3) и так далее: вызовы образуют дерево, в котором одни и те же члены встречаются снова и снова. Число вызовов равно 2·F(n + 1) − 1 и растет так же быстро, как сами числа Фибоначчи: 177 вызовов для F(10), 21 891 для F(20) и больше 331 миллиона для F(40). Именно для таких перекрывающихся подзадач и существует динамическое программирование.
Часто задаваемые вопросы
Что такое динамическое программирование?
Способ решать задачу, разбивая ее на меньшие задачи, которые перекрываются, решая каждую меньшую задачу один раз и сохраняя ее ответ в таблице. Числа Фибоначчи — самый простой пример: каждый член строится из двух предыдущих.
Чем мемоизация отличается от табуляции?
Мемоизация сохраняет рекурсивный код и запоминает каждый ответ, когда он вычислен впервые, так что последующие вызовы просто читают его. Табуляция заполняет таблицу в таком порядке, чтобы каждый ответ, нужный ячейке, уже был готов. Оба способа делают одни и те же сложения; табуляция обходится без стека вызовов, а мемоизация вычисляет только те ячейки, которые действительно нужны.
Сколько сложений нужно для F(n)?
С таблицей — n − 1: по одному для каждого члена от F(2) до F(n). Читаются всегда только два последних члена, поэтому программа может хранить вместо всей таблицы всего два числа.
Почему приложение останавливается на n = 40?
F(40) = 102 334 155 еще легко помещается на экране, а обычной рекурсии для него понадобился бы уже 331 160 281 вызов. Дальше члены растут быстро: F(78) — самый большой член, который число JavaScript хранит точно.
Отправляются ли куда-нибудь данные?
Нет. Все вычисляется в вашем браузере, а ваши последние настройки остаются в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор