Python Dilinde Fibonacci Sayıları

Fibonacci sayıları, ilk değerin 0, ikinci değerin önceden 1 olarak bildirildiği belirli bir dizidir. Geri kalan sayılar, önceki iki sayının eklenmesiyle bu ikisinden üretilir. Tüm Fibonacci sayıları 0'dan başlayan pozitif tam sayılardır. İlk on iki Fibonacci sayısı ve nasıl elde edildikleri aşağıdaki gibidir:

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

Toplam ifadeler olmadan, bu Fibonacci sayıları aşağıdaki gibi bir tabloya konulabilir:

İlk satırda Fibonacci sayıları bulunur. İkinci satır, Fibonacci sayılarının bir dizide olduğu varsayılarak sıfır tabanlı dizinlere sahiptir.

Fibonacci sayıları O(n) zamanında ve O(1) zamanında üretilebilir. Bu zaman karmaşıklığı ifadelerinde n, n ana işlem anlamına gelir ve 1, 1 ana işlem anlamına gelir. O(n) ile, 0'dan başlayarak n Fibonacci sayısı üretilir. O(1) ile, karşılık gelen bir indeksten bir Fibonacci sayısı üretilir. Bu nedenle n ana işlem yerine sadece bir ana işlem alır.

Bu makalenin amacı, Python kullanarak Fibonacci sayılarının her iki şekilde nasıl üretileceğini açıklamaktır.

Fibonacci Sayısı Formülü

Bir Fibonacci sayısının resmi tanımı şöyledir:

nerede F _n sıfır tabanlı n

O(n) Zamanında Fibonacci Sayılarının Üretilmesi

n 1 ise, Fibonacci sayısı olarak yalnızca 0 yazdırılır. n 2 ise, 0 ve 1 bu sırayla Fibonacci sayıları olarak yazdırılacaktır. n 3 ise, 0, 1 ve 1 bu sırayla Fibonacci sayıları olarak yazdırılacaktır. n 4 ise, 0, 1, 1 ve 2 bu sırayla Fibonacci sayıları olarak yazdırılacaktır. n 5 ise, 0, 1, 1, 2 ve 3 bu sırayla Fibonacci sayıları olarak yazdırılacaktır. n 6 ise, o zaman 0, 1, 1, 2, 3 ve 5 Fibonacci sayıları olarak bu sırayla yazdırılır - ve bu böyle devam eder.

İlk n Fibonacci sayısını üreten Python işlevi:

Tümü sıfırlarla başlatılmış bir n eleman dizisi oluşturarak başlar. Bu dizi Fibonacci sayılarını tutacaktır. İlk Fibonacci sayısı 0, zaten orada. İkinci Fibonacci sayısı 1, bir sonraki ifadeyle (fonksiyonda) atanır. Sonra indeks 2'den n'nin hemen öncesine kadar başlayan for döngüsü vardır. Şu ifade var:

Bu, hemen önceki iki sayıyı ekler.

Fonksiyonu çağırmak ve ilk on iki Fibonacci sayısını yazdırmak için kod şöyle olabilir:

N = 12
A = fibonacci(N)
(N) aralığındaki i için:
yazdır (A[i], bitiş=' ')
Yazdır()

Çıktı:

Sabit Zamanda Bir Fibonacci Sayısı Üretmek

Sıfır tabanlı bir indeksi karşılık gelen Fibonacci sayısıyla ilişkilendiren matematiksel bir formül vardır. Formül:

Denklemin sağ tarafında, n kuvvetine yükseltilenin 5'in karekökü olmadığına dikkat edin; n kuvvetine yükseltilmiş parantez içindeki ifadedir. Böyle iki ifade var.

n 0 ise Fibn 0 olur. n 1 ise Fib _n 1 olur. n 2 ise, Fib _n 1 olur. n 3 ise, Fib _n 2 olur. n 4 ise, Fib _n 3 olur - ve böyle devam eder. Okuyucu, n yerine farklı değerler koyarak ve değerlendirerek bu formülü matematiksel olarak doğrulayabilir. n, bu formülde sıfır tabanlı bir dizindir.

Bu formül için Python kodu:

matematik ithal etmek

Matematik modülü içe aktarıldı. Karekök fonksiyonuna sahiptir. Operatör, ** güç için kullanılır. fibNo() işlevi, formülü doğrudan uygular. fibNo() işlevi için uygun bir çağrı ve yazdırma:

N = 11
sağ = fibNo(N)
yazdır(ret)

Çıktı:

Cevaptan gereksiz ondalık basamakları çıkarmak mümkündür. Ancak, bu başka bir zaman için bir tartışma.

Farklı n dizinleri için farklı Fibonacci sayıları gerekiyorsa, karşılık gelen farklı Fibonacci sayılarını döndürmek için fibNo() işlevinin her n dizini için bir kez çağrılması gerekir. Aşağıdaki program bunu 7'den 9'a (dahil) sıfır tabanlı dizinler için yapar:

matematik ithal etmek

Çıktı:

Python'da for döngüsünün nasıl kodlandığına dikkat edin. İlk dizin 7'dir. Sonraki dizin 8'dir ve son dizin 9'dur. Aralık bağımsız değişkeninde 10, 9 + 1'dir. 10 konumundaki değer, son sıfır tabanlı dizin artı 1 olmalıdır. argüman, 7, sıfıra dayalı başlangıç ​​indeksidir.

Çözüm

Fibonacci sayıları belirli bir tam sayı dizisidir (pozitif tam sayılar). 0 ile başlar, ardından koşulsuz olarak 1 gelir. Sayıların geri kalanı, hemen önceki iki sayının eklenmesiyle oradan geliştirilir.

İlk n Fibonacci sayısını elde etmek için, ilk ikisi olarak 0 ve 1'i kabul edin, ardından geri kalanı için aşağıdaki gibi bir ifadeyle bir for döngüsü kullanın:

bu hemen önceki iki sayıyı ekler.

Sıfır tabanlı bir indeks n'den yalnızca bir Fibonacci sayısı elde etmek için aşağıdaki formülü kullanın: