Tous les défis
Facile 0 résolus 0 % de réussite

Premier terme de Fibonacci à n chiffres

Trouver le rang du premier nombre de Fibonacci qui a n chiffres.

Ce que vous allez apprendre

  • Additionner deux tableaux de chiffres
  • Générer les termes de Fibonacci sans dépassement de capacité
  • S'arrêter au premier terme qui vérifie une condition

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

Exemple 1
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.

Exemple 2
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.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.