Sayı k'den küçük Fibonacci sayılarının sayısı. Sub O (n)

Söyleşi sorusu: Belirli bir sayı k'den daha az kaç Fibonacci numarası var? K'den daha az fibonacci sayısını elde etmek için k cinsinden bir fonksiyon bulabilir misiniz?Sayı k'den küçük Fibonacci sayılarının sayısı. Sub O (n)

Örnek: n = 6

Yanıt: 6 olarak (0, 1, 1, 2, 3, 5) yeterince kolay

, bir döngü yazma Fibonacci yinelemeli tanımı kullanın. Ancak, bu çok kolay geliyor ... kapalı form tanımını kullanarak bunu yapmak için bir yol var mı? (https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression)

kaynak

2016-04-13 Pinhead

Neden birinin bunu bilmesi gerekiyor? Sadece bir bulmaca sorusu mu yoksa ev ödevi mi? "Sub O (n)", bir O (log (n)) veya bir O (1) aradığınızı mı yoksa umursamadığınızı mı gösterir? –

Yanıtın üst veya alt sınırını kabul edersiniz, çünkü bu çok kolay olabilir .. –

Bu bir röportaj sorusudur. Bunu bir düzenleme olarak eklememe izin verin.Bu yüzden bunu yapmak çok kolay olduğunu düşünüyorum O (n) – Pinhead

İşte O (1) olan bir yakın Python çözümü. (Eğer bağlı Vikipedi makalesinden) Binet formülü kullanır:

>>> from math import sqrt,log 
>>> def numFibs(n): return int(log(sqrt(5)*n)/log((1+sqrt(5))/2)) 

>>> numFibs(10) 
6

1,1,2,3,5,8

nokta ile izler olduğunu Binet formülü ikinci dönem ihmal edilebilir ve ihmal sonucunu tersine çevirmek için yeterince kolaydır. Yukarıdaki formül, 'dan küçük veyan'a eşit olan Fibonacci sayılarının sayısını sayar. Her yeni Fibonacci numarası ile 1 atlar. Yani, örneğin, numFibs(12) = 6 ve numFibs(13) = 7. 13, 7. Fibonacci sayısıdır, bu nedenle numaralı Fibobacci sayılarının 'dan daha küçük olan sayısından daha küçük olmasını istiyorsanız bir gecikme yapmanız gerekir. Bir şey gibi:

def smallerFibs(n): 
    if n <= 1: 
     return 0 
    else: 
     return min(numFibs(n-1),numFibs(n))

Şimdi smallerFibs(13) hala 6 ama sonra smallerFibs(14) = 7. Bu hala tabii O(1) olmasıdır.

kaynak

2016-04-13 15:34:28

Bu harika bir açıklama! Teşekkürler! – Pinhead

Bu sayının büyümesini en azından görmenin oldukça kolay olduğunu düşünüyorum. Binet/De-Moivre formula,

f ile _N = (φ ^N-ψ ^N) yana/5

| ψ | 1 < φ <, daha sonra

f _N ∼ φ ^N/5. Bundan

o Fibonacci numaralarının sayısı daha küçük xgünlüğüne _φ (5x) gibi büyür izler.

kaynak

2016-04-13 15:24:51

İhtiyacınız var bir kare kök –

Sayı k'den küçük Fibonacci sayılarının sayısı. Sub O (n)

cevap

İlgili konular