Aslında, ilk iki Fibonacci sayısı önceden tanımlanmıştır. İlk Fibonacci sayısı 0 ve ikinci Fibonacci sayısı 1'dir. Sıfır tabanlı indeksleme ile ve Fibonacci sayılarının bir dizide olduğunu varsayarak:
indekste 0 , Fibonacci sayısı 0 , ( önceden tanımlanmış ) ;indekste 1 , Fibonacci sayısı 1 , ( önceden tanımlanmış ) ;
indekste iki , Fibonacci sayısı 1 = 1 + 0 , ( tanım olarak ) ;
indekste 3 , Fibonacci sayısı iki = 1 + 1 , ( tanım olarak ) ;
indekste 4 , Fibonacci sayısı 3 = iki + 1 , ( tanım olarak ) ;
indekste 5 , Fibonacci sayısı 5 = 3 + iki , ( tanım olarak ) ;
indekste 6 , Fibonacci sayısı 8 = 5 + 3 , ( tanım olarak ) ;
indekste 7 , Fibonacci sayısı 13 = 8 + 5 , ( tanım olarak ) ;
indekste 8 , Fibonacci sayısı yirmi bir = 13 + 8 , ( tanım olarak ) ;
indekste 9 , Fibonacci sayısı 3. 4 = yirmi bir + 13 , ( tanım olarak ) ;
ve benzeri.
Programlamada, bu Fibonacci sayıları için sıfır tabanlı indeksler için n değişkeni ve i değil kullanılır. Ve bununla birlikte, ilk on iki Fibonacci sayısı:
| 0 | 1 | 1 | iki | 3 | 5 | 8 | 13 | yirmi bir | 3. 4 | 55 | 89 |
| 0 | 1 | iki | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | on bir |
Tablodaki ikinci satır, her biri programlamada n değişkenine sahip olacak sıfır tabanlı dizinleri verir. İlk satır, karşılık gelen Fibonacci sayılarını verir. Yani, Fibonacci sayıları herhangi bir sayı değildir. Çekirdek tanımı, ilk Fibonacci sayısı için 0 ve ikinci Fibonacci sayısı için 1 ile başlar. Kalan sayılar oradan üretilir.
Fibonacci sayıları O(n) zamanında ve ayrıca O(1) zamanında üretilebilir. O(n) zamanı için, örneğin n 12 ise, ilk on iki Fibonacci sayısı üretilecektir. O(1) zamanı için sadece bir Fibonacci sayısı üretilir. Örneğin, n 6 ise, o zaman Fibonacci sayısı 8 üretilir.
Bu makale, Java'da Fibonacci sayıları üretmenin bu iki yolunu açıklamaktadır.
Fibonacci Sayısı Formülü
Fibonacci sayısının matematiksel bir formülü vardır. Bu formül üç satırda veya bir satırda yazılabilir. Üç satırda şöyle yazılır:
nerede F n sıfır tabanlı n'deki Fibonacci sayısıdır inci dizin. Fibonacci sayısı bu şekilde tanımlanır.
O(n) Zamanında Fibonacci Sayılarının Üretilmesi
Fibonacci sayıları O(3) kez üretilecekse, 0, 1, 1 sayıları üretilecektir; bunlar ilk üç Fibonacci sayısıdır. Son sıfır tabanlı n inci buradaki indeks 2'dir. Fibonacci sayıları O(7) kez üretilecekse, 0, 1, 1, 2, 3, 5, 8 sayıları üretilecektir; bunlar ilk yedi Fibonacci sayısıdır. Son sıfır tabanlı n inci buradaki indeks 6'dır. Fibonacci sayıları O(n) kez üretilecekse, 0, 1, 1, 2, 3, 5, 8 – – - sayıları üretilecektir; bunlar ilk n Fibonacci sayılarıdır. Son sıfır tabanlı n inci buradaki indeks n-1'dir.
İlk n Fibonacci sayılarını üretmek için bir sınıftaki Java yöntemi:
sınıf Fibonacci {geçersiz fibonacci ( int [ ] P ) {
int n = P. uzunluk ;
eğer ( n > 0 )
P [ 0 ] = 0 ;
eğer ( n > 1 )
P [ 1 ] = 1 ;
için ( int i = iki ; i < n ; i ++ ) { //n=0 ve n=2 kabul edildi
int currNo = P [ i - 1 ] + P [ i - iki ] ;
P [ i ] = currNo ;
}
}
}
Fibonacci sınıfı özeldir. bu fibonacci() yöntem P dizisini alır ve void döndürür. Yöntem, dizinin uzunluğunu belirleyerek başlar. Bu n uzunluğu, gerekli Fibonacci sayılarının sayısıdır. Birinci ve ikinci Fibonacci sayıları açıkça belirlenir ve dizideki birinci ve ikinci konumlara yerleştirilir.
Üçüncüden başlayarak kalan Fibonacci sayıları (indeks, n = 2) bir for-döngüsü içinde belirlenir ve dizideki konumlarına yerleştirilir. Bu nedenle, işlevin void döndürmesi gerekir. For döngüsündeki ana ifade, önceki iki sayıyı ekler.
Açıklık sağlamak amacıyla n yerine indeks değişkeni i kullanılmıştır.
Uygun bir Java Ana sınıfı (Java ana yöntemiyle):
halka açık sınıf Ana {halka açık statik geçersiz ana ( Sicim argümanlar [ ] ) {
int m = 12 ;
int [ ] varış = yeni int [ m ] ;
Fibonacci nesnesi = yeni Fibonacci ( ) ;
nesne fibonacci ( varış ) ;
için ( int i = 0 ; i < m ; i ++ )
sistem . dışarı . Yazdır ( varış [ i ] + ' ' ) ;
sistem . dışarı . println ( ) ;
}
}
Sayılar fibonacci() yöntemiyle üretildikten sonra Java ana yöntemi onları okur.
Sabit Zamanda Bir Fibonacci Sayısı Üretmek
Karşılık gelen sıfır tabanlı indeks verildiğinde, bir Fibonacci sayısı üretmek için kullanılabilecek matematiksel bir formül vardır, n. Formül:
n, sıfır tabanlı dizin ve Fib'dir n karşılık gelen Fibonacci sayısıdır. Denklemin sağ tarafında, n kuvvetine yükseltilenin 5'in karekökü olmadığına dikkat edin; n kuvvetine yükseltilmiş parantez içindeki ifadedir. Bu tür ifadelerden iki tane var.
n 0 ise, Fib n 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.
Kodlandığında, bu formül n için yalnızca bir Fibonacci sayısı üretecektir. Birden fazla Fibonacci sayısı gerekliyse, formül kodunun karşılık gelen farklı indekslerin her biri için bir kez çağrılması gerekir.
Java'da sadece bir Fibonacci sayısı üretme yöntemi şudur:
içe aktarmak java.lang.* ;sınıf lif {
çift fibHayır ( int n ) {
çift fibN = ( Matematik . güç ( ( 1 + Matematik . sqrt ( 5 ) ) / iki , n ) - Matematik . güç ( ( 1 - Matematik . sqrt ( 5 ) ) / iki , n ) ) / Matematik . sqrt ( 5 ) ;
dönüş fibN ;
}
}
Java.lang.* paketinin programın başında içe aktarılması gerekiyordu. Bunun nedeni paketin, power (pow) ve karekök (sqrt) yöntemlerine sahip Math sınıfına sahip olmasıdır. Buradaki özel Java yöntemi, matematik formülünü doğrudan uygular.
Bu işlevin zaman karmaşıklığı, bir ana işlemin sabit uysallığı olan O(1)'dir. Yukarıdaki yöntem için Java ana yöntemiyle uygun bir Java Ana sınıfı:
halka açık sınıf Ana {halka açık statik geçersiz ana ( Sicim argümanlar [ ] ) {
int N = on bir ;
fiber nesne = yeni lif ( ) ;
çift Sağ = nesne fibHayır ( N ) ;
sistem . dışarı . println ( Sağ ) ;
}
}
n = 11 indeksi gönderilir ve Fibonacci sayısı 89 döndürülür. Çıktı:
89.000000000000003Gereksiz ondalık basamaklar kaldırılabilir, ancak bu başka bir zaman için bir tartışma.
Çözüm
Fibonacci sayıları belirli bir tam sayı dizisidir. Geçerli numarayı elde etmek için, hemen önceki iki karşılık gelen sayıyı ekleyin. İlk iki Fibonacci sayısı, ardından 0, tüm dizi için önceden bildirilir. Fibonacci sayılarının geri kalanı oradan üretilir.
Dizin 2'den dizin n-1'e karşılık gelen Fibonacci sayıları üretmek için, temel ifadeyle birlikte bir for döngüsü kullanın:
int currNo = P [ i - 1 ] + P [ ben - iki ] ;burada currNo geçerli Fibonacci sayısıdır ve P, n sayılarını depolayacak dizidir.
Herhangi bir sıfır tabanlı indeks n'den sadece bir Fibonacci sayısı üretmek için matematiksel formülü kullanın:
