Merhabalar herkese. Kafama takılan bir python problemi var. Şekilde görüldüğü üzere Python ile fibonacci dizisi tanımlanabiliyor.
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-2) + fibonacci(n-1)
Bu recursive fonksiyonu kullanarak altın oranında yaklaşık değeri tam olmasada şekildeki gibi bulunur.
fibonacci(23) / fibonacci(22)
Ancak ben görselleştirmede kullanıp görselde göze daha çekici gelmesi için altın oranın tam değerini bu fonksiyona bağlı kullanabilmek istiyorum. Yani bu dizinin son indisini sondan bi önceki indisine bölersem elimde altın oran tam olarak olacak. Sizce ne yapmalıyım ?
dizinin son indisi derken tam olarak neyi kastettin anlamadım. altın oran yakınsayan bir sayı. dizi sonsuza doğru gider.
ayrıca bana sorarsan fibonacci dizisi için rekürsif yerine basit bir liste kullanırsan program daha hızlanacaktır. her sayı için kendine gönderme yapmana gerek yok.
Sanırım fibonacci fonksiyonuna verilen değerin büyümesi ile altın orana yakınsamadaki doğru orantıyı iki boyutlu bir tabloda göstermek istiyorsunuz. Bunu hangi kütüphane ile görselleştireceksiniz?
Bu arada fibonacci fonksiyonunun özyinelemeli halden döngü kullanan bir hale getirilmesini, hatta her fibonacci sayısını en baştan hesaplamamak için her seferinde bir sonraki sayıyı döndüren bir generatore dönüştürülmesini şiddetle tavsiye ediyorum.
Aslında amacım turtle kütüphanesi ile birkaç geometrik şekil çizerek estetiği görmek. Ama güzel şeyler çıkarsa ileri görsel programlama modüllerinede geçmeyi düşünürüm.
import math
from decimal import Decimal
def fibonacci():
x = 1
y = 0
while True:
yield x
x, y = x + y, x
i = fibonacci()
altın_oran = (Decimal(5).sqrt() + 1) / 2
print("Altın oran:", altın_oran)
j, k = next(i), next(i)
while True:
print(Decimal(k) / Decimal(j))
j = k
k = next(i)
Fibonacci serileriyle alakalı alternatif bir yöntemden bahsedeyim.
Bu serisinin fonksiyonel ifadesini Jacques Philippe Marie Binet 1843’te şöyle vermiş:
Fibonacci serisinde n. sırada yer alan sayı, altın oranın köklerinin n. kuvvetlerinin farkının, köklerin kendilerinin farkına olan bölümüne eşittir.
Yani, altın oran (Φ) diye bir irrasyonel sayı ve bu irrasyonel sayının x1 ve x2 diye iki tane kökü var. Bu kökleri bulup, istenen fonksiyonu f(n) = (x1 ** n - x2 ** n) / (x1 - x2) cinsinden yazıp, n. sırada yer alan fibonacci sayısını bulabiliriz.
Altın oran ne diyordu bize?
a > b > 0 durumunda; a'nın b'ye olan oranı, a+b'nin a'ya olan oranına eşitse, a ve b arasında altın oran vardır. Yani;
Φ = a/b = (a+b)/a
Yukardaki formüldeki (a+b)/a ifadesini açacak olsak, şöyle yazamaz mıydık?
(a/a) + (b/a)
a/a da 1'e eşit olur bu durumda. Formül de şöyle değişmez mi?
Φ = a/b = 1+b/a
Madem a/b, altın orana eşit o halde b/a için 1/Φ yazıp formülü yeniden düzenleyelim:
Φ = 1 + 1/Φ
İşte bir denklem elde ettik. Bu denklemi biraz daha değiştiriyorum.
Φ ** 2 - Φ - 1 = 0
Evet, lise zamanlarından aşina olduğumuz bir denkleme benzettik.
Hatırlarsanız, bir denklemin köklerini bulmak için deltayı (Δ) bulmamız lazımdı. Δ'nın formülünü hatırlayalım:
ax^2 + bx + c = 0 denklemi için Δ:
delta = b ** 2 - 4 * a * c
Bir denklemin kökleri nasıl bulunuyordu hatırlayalım:
Binet’in f(n) = (x1n - x2n) / (x1 - x2) formülünü aşağıdaki adımları takip ederek elde edebiliriz:
Yukardaki mesajda, Φ sayısıyla alakalı bir denklem türetmiştik:
Φ2 - Φ - 1 = 0
Bu denklemin köklerini bulmuştuk sonra:
x1 = ((1 + √5) / 2)
x2 = ((1 - √5) / 2)
Şimdi genel bir f fonksiyonu nasıl tanımlarız buna bakalım.
Böyle durumlarda, eldeki bilgileri tekrar gözden geçirmekte yarar var. Bu mevcut bilgileri kullanıp, bazı yer değiştirme esasları uygulayarak genel geçer bir formül elde edebiliyor muyuz araştırmak lazım.
Örneğin, Φ2 - Φ - 1 = 0 denkleminden başlayalım.
Burada, Φ gördüğümüz yere x yazarsak herhangi bir değişiklik yapmamış oluruz.
O halde x2 - x - 1 = 0 ise
x1 = x
x2 = x + 1 olmaz mı?
x3'ü de şu şekilde yazabiliriz değil mi?
x3 = x * x2
Şimdi buradaki x2 ifadesini ortadan kaldırıp, x’e göre bir yazım yapabiliriz. Çünkü x2'ın ne olduğunu biliyoruz. O halde:
x3 = x * (x + 1) olur. Bu da aşağıdaki ifadeye eşittir.
x3 = x2 + x
x2 yerine x + 1 yazmaya devam ediyorum.
x3 = x + 1 + x = 2 * x + 1
Evet x4'e geçelim.
x4 = x * x3
x3 yerine 2 * x + 1 yazıyorum.
x4 = x * (2 * x + 1)
x4 = 2 * x2 + x
x2 yerine x + 1 yazıyorum.
x4 = 2 * (x + 1) + x
x4 = 3 * x + 2
Bu yaklaşımı devam ettirirsek, x5'in değerinin 5 * x + 3, x6'nın 8 *x + 5, x7'nin 13 * x + 8 olduğunu buluruz.
Sonuçları alt alta bir daha yazalım.
x1 = x
x2 = x + 1
x3 = 2 * x + 1
x4 = 3 * x + 2
x5 = 5 * x + 3
x6 = 8 * x + 5
x7 = 13 * x + 8
Burada sizin de gözünüze bir örüntü çarpmış olmalı. x’in üssü 1, 2, 3, 4, 5 … diye artıkça, x’in katsayıları da fibonacci serisinin 1. 2. 3. 4. … indislerinde yer alan değerleri alıyorlar. Öte yandan denklemdeki sabit ise Fibonacci serisini 1 adım geriden takip ederek değerler alıyor.
Biz fibonacci serisini bulan fonksiyona f ismini vermiştik. Yani:
x7 = 13 * x + 8 ise
f(7)'nin bize 13 değerini, f(6)'nın da 8 değerini vermesi gerekir.
O halde, xn ifadesini yazacak olursak şöyle yazamaz mıyız?
xn = f(n) * x + f(n - 1)
Fibonacci denkleminin köklerini bu denklemlere yazalım.
f(n - 1)'ler birbirini götürür, elimizde şöyle bir formül kalır:
x1n - x2n = f(n) * x1 - f(n) * x2
Yukardaki ifadeyi f(n) parantezine alabiliriz.
x1n - x2n = f(n) * (x1 - x2)
f(n)'i yalnız bırakalım.
f(n) = (x1n - x2n) / (x1 - x2)
Gördüğünüz gibi son adımda fibonacci dizisinin fonksiyonel formülünü elde ettik. Fibonacci sayısının köklerini de bulmuştuk zaten. Bu kökleri, son elde ettiğimiz formüldeki yerlerine koyarak Fibonacci serisinin n. basamağındaki değeri O(1) hızında bulabiliriz.
