Nombre d'appels pour la n-ième nombre de Fibonacci

Envisager l'extrait de code suivant:

int fib(int N)
{
   if(N<2) return 1;
   return (fib(N-1) + fib(N-2));
}

Étant donné que fib est appelée main avec N comme 10,35,67,... (dire), le nombre total des appels
sont faits pour fib?

Est-il un rapport à ce problème?

PS: C'est une question théorique et ne doit pas être exécuté.

EDIT:

Je suis conscient du fait que d'autres méthodes pour accélérer le calcul de la suite de Fibonacci.

Je veux une solution pour le calcul du nombre de fois fib est invoquée pour fib(40),fib(50) ,.. sans l'aide du compilateur et de l'examen de la condition où vous êtes censé répondre 40 question similaire à celui-ci dans un stipulé de temps ( environ 30 bonbons à la menthe).

Merci,

Qu'essayez-vous de réaliser? En supposant que vous n'êtes pas tout simplement à la recherche de quelqu'un pour répondre à vos devoirs.
Est-ce 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 demander sur le problème spécifique que vous avez rencontré.
(Presque mais pas tout à fait dupe): stackoverflow.com/questions/360748/...
Non ce n'est pas un travail à domicile problème!!!!!
Je dirais que cela dépend de si vous utilisez memoization pour garder le résultat d'précédemment calculés nombres de fibonacci ou pas 🙂

OriginalL'auteur whacko__Cracko | 2009-11-15

  1. 11

    Laisser f(n) être le nombre d'appels effectués à calculer fib(n).

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

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

    • De la Base de cas (n < 2, qui est, 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 des moyens efficaces de calculer n'importe quel terme de Fibonacci. Donc la situation est la même pour f(n).

    Vous montrez trop, monsieur.
    Merci,je sais que cette relation de Récurrence.J'étais curieux de le résoudre par la directe de la formule. Dans le document, il est donné pour trouver la valeur de la Fib(40) qui est en fait 331160281.Je me demande comment le résoudre en 30 secondes (sans compilateur de cours)
    J'espère que ma mise à jour de la réponse vous aide à répondre à cette question.
    Je l'ai déjà dit, je suis conscient de la plus rapide des algorithmes de génération de nième nombres de Fibonacci. Votre induction mesures sont correctes, mais toujours pas possible pour le calcul de f(40) à la main dans un très court laps de temps.
    vous n'êtes pas censé s'appliquer à l'induction, mais au lieu de cela aller avec la formule f(n) = 2 * fib(n) - 1. Depuis, comme vous le dites, vous ont un algorithme rapide pour calculer les nombres de Fibonacci, ce qui résout le problème. Droit?

    OriginalL'auteur Stephan202

  2. 4

    Est-il un lien pour ce problème
    ?

    Il existe une étroite-forme de l'équation pour le n-ième nombre de fibonacci: http://en.wikipedia.org/wiki/Fibonacci_number#Closed_form_expression

    Dans le pseudo-code que vous avez posté, le nombre d'appels satisfait à la relation de récurrence

    x(n) = x(n-1) + x(n-2) +1   # for n>=2
x(1) = 1
x(0) = 1

    C'est presque la même que la Fibonacci relation de récurrence. La preuve par induction peut montrer que le nombre d'appels à la fib faite par fib(n) est égale à 2*fib(n)-1, pour n>=0.

    Bien sûr, le calcul peut être accéléré en utilisant l'expression analytique, ou par l'ajout de code à mémoriser les valeurs précédemment calculées.

    Ne pourrait-il pas être x(n) = x(n-1) + x(n-2) + 1?
    pas de. seq = 1,1,2,3,5,8,13,... il n'y a pas de +1 nécessaire.
    nous parlons du nombre de les appels de fonction, pas la séquence de Fibonacci. E. g. fib(0) et fib(1) 1 appel, mais fib(2) nécessite 3 appels (pas 2!): l'appel lui-même, et les deux appels récursifs.
    Stephan202, merci pour cette remarque. J'ai corrigé ma réponse.
    avez-vous réellement en mesure d'effectuer la preuve par induction? Je pense que la formule est incorrecte (voir ma réponse).

    OriginalL'auteur unutbu

  3. 3

    Comme mentionné ci-dessus, vous avez besoin pour résoudre le périodique suivant l'équation:
    K(n)=K(n-1)+K(n-2)+1

    Nous allons l'écrire pour n-1: K(n-1)=K(n-2)+K(n-3)+1

    Maintenant, il faut soustraire le deuxième en partant 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.

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

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

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

    sera une solution de l'équation.

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

    J'ai bien aimé votre approche.
    -1. K(n) - 2*K(n-1) + K(n-3) = 0 ne se traduisent pas x^3 - 2*x^2 + 1 = 0... 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 en x - 2*y + z = 0 sauf si vous pouvez prouver une relation entre ces variables. Réponse erronée et trompeuse.
    Neil, la réponse n'est pas trompeuse. Vous feriez mieux de lire sur l'utilisation de la caractéristique équations à résoudre linéaire récidives. Voici le lien: [hcmop.wordpress.com/2012/04/20/...

    OriginalL'auteur Dmitry Shkolnik

  4. 2

    phi est une constante

    position = ceil(log((n - 0.5)*sqrt(5))/log(phi));

    n est le nombre de fibonacci...
    position vous donnera le qui nombre de fibonacci est n

    par exemple à 13 , la position sera 7 - 0 1 1 2 3 5 8 13

    à l'aide de cette position juste de calculer le nombre de fibonacci à la position 1 ou de n'importe quelle position que vous voulez par rapport à donné le nombre de fibonacci.

    Previous Fibo Num = floor((pow(phi,position-1)/sqrt(5))+0.5);

    floor((pow(phi, position)/sqrt(5))+0.5) - est la formule standard pour le calcul du n-ième de fibonacci num (Note - Ce n'est pas une approximation)

    J'ai juste inverser cette formule pour calculer la position et l'utilisation de la position - 1 pour calculer la précédente nombre de fibonacci.

    Ref - http://itpian.com/Coding/20951-Given-the-Nth-fib-no-and-find-the--N-1-th-fib-number-without-calculating-from-the-beginning---------.aspx

    OriginalL'auteur Jeet

  5. 1

    C'est un problème classique pour résoudre avec Relations de Récurrence.

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

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

    Une fois que vous maîtrisez la résolution des récurrences, vous n'aurez aucun problème pour parvenir à une solution (qui, incidemment, est exactement le même que fib(n)).

    Expliquer l'-1.

    OriginalL'auteur Yuval Adam

  6. 1

    Question intéressante, je ne peux pas vous donner une formule, mais j'ai écrit un Rubis programme pour le faire, il travaille sur les chiffres que j'ai trouvé sur le papier, et cela devrait fonctionner pour tout.

    #!/usr/bin/ruby
#find out how many times fib() would need to be called

def howmany(n)
    a = [ ]
    a.push n-1
    a.push n-2
    while a.select{|n| n > 2}.length > 0
        a.map! do |n|
            n > 2 ? [n-1,n-2] : n
        end
        a.flatten!
    end
    a.length
end

    .

    >> howmany(10)
=> 55

    C'est lent.. je suis en train de comprendre 35 maintenant, je vais modifier quand il se termine.

    Edit:

    >> howmany(35)
=> 9227465

    OriginalL'auteur Jeffrey Aylesworth