Algorithme fonction de la suite de fibonacci
Je ne cherche pas forcément la réponse, mais je suis à la recherche de ce qui est demandé. Trouve cette question à étudier pour une entrevue, mais pas sûr de ce qu'ils demandent?
Écrire la fonction qui s'exécute par le biais de la suite de Fibonacci et les retours
l'index qui est transmis en tant que paramètre.
Ah....que de plus en plus claire. Thx.
Avez-vous lu ma réponse?
supposons que l'indice de i est donné. a) passage de la fib de la série: 1 1 (il n'a' dire dans quelle mesure ou whatfor, n'est ce pas?) b) le retour de i
Avez-vous lu ma réponse?
supposons que l'indice de i est donné. a) passage de la fib de la série: 1 1 (il n'a' dire dans quelle mesure ou whatfor, n'est ce pas?) b) le retour de i
OriginalL'auteur KingKongFrog | 2013-05-05
Vous devez vous connecter pour publier un commentaire.
tout d'abord,vous pouvez mettre à jour votre base de mathématiques de l'information à propos de Fibonacci avec cette lien de wiki. et regardez cette formule rapide à calculer.et vous pouvez lire l'ensemble de ce sujet dans ce lien.
C'est une fonction récursive pour calculer n-ième nombre de Fibonacci et est de O(2^n) temps:
c'est la meilleure idée pour calculer n-ième nombre de Fibonacci et est de O(n) temps:
et c'est la meilleure façon de calculer les n-ième nombre de Fibonacci et est de O(log(n)) durée:
ce lien:
Que vous êtes déjà se douter, ce sera très similaire. L'utilisation de la n-ième puissance de la
x * x
matriceC'est facile à comprendre si vous multipliez cette matrice avec le vecteur
qui résultats dans
Des exponentielles de matrices peut être fait en O(log(n)) (lorsque x est considérée comme étant constante).
Pour le Fibonacci de récurrence, il existe aussi un fermé de la formule de solution, voir ici http://en.wikipedia.org/wiki/Fibonacci_number, recherchez Binet ou la formule de Moivre.
et regardez:
1-n-ième nombre de fibonacci dans sublinéaire temps
OriginalL'auteur amin k
Ce qu'il me semble, c'est que vous êtes invité à renvoyer le la n-ième de fibonacci pas., où n est l'passées en paramètre. Vous pouvez employer différentes méthodes pour répondre à cette question, alors que tous ceux-ci varie dans le temps de la complexité et de la complexité du code.
Méthode 1 ( Utiliser la récursivité )
Une méthode simple qui est directement recusrive mise en œuvre mathématique recurance relation donnée ci-dessus.
Complexité temporelle: T(n) = T(n-1) + T(n-2) qui est exponentielle.
Nous pouvons observer que cette mise en œuvre fait beaucoup de travail répété (voir la suite de la récursivité de l'arbre). C'est donc une mauvaise mise en oeuvre pour la n-ième nombre de Fibonacci.
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/\
fib(1) fib(0)
Supplémentaire de l'Espace: O(n) si l'on considère la fuinction appel de la taille de la pile, sinon O(1).
Méthode 2 ( Utilisation De La Programmation Dynamique )
Nous pouvons éviter la répétition de travaux est la méthode 1 en stockant les nombres de Fibonacci calculé jusqu'à présent.
Temps de la Complexité: O(n)
Supplémentaire de l'Espace: O(n)
Méthode 3 ( Espace Otimized Méthode 2 )
Nous pouvons optimiser l'espace utilisé dans la méthode 2 en stockant les deux numéros précédents seulement parce que c'est tout que nous avons besoin pour obtenir le prochain Fibannaci numéro dans la série.
Temps de la Complexité: O(n)
Supplémentaire De L'Espace: O(1)
Méthode 4 ( en Utilisant la puissance de la matrx {{1,1},{0,1}} )
Cette autre O(n), qui s'appuie sur le fait que si nous n fois multiplier la matrice M = {{1,1},{0,1}} à lui-même (en d'autres mots calculer la puissance(M, n )), alors nous obtenons la (n+1)ième nombre de Fibonacci que l'élément de ligne et de colonne (0, 0) dans la matrice résultante.
La représentation matricielle donne a fermé expression pour les nombres de Fibonacci:
Temps de la Complexité: O(n)
Supplémentaire De L'Espace: O(1)
La Méthode 5 ( Méthode Optimisée 4 )
La méthode 4 peut être optimisé pour fonctionner en O(Logn) le temps de la complexité. Nous pouvons faire récursive de la multiplication pour obtenir de l'énergie(M, n) dans les précédents méthode (Similaire à l'optimisation de faire dans ce post)
Temps De La Complexité: O(Logn)
Supplémentaire de l'Espace: O(Logn) si nous considérons l'appel de fonction de la taille de la pile, sinon O(1).
Programme De Pilote:
int main()
{
int n = 9;
printf("%d", fib(9));
getchar();
return 0;
}
Références:
http://en.wikipedia.org/wiki/Fibonacci_number
http://www.ics.uci.edu/~eppstein/161/960109.html
OriginalL'auteur Aman Chhabra
C'est très mal formulé la question, mais vous devez supposer qu'ils demandent le nème Fibonnaci nombre où
n
est fourni comme paramètre.En plus de toutes les techniques énumérées par d'autres, pour
n > 1
vous pouvez également utiliser le golden ratio de la méthode, qui est plus rapide que n'importe quelle méthode itérative. Mais comme la question dit: "courir à travers la séquence de Fibonacci" cela peut ne pas être admissible. Vous auriez probablement aussi de leur faire peur à la mort.OriginalL'auteur user207421
OriginalL'auteur Dima
J'interprète la question différemment....étant donné un
number
en entrée, ce qui est leindex
de ce numéro dans la série? par exemple,input=5
, alors l'index est5
(compte tenu de la séquence est0 1 1 2 3 5
où l'indice commence avec0
)Ce que le code est comme suit (qui renvoie l'index) [Avertissement: Adapté à partir du code donné à http://talkbinary.com/programming/c/fibonacci-in-c/ ]
OriginalL'auteur Bill