Wypełnione komórki
Dodawania
Wywołania bez tablicy

  • Wypełniana
  • Odczytywana
  • Odpowiedź

Więcej o liczbach Fibonacciego i programowaniu dynamicznym

Liczby Fibonacciego i programowanie dynamiczne

Liczby Fibonacciego to klasyczny pierwszy przykład programowania dynamicznego. Zwykła rekurencja wciąż prosi o te same wyrazy, ale dzięki tablicy, która zapamiętuje każdy wyraz, ilość pracy rośnie tylko razem z n. Wybierz wyraz, wybierz metodę wstępującą lub zstępującą i przejdź krok po kroku, aby zobaczyć, jak każda komórka jest wypełniana tylko raz. Naciśnij Odtwórz, aby zobaczyć, jak wypełnia się tablica, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Wybierz n, czyli wyraz do obliczenia, oraz metodę: Wstępująca wypełnia tablicę od lewej, Zstępująca zachowuje rekurencję, ale najpierw zagląda do tablicy, a rząd pod tablicą jest wtedy stosem otwartych wywołań. Nowy przykład wybiera inne n. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.

Jak to działa

  1. Wpisz n, czyli wyraz do obliczenia, i wybierz Wstępująca lub Zstępująca.
  2. Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce.
  3. Obserwuj, jak każda komórka odczytuje dwie komórki przed nią. W metodzie Zstępująca rząd pod tablicą to stos otwartych wywołań.

Metoda wstępująca i zstępująca

Metoda wstępująca (bottom-up), nazywana też tablicowaniem, zaczyna od F(0) = 0 i F(1) = 1 i wypełnia tablicę od lewej do prawej: każda nowa komórka jest sumą dwóch komórek przed nią. Metoda zstępująca (top-down), nazywana też memoizacją, zachowuje definicję rekurencyjną: aby znaleźć F(n), prosi o F(n − 1) i F(n − 2). Różnica w porównaniu ze zwykłą rekurencją polega na tym, że każde wywołanie najpierw zagląda do tablicy i oblicza wyraz tylko wtedy, gdy jego komórka jest jeszcze pusta. Obie metody wypełniają każdą komórkę raz i wykonują n − 1 dodawań.

Dlaczego zwykła rekurencja jest tak wolna

Bez tablicy F(n) wywołuje F(n − 1) i F(n − 2), oba te wywołania wywołują F(n − 3) i tak dalej: wywołania tworzą drzewo, w którym te same wyrazy pojawiają się wciąż od nowa. Liczba wywołań wynosi 2·F(n + 1) − 1 i rośnie tak szybko jak same liczby Fibonacciego: 177 wywołań dla F(10), 21 891 dla F(20) i ponad 331 milionów dla F(40). Właśnie do takich nakładających się podproblemów służy programowanie dynamiczne.

Często zadawane pytania

Czym jest programowanie dynamiczne?

To sposób rozwiązywania problemu przez podzielenie go na mniejsze, nakładające się problemy, rozwiązanie każdego z nich tylko raz i zapisanie odpowiedzi w tablicy. Liczby Fibonacciego to najprostszy przykład: każdy wyraz powstaje z dwóch poprzednich.

Czym różni się memoizacja od tablicowania?

Memoizacja zachowuje kod rekurencyjny i zapisuje każdą odpowiedź, gdy zostanie obliczona po raz pierwszy, więc późniejsze wywołania tylko ją odczytują. Tablicowanie wypełnia tablicę w takiej kolejności, aby każda odpowiedź potrzebna komórce już tam była. Obie wykonują te same dodawania; tablicowanie obywa się bez stosu wywołań, a memoizacja oblicza tylko te komórki, które są naprawdę potrzebne.

Ile dodawań potrzeba do obliczenia F(n)?

Z tablicą n − 1: po jednym dla każdego wyrazu od F(2) do F(n). Odczytywane są zawsze tylko dwa ostatnie wyrazy, więc program może też przechowywać jedynie dwie liczby zamiast całej tablicy.

Dlaczego aplikacja kończy na n = 40?

F(40) = 102 334 155 wciąż łatwo mieści się na ekranie, a zwykła rekurencja potrzebowałaby do tego już 331 160 281 wywołań. Większe wyrazy szybko rosną: F(78) to największy, jaki liczba w JavaScripcie przechowuje dokładnie.

Czy coś jest gdzieś wysyłane?

Nie. Wszystko jest obliczane w Twojej przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora