Version imprimable
bonsoir,
Est ce qu'il ya quelqu'un qui a rencontré l'algo de brent ou floyd pour la détection de cycle dans une serie de données:
http://en.wikipedia.org/wiki/Cycle_detection
J'ai cherhé sur le net mais trouvé que des codes implémentent une fonction qui génère les séquences {p,f(p),f(f(p)),...} à partir d'un point p, alors que pour moi, j'ai un fichier qui inclue ces séquences et j'ai besoin juste de detecter le cycle!
serait il possible selon vous?
pouvez vous m'aider dessus?
merci beaucoup!
Tu peux sans problème utiliser le dit algorithme.
Sauf que dans ton cas tu connais déjà les f^k(p), donc il faut remplacer le calcul itératif de f^k(p) et f^2k(p) par des itérateurs qui visiteront tes f^k(p) à des vitesses différentes (le 1er de 1 en 1, 2nd de 2 en 2).
Par contre tu perds un peu l'intérêt de l'algorithme ... en effet tu as déjà précalculé/stocké plus de f^k(p) que nécessaire.
oui tu as raison quant au calcul/stockage plus que nécessaire.. mais le but initial etait de voir si le cycle se rèpète ou s'il ya plusieurs cycles dans le même fichier contenant les sorties.
Après peut-etre avec l'algo tel qu'il est, ceci ne va pas etre possible!
Par : " remplacer le calcul itératif de f^k(p) et f^2k(p) par des itérateurs qui visiteront tes f^k(p) à des vitesses différentes" ,j'ai compris que je peux accèder et retirer les résultats directement depuis le fichier. Ceci doit supposer de créer une structure de donnée (telle une liste)?
Merci de ton interet!