Yazan : Şadi Evren ŞEKER
Bu yazının amacı, özyineli problemlere bir örnek vermek ve nasıl çözüldüğünü anlatmaktır. Problemimiz oldukça meşhur olan bir çemberin doğrular tarafından bölünmesidir.
Kabaca, bir çemberi 20 adet doğrunun en fazla kaç alana ayırabileceğini soralım.
Örneğin n=0 için alan sayımız 1’dir:
Bir doğru ile çemberi kestiğimizde iki alan çıkar:
ikinci bir doğru eklendiğinde 3 alan çıkmaktadır:
3 doğru için 7 alan bulunur:
4 doğru için 11 alan bulunur:
Şimdi yukarıdaki bulunan değerleri liste halinde yazalım:
0 1
1 2
2 3
3 7
4 11
Buradaki sayılardan çıkan bağlantı, her adımda, bir önceki değere adım değerinin eklenmesidir. Örneğin 4. adım, bir önceki adımdaki değer olan 7+4 = 11 şeklinde bulunmuştur.
Bu ağlantı aşağıdaki şekilde formülize edilebilir:
f(n) = n + f(n-1)
Görüldüğü üzere bu denklem özyineli bir denklemdir (recursive equation).
Şimdi bu özyineli denklemi çözmeye çalışalım. Bu tip denklemlerin çözümü için iki alternatif bulunur. Aslında ikisi de sonuçta aynı şeyi bulmayı amaçlar.
-
Top Down Approach (Yukarıdan Aşağıya Yaklaşım)
-
Bottom Up Approach (Aşağıdan Yukarıya Yaklaşım)
Denklemimizi önce Yukarıdan aşağıya yaklaşımla açalım:
f(n) = n + f(n-1)
f(n-1) = n-1 + f(n-2)
f(n-2) = n-2 + f(n-3)
…
f(1) = 2
f(0) = 1
Yukarıdaki ilk üç denklemi birbiri cinsinden yazalım:
f(n) = n + n-1 + n-2 + f(n-3)
Buna göre denklemin tamamı açıldığında aşağıdaki gibi bir bağlantı görülebilir:
f(n) = n + n-1 + n-2 + n-3 … + f(1)
Bu denklemi matematiksel olarak aşağıdaki şekilde gösterebiliriz:
Bu denklem de oldukça meşhur olan 1’den n’e kadar olan sayıların toplamı şeklinde düşünülebilir:
Aynı problemi bu defa aşağıdan yukarıya yaklaşımla çözelim (bottom up approach):
f(0)= 1
f(1) = 2
f(2) = 3
f(4) = 7
f(5) = 11
…
Buradaki denklemleri birbiri cinsinden yazıyoruz:
f(0) = 1
f(1) = 1 + f(0)
f(2) = 2 + f(1)
f(3) = 3 + f(2)
f(4) = 4 + f(3)
f(5) = 5 + f(4)
…
şeklinde yazdıktan sonra, son terimi çekelim:
f(5) = 5 + 4 + 3 + 2 + 1 + 1
Buradan çıkan netice ise bir önceki yöntemde elde ettiğimiz netice ile aynıdır.
f(n) = n + n-1 + n-2 … 5 + 4 + 3 + 2 + 1 + 1
dolayısıyla aynı denklemi yazabiliriz:
ve sonuç olarak aşağıdaki hesap doğrudur:
Yukarıdaki denklemleri elde ettikten sonra, bize ilk başta sorulan acaba 20 adet doğru olsaydı en fazla kaç alana bölünebilirdi sorusuna cevap bulabiliriz: