Au moment où on détecte que la séquence lue est (pour reprendre ton exemple)
12-2-4-2-6-4-10-2-4-2-6-12-2-4-2-6-4-10-2-4-2-6.
on ne peut rien conclure, car peut être, en continuant la lecture on aura
12-2-4-2-6-4-10-2-4-2-6-12-2-4-2-6-4-10-2-4-2-6-5.
et la période de la séquence n'est pas complète.
On ne peut donc espérer trouver cette période qu'en considérant l'intégralité de la séquence.
La dernière période de la séquence peut-elle être tronquée, comme par exemple ici :
12-2-4-2-6-4-10-2-4-2-6-12-2-4-2-6-4-10-2-4-2-6-12-2-4-2-6 et en conclure que la période est
12-2-4-2-6-4-10-2-4-2-6 ?
Prenons le premier élément v[0], en position 0 dans le tableau. On peut rechercher la position de l'élément suivant ayant la même valeur v[0] soit v[p]. Dans ce cas, pour que p soit la longueur de la période, il faut que v[k] soit égal à tous les v[np+k] (np+k<N) (N nombre d'éléments de la séquence) pour tous les k=0..p-1.
Si cela est vérifié, alors p est la longueur de la période.
Sinon, il faut rechercher une nouvelle valeur de p, supérieure à la précédente, pour laquelle v[0] == v[p]. Si on en trouve une, alors on recommence le même processus, sinon la période p est la longueur N de la séquence entière.
Exemple : Soit cette séquence de 27 nombres (au dessus figurent les indices)
0 5 10 15 20 25
12- 2- 3- 4- 5-12- 2- 3- 6- 7-12- 2-12- 2- 3- 4- 5-12- 2- 3- 6- 7-12- 2-12- 2- 3
p= 5 v[5] == V[0] == 12 ; v[2*5] == 12 ; v[3*5] == 4 echec
p=10 v[10] == v[0] ; v[2*10] == 6 echec
p=12 v[12] == v[0] ; v[2*12] == 12
v[12+1] == v[1] == 2 ; v[2*12+1] == 2
v[12+2] == v[2] == 3 ; v[2*12+2] == 3
v[12+3] == v[3] == 4 ;
...
v[12+11] == v[11] succès
Période p=12 : 12-2-3-4-5-12-2-3-6-7-12-2.
Partager