Version imprimable
Bonjour à tous,
Je voudrai ecrire un algorithme qui me dit si une suite de termes est cylique
sans utiliser des tableaux pour stocker les termes de la suite.
par exemple: la suite 2, 9, 20, 12, 3, 5, 8, 20, 12, 3, 5, 8.... est cyclique
est-ce possible?
Salut,
Et tu les stockes dans quoi tes termes pour appliquer l'algorithme??? :?Citation:
Envoyé par nina2007
Une pile, tu considères ça comme un tableau ou pas?
Cela dit, parler de tableau dans un algo, c'est un peu introduire des notions de langage informatique... ça ne se fait pas! :lol:
Je présume que les algos de détection de cycle (genre lièvre et tortue...) ne te conviennent pas donc...
merci pour votre réponse...
mais j'ai pas besoin de stocker les termes de la suite, je peux juste les afficher seulement
j'ai une idée: dites-moi si c'est faisable
utiliser deux boucles imbriquées
calculer le terme U_i et recalculer les termes de U_1 à U_(i-1)
si U_i = à l'un des termes déjà calculés alors la suite est cylique
je pense que ça marche, dites-le moi si je me trompe ou y a t-il une meilleur idée?
merci
Bonjour,Citation:
Envoyé par nina2007
oui ton algo fonctionnera, mais il n'est pas optimal. Dans ton cas tu peux adapter l'algo du lièvre et de la tortue (ou moins poétiquement l'algorithme de Floyd de détection de cycle). La page wiki décrit tout ça pas trop mal : Algorithme du lièvre et de la tortue. S'il y a un cycle il le trouve, sinon il boucle ... j'espère que soit tu es sure d'avoir un cycle ou il faudra lui donner une longueur max de cycle.
Cela ne marche que pour une suite de valeurs provenant d'une fonction itérée. En d'autre terme, ca ne marche que si la valeur suivante dans le suite ne dépend que de la valeur actuelle: A[i+1] = f( A[i] ).Citation:
Envoyé par kwariz
Pour ce cas là, ce n'est pas applicable:
:arrow: 1,2,1,3,1,4,1,5,1,6, 1,5,1,6, 1,5,1,6 1,5,1,6, ...
Le problème est particulièrement difficile, car il faut d'une part déterminer quelle est la période de l'éventuel cycle, mais aussi la position du premier cycle. Ces deux valeurs peuvent être arbitrairement grandes.
Une astuce pourrait être de « partir de la fin » de la séquence, si celle-ci en a une (on fait de l'informatique après tout). Dans ce cas favorable, il n'y aurait plus que la période à déterminer. Et cela est bien plus simple.
Peut-on avoir quelques informations supplémentaires sur la source des données ?
Cdlt,
merci pours vos commentaires:ccool:
Je vous donne plus de précisions
la suite d'entiers est construite mathématiquement :
U_n+1 est est égale à la somme des carrés des chiffres de U_n
exemple: si U_i=56 alors U_i+1=61
Alors ma solution marche toujours?
exemple: $U_0=12$, $U_1=5$, $U_2=25$, $U_3=29$, $U_4=85$, $U_5=89$, $U_6=145$,
$U_7=42$,
$U_8=20$, $U_9=4$, $U_{10}=16$, $U_{11}=37$, $U_{12}=58$, $U_{13}=89$,
$U_{14}=145$, $U_{15}=42$,... est une suite cyclique.
On est typiquement dans une fonction itérée: U_i+1 dépend seulement de U_i.Citation:
Envoyé par nina2007
L'algo de Floyd, ou ton algo de recherche exhaustive fonctionnent.
A noter que cette suite est celle des "happy/sad numbers". Elle est soit convergente (vers 1), soit cyclique (longueur 4), suivant la valeur du 1er élément.
merci :ccool: