Vérifiez si la chaîne inclut une partie de la séquence de Fibonacci

Question

Quel chemin dois-je suivre pour créer un algorithme permettant de déterminer si la séquence de Fibonacci existe dans une chaîne donnée ?

La chaîne ne contient que des chiffres sans espaces et il peut y avoir plusieurs séquences, je dois les trouver toutes.

Answer 1

Si, comme le dit votre commentaire, le premier nombre doit avoir moins de 6 chiffres, vous pouvez simplement rechercher toutes les positions où l'un des 25 nombres de Fibonacci (il n'y en a que 25 avec moins de 6 chiffres) apparaît, puis essayer d'étendre cette séquence de 1 nombre dans les deux directions.

Après votre mise à jour :

Vous pouvez même accélérer les choses lorsque vous recherchez uniquement des séquences d'au moins 3 nombres.

Préconstruisez les 25 chaînes de 3-nombres qui commencent par l'un des 25 premiers nombres de Fibonacci, cela devrait donner beaucoup moins de correspondances que la recherche des simples nombres de Fibonacci que j'ai suggérée ci-dessus.

Ensuite, recherchez-les (comme décrit ci-dessus) et essayez d'étendre les séquences de 3-nombres trouvées.

Answer 2

Voici comment je m'approcherais de cela.

L'algorithme principal pourrait rechercher des triplets puis essayer de les étendre en une séquence aussi longue que possible.

Cela nous laisse avec le sous-problème de trouver des triplets. Donc, si vous parcourez une chaîne pour rechercher des nombres de Fibonacci, une chose dont vous pouvez profiter est que le nombre suivant doit avoir le même nombre de chiffres ou un chiffre de plus.

par exemple, si vous avez la chaîne "987159725844" et que vous considérez "[987]159725844" alors la prochaine chose que vous devez regarder est "987[159]725844" et "987[1597]25844". Ensuite, la prochaine partie que vous trouveriez est "[2584]4" ou "[25844]".

Une fois que vous avez les 3 nombres, vous pouvez vérifier s'ils forment une progression arithmétique avec C - B == B - A. S'ils le font, vous pouvez alors vérifier s'ils font partie de la séquence de Fibonacci en vérifiant si le ratio est d'environ 1,6, puis en exécutant l'itération de Fibonacci à rebours jusqu'aux conditions initiales 1,1.

L'algorithme global fonctionnerait donc en parcourant la recherche de tous les triplets en commençant par une largeur de 1, puis une largeur de 2, une largeur de 3 jusqu'à 6.

Answer 3

Je dirais que vous devriez d'abord trouver tous les éléments Fibonacci intéressants (qui, ayant 6 chiffres ou moins, ne dépassent pas 30) et les stocker dans un tableau.

Ensuite, parcourez chaque position dans votre chaîne d'entrée, et essayez d'y trouver le plus long nombre Fibonacci possible (c'est-à-dire, vous devez parcourir le tableau à l'envers).

Si un nombre Fib est trouvé, alors vous devez bifurquer vers un algorithme secondaire, consistant simplement à parcourir le tableau de la position actuelle jusqu'à la fin, en essayant de faire correspondre chaque élément dans la sous-chaîne suivante. Lorsque la correspondance se termine, vous devez revenir à l'algorithme principal pour continuer à rechercher dans la chaîne d'entrée à partir de la position actuelle.

Aucun de ces deux algorithmes n'est récursif, ni trop coûteux.

mise à jour

D'accord. Si aucun tableau n'est autorisé, vous pourriez quand même utiliser cette approche en remplaçant dans la première boucle la manière d'obtenir le meilleur nombre Fibo: Au lieu de l'indexation, appliquez votre formule.