Discussion :

[fred61]

Bonjour,

J'ai un programme qui entre une suite de chiffre dans un tableau, ce tableau comporte plusieurs milliers de chiffres.

Je sais que les chiffres forment une suite, suite qui change en fonction des données que j'entre dans mon programme, mais je ne peux pas savoir ou se termine la suite.

Je voudrais faire une fonction qui me permette d'analyser mon tableau pour trouver à quel moment les chiffres se répètent pour connaitre la taille de la suite.

Est-ce que vous avez une idée de la façon de procéder ?

Merci.

[Bktero]

Bonjour,

Dans tous les cas, la suite se termine quand le dernier chiffre se répète plusieurs fois ? Sais-tu si tu peux avoir une répétition du même nombre avant la fin de la suite ?

Exemples :

12 01 07 08 09 56 89 89 89 89 89 89

12 01 07 07 07 56 89 89 89 89 89 89

[fred61]

Non, les suites sont du genre :

12-2-4-2-6-4-10-2-4-2-6-12-2-4-2-6-4-10-2-4-2-6...

Mais souvent avec des parties qui se répètent plus longues.

[Bktero]

Et y a t-il un pattern pour détecter la fin ?......

Ou est-ce que 12-2-4-2-6-4-10-2-4-2-6 est la suite à détecter ?

[gangsoleil]

Je sais que les chiffres forment une suite, suite qui change en fonction des données que j'entre dans mon programme, mais je ne peux pas savoir ou se termine la suite.

Je voudrais faire une fonction qui me permette d'analyser mon tableau pour trouver à quel moment les chiffres se répètent pour connaitre la taille de la suite.

Comment peux-tu connaitre la taille, "a la main" ?

[diogene]

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.

[Bktero]

Un jour je serai(s) fort comme mon parrain

[fred61]

Désolé pour le retard de réponse, j'étais absent hier. Merci pour vos réponses, je vais faire une adaptation de la réponse de Diogène, j'avais une idée assez similaire.

Merci encore.