Dev Faq
9
votes

Nombre d'appels pour Nth Fibonacci Number

Considérez l'extrait de code suivant: xxx

étant donné que fib est appelé de la principale avec N comme étant 10,35,67, ... (disons), Combien d'appels total sont faits à fib ?

y a-t-il une relation pour ce problème?

PS: Ceci est une question théorique et non censée être exécutée.

Edit:

Je suis au courant d'autres méthodes pour le calcul plus rapide de la série Fibonacci.

Je veux une solution pour calculer le nombre de fois que FIB est invoqué pour FIB ( 40), FIB (50), .. Sans l'aide du compilateur et lors de la condition d'examen où vous êtes censé répondre à 40 question similaire à celle-ci dans un temps stipulé (environ 30 menthes).

Merci ,

7 commentaires

Qu'est-ce que vous essayez d'accomplir? En supposant que vous ne cherchez pas seulement quelqu'un pour répondre à vos devoirs.

Est-ce que c'est une question d'un devoir? Vous ne devriez pas demander à d'autres personnes de faire vos devoirs pour vous; Vous devriez au moins montrer ce que vous avez essayé jusqu'à présent et poser des questions sur le problème spécifique que vous rencontrez.

Related (presque mais pas-pas-dpeu): Stackoverflow.com/Questtions/360748/...

Non, ce n'est pas un problème de travail à la maison !!

Je dirais que cela dépend si vous utilisez la mémoire de mémoisation pour conserver le résultat des numéros de Fibonacci précédemment calculés ou non :)

@ MATTHIEU M: Qu'est-ce que cela signifie ici? Le problème donné n'autorise aucune modification de la fonction FIND_FIB.

Vous êtes plutôt bon pour le faire son comme devoirs, vous savez. ;) (BTW, il n'y a pas de FIND_FIB fonction).

6 Réponses :

14
votes

let f (n) être le nombre d'appels apportés pour calculer fib (n) .

  • si n <2 puis f (n) = 1 .
  • Sinon, f (n) = 1 + f (n - 1) + f (n-2) .

    Alors, f est au moins o (fib (n)) . En fait, f (n) est 2 * fib (n) - 1 . Nous montrons cela par induction:

    • cas de base ( n <2 , c'est-à-dire n = 0 ou n = 1 ):
      • f (n) = 1 = 2 * 1 - 1 = 2 * fib (n) - 1 . .
      • étape d'induction ( n> = 2 ):
        • f (n + 1) = f (n) + f (n - 1) + 1
        • f (n + 1) = 2 * FIB (N) - 1 + 2 * FIB (N - 1) - 1 + 1
        • f (n + 1) = 2 * fib (n + 1) - 1

          Il existe façons efficaces pour calculer n'importe quel terme Fibonacci. Ainsi, il en va de même pour f (n) .

5 commentaires

Merci, je sais que cette relation de récurrence.Je était curieuse pour la résoudre par une formule directe. Dans le document, il est donné de trouver la valeur de FIB (40) qui est en fait 331160281.Je merveille comment il ya-t-il une résolution dans environ 30 secondes (sans compilateur de cours)

@nthgeek: J'espère que ma mise à jour de la réponse vous aide à répondre à cette question.

@ Stephan202: Merci, comme je l'ai déjà dit, je suis conscient des algorithmes plus rapides pour générer des numéros de Nth Fibonacci. Vos étapes d'induction sont correctes mais ne sont toujours pas possibles pour l'informatique F (40) manuellement en très peu de temps.

@nthgeek: Vous n'êtes pas censé appliquer l'induction, mais aller à la place avec la formule F (N) = 2 * FIB (N) - 1 . Depuis, comme vous l'énoncez, vous do ont un algorithme rapide pour calculer les numéros de Fibonacci, cela résout le problème. Droit?

Notez que cela utilise la définition de la séquence Fibonacci où f₀ = 1 (tel que défini dans la question). Si vous attendez f₀ = 0 , vous obtenez f (n) = 2 • fib (n + 1) - 1 .

4
votes

Y a-t-il une relation pour ce problème ?

Il existe une équation de forme proche du NTH Fibonacci Numéro: http: // fr. wikipedia.org/wiki/fibonacci_number# closed_form_expression

Dans le pseudocode que vous avez affiché, le nombre d'appels satisfait la relation récurrence xxx ceci est presque identique à la relation de récurrence de Fibonacci. La preuve par induction peut montrer que le nombre d'appels vers FIB fabriqués par FIB (N) est égal à 2 * FIB (N) -1, pour N> = 0.

Bien sûr, le calcul peut être accéléré en utilisant l'expression de formulaire fermée ou en ajoutant du code pour mémoriser des valeurs précédemment calculées.

5 commentaires

Cela ne devrait-il pas être x (n) = x (n-1) + x (n-2) + 1 ?

@David: Nous parlons du nombre d'appels de fonction , pas de la séquence de Fibonacci. Par exemple. fib (0) et fib (1) nécessite 1 appel, mais fib (2) nécessite 3 appels (pas 2!): l'appel lui-même et deux appels récursifs.

Stephan202, merci d'avoir souligné cela. J'ai corrigé ma réponse.

@ ~ Unutbu: Avez-vous effectué la preuve par induction? Je pense que la formule est incorrecte (voir ma réponse).

Merci encore Stephan202. C'était négligé de moi. Je voterais à nouveau votre réponse, d'autres que je pouvais.

1
votes

Ceci est un problème classique pour résoudre avec relations récurrences forte> .

Plus précisément, le problème de Fibonacci a les paramètres suivants: P> 

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2)

0 commentaires
3
votes

Comme mentionné ci-dessus, vous devez résoudre l'équation récurrente suivante: K (n) = k (n-1) + k (n-2) +1

Écrivons-le pour N-1: K (N-1) = K (N-2) + K (N-3) +1

Maintenant, soustrayez le deuxième de la première: K (n) -k (n-1) = k (n-1) - k (n-3),

ou

k (n) - 2 * k (n-1) + k (n-3) = 0.

L'équation caractéristique respective sera: x ^ 3 - 2 * x ^ 2 + 1 = 0.

Il a les racines suivantes: 1, (1 + sqrt (5)) / 2, (1-sqrt (5)) / 2

Ainsi pour tout réel A, B, C la fonction suivante K (n) = a * (1) ^ n + b * ((1 + sqrt (5)) / 2) ^ n + c * ((1-sqrt (5)) / 2) ^ n

sera une solution pour votre équation.

Pour trouver A, B, C Vous devez définir plusieurs valeurs initiales K (0), K (1), K (2) et résoudre le système d'équations.

2 commentaires

-1. k (n) - 2 * k (n-1) + k (n-3) = 0 ne traduit pas par x ^ 3 - 2 * x ^ 2 + 1 = 0 < / Code> ... k (n) n'est pas x ^ 3 , k (n-1) n'est pas x ^ 2 et k (n-3) n'est certainement pas 1. Au mieux, vous pouvez traduire k (n) - 2 * k (n-1) + K (n-3) = 0 dans x - 2 * y + z = 0 sauf si vous ne pouvez prouver une relation entre ces variables. Réponse trompeuse.

Neil, la réponse n'est pas trompeuse. Vous feriez mieux de lire sur l'utilisation d'équations caractéristiques pour résoudre les récidives linéaires. Voici le lien: [ HCMOP.WordPress.com/2012/04/20/...

1
votes

Question intéressante, je ne peux pas vous donner une formule, mais j'ai écrit un programme de rubis pour le faire, cela fonctionne sur des chiffres que j'ai compris sur papier, et cela devrait fonctionner pour tout. 

>> howmany(35)
=> 9227465

0 commentaires
2
votes

phi est une constante xxx

n est le numéro de fibonacci ... la position vous donnera que le numéro de Fibonacci est N

par exemple donné 13, la position sera de 7 à 0 1 1 1 2 3 5 8 13

Utilisation de cette position Calculer simplement le numéro de Fibonacci À la position-1 ou à n'importe quelle position que vous souhaitez relatif de numéro de fibonacci. xxx

plancher ((PP (PHI, position) / SQRT (5)) + 0.5 ) - est la formule standard pour calculer nth fibonacci num (note - ceci n'est pas une approximation)

Je viens d'inverser cette formule pour calculer la position et utiliser la position - 1 pour calculer la position. Précédent Numéro de Fibonacci.

REF - http://itpian.com/coding/20951-given-the- NTH-FIB-no-and-Trouvez-le - N-1-TH-FIB-Number-Number-Sans-Calculer-Du début ----------. ASPX

0 commentaires

Articles qui pourrait vous intéresser :

Que puis-je utiliser pour la conversion d'entrée au lieu de scanf?
Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde?
Comment vérifier si un pointeur void (void *) est l'un des deux types de données?
L'écran LCD affiche des caractères aléatoires (MPLAB)