Fibonacci Sayılarının Anlamı
Fibonacci sayıları, 0'dan başlayan belirli bir pozitif tamsayı dizisidir. Tam sayılar, pozitif tam sayılardır. Dolayısıyla, bir Fibonacci sayısı, 0'dan başlayan belirli bir tam sayılar veya doğal sayılar dizisidir. Bu dizide, ilk iki sayı, bu sırayla 0 ve 1'dir. Kalan sayılar, önceki iki sayının eklenmesiyle oradan geliştirilir. İlk on iki Fibonacci sayısı aşağıdaki gibi elde edilir:
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
Başka bir deyişle, ilk on iki Fibonacci sayısı:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Elbette on üçüncü sayı: 144 = 55 + 89 olacaktır. Fibonacci sayılarının şöyle bir dizide olduğu düşünülebilir:
| 0 | 1 | 1 | iki | 3 | 5 | 8 | 13 | yirmi bir | 3. 4 | 55 | 89 |
Bir dizinin indeksleri vardır. Aşağıdaki tabloda, ikinci satır, bir dizideki Fibonacci sayıları için karşılık gelen sıfır tabanlı dizinleri gösterir:
| 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 |
Sıfır tabanlı dizinlerde, on iki öğe varsa, son dizin 11'dir.
Fibonacci sayıları O(n) zamanında veya 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 indeksten bir Fibonacci sayısı üretilir. Bu nedenle O(1), n ana işlem yerine yalnızca bir ana işlem alır.
Bu makalenin amacı, günümüzde ECMAScript olan JavaScript kullanarak Fibonacci sayılarının her iki şekilde nasıl üretileceğini açıklamaktır.
Kodlama Ortamı
node.js ortamı, okuyucunun tahmin edebileceği gibi kullanılmayacaktır. Bunun yerine tarayıcı, kodun yorumlanması ve sonuçların görüntülenmesi için kullanılacaktır. Komut dosyası (kod), “.html” uzantısıyla kaydedilmesi gereken bir metin düzenleyici dosyasına yazılmalıdır. Komut dosyası minimum koda sahip olmalıdır:
DOCTYPE HTML >< html >
< kafa >
< Başlık > JavaScript ile Fibonacci Sayıları Başlık >
kafa >
< gövde >
< komut dosyası türü = 'metin/ecmascript' >
senaryo >
gövde >
html >
Bu, bir web sayfasının ihtiyaç duyduğu yaklaşık bir minimum koddur. Bu makale için tüm kodlamalar etiketleri arasında gider.
Yazılan (eklenen) kodu çalıştırmak için dosya adının simgesine çift tıklamanız yeterlidir, bilgisayarın tarayıcısı onu açacaktır.
Fibonacci Sayısının Tanımı
Fibonacci sayısının matematiksel bir tanımı vardır. Aşağıdaki gibi tanımlanır:
Fn, sıfır tabanlı bir indekse karşılık gelen bir Fibonacci sayısı olduğunda, n.
İlk iki sayı: 0 ve 1, bu sırayla önceden bildirilir. Bu fonksiyonun son satırı, geri kalan sayıların sıralarındaki ilk iki sayıdan nasıl kaynaklandığını gösterir.
Bu tanım aynı zamanda Fibonacci sayısının formüllerinden biridir.
O(n) Zamanında Fibonacci Sayılarının Üretilmesi
n 1 ise, Fibonacci sayısı olarak yalnızca 0 görüntülenecektir. n 2 ise, 0 ve 1 bu sırayla Fibonacci sayıları olarak gösterilecektir. Eğer n 3 ise, 0, 1 ve 1 bu sırayla Fibonacci sayıları olarak gösterilecektir. n 4 ise, 0, 1, 1 ve 2 bu sırayla Fibonacci sayıları olarak gösterilecektir. n 5 ise, 0, 1, 1, 2 ve 3 bu sırayla Fibonacci sayıları olarak gösterilecektir. Eğer n 6 ise, o zaman 0, 1, 1, 2, 3 ve 5 bu sırayla Fibonacci sayıları olarak gösterilecektir - ve böyle devam eder.
İlk n Fibonacci tamsayısını (sayı) oluşturmak için ECMAscript işlevi:
< komut dosyası türü = 'metin/ecmascript' >işlev fibonacci ( A ) {
n = A. uzunluk ;
eğer ( n > 0 )
A [ 0 ] = 0 ;
eğer ( n > 1 )
A [ 1 ] = 1 ;
için ( i = iki ; i < n ; i ++ ) { //n=0 ve n=2 kabul edildi
currNo = A [ i - 1 ] + A [ i - iki ] ;
A [ i ] = currNo ;
}
}
Kapanış komut dosyası etiketi gösterilmedi. İşlev bir dizi alır. İlk iki Fibonacci sayısı konumlarına atanır. For döngüsü, sıfır tabanlı dizinden 2'den n'nin hemen altına kadar yinelenir. For döngüsündeki en önemli ifade şudur:
currNo = A[i – 1] + A[i – 2];
Bu, geçerli sayıya sahip olmak için dizideki hemen önceki iki sayıyı ekler. fibonacci() işlevi çalışmayı bitirdiğinde, dizinin tüm öğeleri ilk n Fibonacci sayısıdır. fibonacci() işlevini çağırmak ve Fibonacci sayılarını görüntülemek için uygun bir kod:
N = 12 ;varış = yeni Dizi ( N ) ;
fibonacci ( varış ) ;
için ( i = 0 ; i < N ; i ++ )
belge. yazmak ( varış [ i ] + '' ) ;
belge. yazmak ( '
' ) ;
senaryo >
Bu kod, kapanış komut dosyası etiketini gösterir. Kod, yukarıdaki kodun altına yazılmıştır. Web sayfasında görüntülenen çıktı:
0 1 1 2 3 5 8 13 21 34 55 89
beklenildiği gibi.
O(1) Zamanda Bir Fibonacci Sayısı Üretmek
O(1) sabit zamandır. Bir ana işlemi ifade eder. Bir Fibonacci sayısı üretmek için başka bir matematiksel 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, Fibn 1 olur. n 2 ise, Fibn 1 olur. n 3 ise, Fibn 2 olur. n 4 ise, Fibn 3 olur – ve benzeri. 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. Sonuç, karşılık gelen Fibonacci sayısıdır.
Bu formül için ECMAScript (JavaScript) kodu:
< komut dosyası türü = 'metin/ecmascript' >işlev fibHayır ( n ) {
fibN = ( Matematik . güç ( ( 1 + Matematik . sqrt ( 5 ) ) / iki , n ) - Matematik . güç ( ( 1 - Matematik . sqrt ( 5 ) ) / iki , n ) ) / Matematik . sqrt ( 5 ) ;
dönüş fibN ;
}
Kapanış komut dosyası etiketi gösterilmedi. Güç (pow) ve karekök (sqrt) önceden tanımlanmış işlevlerin nasıl kullanıldığına dikkat edin. ECMAScript'te (JavaScript), Math modülünün içe aktarılması gerekmez. fibNo() işlevi, formülü doğrudan uygular. Web sayfasındaki fibNo() işlevi için uygun bir çağrı ve gösterim:
N = on bir ;Sağ = fibHayır ( N ) ;
belge. yazmak ( Sağ ) ;
senaryo >
Kod, kapanış komut dosyası etiketini gösterir. Çıktı:
89.000000000000003
Cevaptan gereksiz ondalık basamakları çıkarmak mümkündür. Ancak, bu başka bir zaman için bir tartışma.
Birden fazla Fibonacci numarası gerekliyse, kodun her sıfır tabanlı karşılık gelen n indeksi için formülü bir kez çağırması gerekir.
Çözüm
Fibonacci sayıları, 0'dan başlayan belirli bir pozitif tamsayı dizisidir. Tam sayılar, pozitif tam sayılardır. Yani, bir Fibonacci sayısı, 0'dan başlayan belirli bir tam sayılar veya doğal sayılar dizisidir. Bu dizide, ilk iki sayı, bu sırayla 0 ve 1'dir. Bu ilk iki sayı sadece bu şekilde tanımlanır. Sayıların geri kalanı, hemen önceki iki sayının eklenmesiyle oradan geliştirilir.
İlk iki Fibonacci sayısını ürettikten sonra, kalan Fibonacci sayılarını üretmek için toplam n sayı elde etmek için, ifadeyle birlikte bir for döngüsü kullanılmalıdır:
currNo = A[i – 1] + A[i – 2];
Bu, mevcut Fibonacci numarasına sahip olmak için hemen son iki Fibonacci sayısını ekler.
Sıfır tabanlı bir indeks verildiğinde, karşılık gelen Fibonacci numarasına sahip olmak için aşağıdaki formülü kullanın:
