ünite 5 · Klasik Algoritmalar
·
ders 5.3
Fibonacci ve tekrarlı ilişkiler
Her terim önceki ikisinin toplamı: 0 1 1 2 3 5 8 13…
7 dk
18 / 22
tamamlandı
Bazı dizilerin her elemanı öncekilerden üretilir. Fibonacci: F(n) = F(n−1) + F(n−2), başlangıç 0 ve 1. Algoritmada iki kutu tutup her adımda kaydırırız: a ← b, b ← a + b — ama sırayla! Önce toplamı geçici kutuya al.
Kaydırma kalıbı
yeni ← a + b
a ← b
b ← yeni
Bu üçlü, "önceki iki değeri hatırla" gerektiren her problemde çıkar: hareketli ortalama, oyun skorları, faiz hesabı.
Büyüme
Fibonacci hızla büyür: 47. terim int kutusuna sığmaz (2 milyarı aşar). Taşma da bir algoritma hatasıdır; büyük sayılar için long gerekir.
akış şeması
elips: başla/bitir · dikdörtgen: işlem · paralelkenar: girdi/çıktı · baklava: karar
flowchart TD
A[a = 0, b = 1, i = 0] --> B{i #lt; n ?}
B -- Evet --> C[/a yaz/]
C --> D[yeni = a + b]
D --> E[a = b]
E --> F[b = yeni]
F --> G[i = i + 1]
G --> B
B -- Hayır --> H([Bitir])
sözde kod
adımlar
1a ← 02b ← 13i ← 04İKEN i < n5 YAZ a6 yeni ← a + b7 a ← b8 b ← yeni9 i ← i + 110DÖNGÜ SONU
aynısı C# ile
C#
1int a = 0, b = 1;2for (int i = 0; i < 10; i++)3{4 Console.Write(a + " ");5 int yeni = a + b;6 a = b;7 b = yeni;8}
adım adım izleme
Kutuların her adımdaki değeri. Kağıtta izleme tablosu tutarken tam bunu yaparsın.
| # | satır | a | b | ekran | not |
|---|---|---|---|---|---|
| 1 | başlangıç | 0 | 1 | ||
| 2 | YAZ 0; yeni=1; a=1; b=1 | 1 | 1 | 0 | 1. tur |
| 3 | YAZ 1; yeni=2; a=1; b=2 | 1 | 2 | 0 1 | 2. tur |
| 4 | YAZ 1; yeni=3; a=2; b=3 | 2 | 3 | 0 1 1 | 3. tur |
| 5 | YAZ 2; yeni=5; a=3; b=5 | 3 | 5 | 0 1 1 2 | 4. tur |
senin sıran
Kaydırma kalıbıyla "önceki üç terimin toplamı" dizisini (Tribonacci: 0 0 1 1 2 4 7…) üret. Kaç kutu gerekiyor?
kendini sına
a ← b satırını yeni ← a + b'den önce yazsak ne olur?
a'nın eski değeri kaybolur; yeni = b + b olur ve dizi 0 1 2 4 8… diye ikiye katlanır. Sıra önemli.
tamamlandı
İşaret bu tarayıcıda kalır. XP için
giriş yap — her ders +15 XP.