Discussion :

[SmileSoft]

Salut,

je cherche un algorithme pour déterminer est ce qu'un tableau est périodique "cyclique" ou non?

pour simplifier mon tableau est de type enum qui prend comme valeur: -1 ou 1.
exemple: [1,-1,1, 1,-1,1, 1,-1,1 ....1,-1,1] est un tableau périodique dont le cycle est [1.-1.1].

Merci d'avance

[georges86]

salut,
déja pour avancer on retiendra qu'un tableau cyclique a des cycles pairs si sa longueur est paire et des cycles impaires dans le cas contraire.
donc je pars du premier élement du tableau tab[1] en supposant que l'on a un tableau allant de 1 a N (n elements).
N paire.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
je parcours le tableau jusqu'à N/2 a la recherche de tab[1].
{ [I]for i=1;i=n/2;i++
if tab==tab[1] 
{
 premier element tab[1] trouvé
je teste si i est pair, 
if(i % 2)==0 
{
  je peux tester si tab[1,i] est cyclique ...
j'extrait le tableau tab[i+1,2i+1]
si c n'est pas la meme sequence alors ce tableau n'est pas cyclique
}
else i n'est pas pair il est impair alors i+1 est pair
 {
   CHOIX 1 : tab[i+1]==tab[1]
dans ce cas on peut faire le test de cyclique 
CHOIX 2 : tab[i+1]!=tab[1] alors 
soit ce tableau n'est pas cyclique , soit ce tableau est cyclique depuis
(i+1)/2
}
}

 
  

}

je vous laisse la suite ....

[Zavonen]

déja pour avancer on retiendra qu'un tableau cyclique a des cycles pairs si sa longueur est paire et des cycles impaires dans le cas contraire.

Et pourquoi ne pas généraliser?
Commencer par lister les diviseurs de n où n est la longueur du tableau.
La longueur d'un cycle période doit être un de ces diviseurs.

[georges86]

bien Zavonen, ce que tu as dit c'est cool.c'est toujours un diviseur.je pense que cela peut aider dans la recherche de la solution.On va s'y pencher

[pseudocode]

Je vais peut-être dire une grosse bêtise, mais ne suffit-il pas de verifier que tab[i] == tab[ (i % seqlen) ], et si ce n'est pas le cas d'augmenter la taille de seqlen en conséquence ?

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
double[] tab = {1,-1.1, 1,-1.1, 1,-1.1};
 
int seqlen=1;
for(int i=0;i<tab.length;i++)
	if (tab[i] != tab[i%seqlen]) seqlen=(i+1);
 
if ((seqlen<tab.length) && (tab.length%seqlen)==0)
	System.out.println("periodic sequence of length = "+seqlen);

[Zavonen]

Non pseudocode, tu ne dis pas une bêtise, mais disons que si la longueur len du tableau est 125, ce n'est pas la peine d'essayer avec seqlen =2,3,4,6, ce que feras avec ton algo puisque tu commences à 1 et tu incrémentes d'une unité à chaque tour de boucle.
Donc il faut, à mon sens, commencer par isoler la liste des diviseurs de n (longueur totale du tableau).
Après on peut faire comme toi avec seqlen parcourant cette liste, ou alors rendre tab[0:seqlen] le comparer globalement avec tab[seqlen,2*seqlen], etc...
A priori je ne sais pas si une des deux méthodes est dans l'absolu (en moyenne) meilleure que l'autre. On peut facilement trouver des exemples où ta méthode est meilleure et d'autres où c'est le contraire.
Il y a quand même quelque chose qui me dérange dans ton code.
Une fois que tu as décelé que tab[i] != tab[i%seqlen] tu en conclus qu'il ne peut y avoir de cycle de longueur seqlen, tu passes donc au suivant, mais dans ce cas il faut recommencer ta boucle i avec i=0.
J'aurais donc vu plutôt deux boucles imbriquées.
Une boucle i à l'intérieur d'une boucle seqlen.