- Dolduruluyor
- Okunan
- Cevap
Dinamik programlama ile Fibonacci
Fibonacci sayıları, dinamik programlamanın klasik ilk örneğidir. Düz özyineleme aynı terimleri tekrar tekrar ister, ama her terimi hatırlayan bir tablo sayesinde iş yalnızca n ile birlikte büyür. Bir terim seçin, aşağıdan yukarı ya da yukarıdan aşağı yöntemi belirleyin ve her hücrenin bir kez dolduğunu görmek için adım adım ilerleyin. Tablonun dolmasını izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Hesaplanacak terim olan n'yi ve yöntemi seçin: aşağıdan yukarı yöntem tabloyu soldan doldurur, yukarıdan aşağı yöntem ise özyinelemeyi korur ama önce tabloya bakar; bu durumda tablonun altındaki satır açık çağrıların yığınıdır. Yeni örnek başka bir n seçer. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Hesaplanacak terim olan n'yi Terim n alanına yazın ve Aşağıdan yukarı ya da Yukarıdan aşağı yöntemini seçin.
- Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
- Her hücrenin kendinden önceki iki hücreyi okumasını izleyin. Yukarıdan aşağı yöntemde tablonun altındaki satır açık çağrıların yığınıdır.
Aşağıdan yukarı ve yukarıdan aşağı
Tablolama olarak da bilinen aşağıdan yukarı yöntem F(0) = 0 ve F(1) = 1 ile başlar ve tabloyu soldan sağa doldurur: her yeni hücre, kendinden önceki iki hücrenin toplamıdır. Memoization olarak da bilinen yukarıdan aşağı yöntem özyinelemeli tanımı korur: F(n)'yi bulmak için F(n − 1) ve F(n − 2) istenir. Düz özyinelemeden farkı şudur: her çağrı önce tabloya bakar ve bir terimi yalnızca hücresi hâlâ boşsa hesaplar. İki yöntem de her hücreyi bir kez doldurur ve n − 1 toplama kullanır.
Düz özyineleme neden bu kadar yavaş?
Tablo olmadan F(n), F(n − 1) ve F(n − 2)'yi çağırır, bunların ikisi de F(n − 3)'ü çağırır ve bu böyle sürer: çağrılar, aynı terimlerin tekrar tekrar göründüğü bir ağaç oluşturur. Çağrı sayısı 2·F(n + 1) − 1'dir ve Fibonacci sayılarının kendisi kadar hızlı büyür: F(10) için 177, F(20) için 21.891 ve F(40) için 331 milyondan fazla çağrı. Bunun gibi örtüşen alt problemler, tam olarak dinamik programlamanın çözmek için var olduğu şeydir.
Sık sorulan sorular
Dinamik programlama nedir?
Bir problemi birbiriyle örtüşen daha küçük problemlere bölüp her küçük problemi bir kez çözerek ve cevabını bir tabloda saklayarak çözme yöntemidir. Fibonacci sayıları en basit örnektir: her terim kendinden önceki iki terimden oluşur.
Memoization ile tablolama arasındaki fark nedir?
Memoization özyinelemeli kodu korur ve her cevabı ilk hesaplandığında saklar, böylece sonraki çağrılar onu yalnızca okur. Tablolama, tabloyu bir hücrenin ihtiyaç duyduğu her cevabın önceden hazır olmasını sağlayan bir sırayla doldurur. İkisi de aynı toplamaları yapar; tablolama çağrı yığınına ihtiyaç duymaz, memoization ise yalnızca gerçekten gereken hücreleri hesaplar.
F(n) için kaç toplama gerekir?
Tabloyla n − 1: F(2)'den F(n)'ye kadar her terim için bir tane. Her zaman yalnızca son iki terim okunur, bu yüzden bir program tablonun tamamı yerine yalnızca iki sayı da tutabilir.
Uygulama neden n = 40'ta duruyor?
F(40) = 102.334.155 hâlâ ekrana rahatça sığar ve düz özyineleme bunun için zaten 331.160.281 çağrıya ihtiyaç duyardı. Daha büyük terimler hızla büyür: bir JavaScript sayısının tam olarak tutabildiği en büyük terim F(78)'dir.
Herhangi bir veri bir yere gönderiliyor mu?
Hayır. Her şey tarayıcınızda hesaplanır ve son ayarlarınız bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git