Problème
La suite de Fibonacci commence par F(1) = 1, F(2) = 1, et chaque terme suivant est la somme des deux précédents : 1, 1, 2, 3, 5, 8, 13, 21, ... Trouvez à quel rang la suite atteint pour la première fois n chiffres décimaux. Les termes dépassent vite la capacité des entiers sur 64 bits : si votre langage n'a pas de grands entiers, additionnez-les sous forme de tableaux de chiffres.
Implémentez fibonacci_with_n_digits(n).
Entrée
n : le nombre de chiffres.
Sortie
Renvoyez l'indice i du premier terme F(i) qui a au moins n chiffres. Pour n = 1, la réponse est 1.
Contraintes
1 ≤ n ≤ 1000
Exemples
Entrée :
n = 2
Sortie attendue :
expected = 7
Entrée :
long long n = 2;
Sortie attendue :
long long expected = 7;
Entrée :
long n = 2;
Sortie attendue :
long expected = 7;
Explication
F(6) = 8 a un chiffre et F(7) = 13 en a deux, donc la réponse est 7.
Entrée :
n = 4
Sortie attendue :
expected = 17
Entrée :
long long n = 4;
Sortie attendue :
long long expected = 17;
Entrée :
long n = 4;
Sortie attendue :
long expected = 17;
Explication
F(16) = 987 et F(17) = 1597, donc la réponse est 17.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Ne gardez que les deux derniers termes.
Indice 2
Stockez chaque terme sous forme de chiffres et additionnez-les avec les retenues.
Indice 3
Comptez l'indice au fur et à mesure, en partant de F(1) = 1.
Complexité attendue
temps O(n²), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.