déterminer si un tableau est périodique ?

Citation:

---

quelqu'un pour m'expliquer le code de Zavonen ?

---

Le mieux c'est que Zavonen s'y colle.
Tout d'abord je suis d'accord avec toutes les remarques pertinentes faites concernant ma proposition. Je commente seulement mon code pour répondre à la demande:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Tab=[1,0,1,1,0,1,1,0,1] #le tableau où l'on cherche une périodicité   n= len(Tab) # n est la longueur du tableau (on s'en serait douté)   D=[k for k in range(1,n+1) if n%k==0] # D est ici une 'comprehension list' contenant l'ensemble des diviseurs de n # on peut l'avoir avec tout langage par une banale itération for k in D: # k parcourt l'ensemble des diviseurs de n if Tab==Tab[0:k]*(n/k): #Tab[0:k] est la sous-liste formée des k premiers éléments de Tab #Tab[0:k]*(n/k) est la concaténation de n/k listes toutes égales à Tab[0:k] # En cas d'égalité on a bien notre période. print Tab[0:k] #on affiche la période break # et on arrête tout

---

Mon programme n'est pas efficace pour toutes les raisons qui ont été données plus haut:
Python, langage de (très) haut niveau, n'est pas réputé pour son efficacité.
La construction préalable du multiple Tab[0:k]*(n/k) n'est pas indispensable.
Si on remarque par exemple que Tab[k]!=Tab[0] pas la peine d'aller plus loin.
De sorte que si on veut chercher des choses efficaces il faut plutôt s'orienter vers des solutions 'à la pseudocode'.
On peut également se dispenser de lister préalablement les diviseurs de n en faisant une vérification 'à la volée'.

Citation:

---

Envoyé par pseudocode

[CODE=python]



# Pour chaque diviseur "k" contenu dans la liste D
for k in D:

# si le tableau est une répétition des "k" premiers éléments
if Tab==Tab[0:k]*(n/k):

---

il ne faut pas avoir un cycle de taille 1 (parce ce que 1 est l'identité donc toujours diviseur de n), ni un cycle de taille n dans ce cas la séquence devient non périodique, elle est très bonne cette idée des diviseurs mais je pense qu'il faut chercher des cycles dans cette intervalle [A,B] avec A=le premier diviseur de n qui est différent de 1 et B=la division entière (n/2) par ce qu'au minimum on aura deux cycles dans une séquence périodique.

Voici une version java de ce que je suggère plus haut:

Code:

---

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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

/*  * To change this template, choose Tools | Templates  * and open the template in the editor.  */ package TestPeriode;   /**  *  * @author gilles  */ public class Main {   static int Tab[] = {1, 0, 1, 1, 0, 1, 1, 0, 1}; static int n = Tab.length;   static boolean Test(int i, int k) { for (int h = k; h < n; h += k) { if (Tab[i] != Tab[i + h]) { return false; } } return true; }   static void FindPeriode() { boolean success = true; for (int k = 1; k <= n; k++) { if (n % k != 0) { continue; } else { success = true; for (int j = 0; j <= k; j++) { if (!Test(j, k)) { success = false; } break; } if (success) { System.out.print(k); break; }   } } }   /**      * @param args the command line arguments      */ public static void main(String[] args) { // TODO code application logic here FindPeriode(); } }

---

Citation:

---

il ne faut pas avoir un cycle de taille 1 (parce ce que 1 est l'identité donc toujours diviseur de n), ni un cycle de taille n dans ce cas la séquence devient non périodique, elle est très bonne cette idée des diviseurs mais je pense qu'il faut chercher des cycles dans cette intervalle [A,B] avec A=le premier diviseur de n qui est différent de 1 et B=la division entière (n/2) par ce qu'au minimum on aura deux cycles dans une séquence périodique.

---

Tout d'abord Il n'y a aucune raison d'éliminer 1.
Tu peux éliminer n si tu veux mais ce n'est pas important.

Citation:

---

Envoyé par Zavonen

Tout d'abord Il n'y a aucune raison d'éliminer 1.

---

si si, par ce que avoir un seul cycle dans une séquence veut dire que la séquence est non périodique.

pour l'exemple de séquence que vous donnez:
n=9;diviseurs={1,3,9}, la taille du cycle ne peut être autre que 3, donc je me limite à chercher des cycles de taille 3 seulement.
par exemple pour n=15, diviseurs={1,3,5,15}, on doit chercher des cycles de taille 3 dans la séquence, si on en trouve pas on passe à la recherche des cycles de taille 5.
et ainsi de suite ..

l'algorithme devient simple:
1- l'ensemble des diviseurs (à part 1 et n) va fournir les différentes tailles de cycles qu'on pourra avoir dans une séquence.
2-chercher la répétition d'un cycle dans toute la séquence selon la taille fournie dans 1.

un seul "cycle" == un "cycle" de la longueur du tableau
un cycle minimum de longueur 1 == tous les éléments du tableau sont identiques…

Citation:

---

Envoyé par JeitEmgie

un seul "cycle" == un "cycle" de la longueur du tableau
un cycle minimum de longueur 1 == tous les éléments du tableau sont identiques…

---

je dois respecter 2 contraintes:
1- la période doit comporter au moins un changement d'état (pas de possibilité d'avoir des valeurs identiques).
2- la séquence doit comporter au moins 2 cycles (un cycle de taille n n'aura pas de sens).

Citation:

---

1- la période doit comporter au moins un changement d'état (pas de possibilité d'avoir des valeurs identiques).
2- la séquence doit comporter au moins 2 cycles (un cycle de taille n n'aura pas de sens).

---

Bon, il suffisait de le dire.
Cela dit qu'est-ce que ça change ?
Tu boucles de 2 à n-1 au lieu de 1 à n, et c'est tout.

Citation:

---

Envoyé par Zavonen

Bon, il suffisait de le dire.
Cela dit qu'est-ce que ça change ?
Tu boucles de 2 à n-1 au lieu de 1 à n, et c'est tout.

---

on y est presque mais pas tout à fait…
dans l'état actuel de l'algorithme, le code Java
répondra sous-séquence de longueur 2 pour [1,1, 1,1]…

mais 2 aussi pour
[ 1,-1,1,2, 1,-1,1,2 ]
ce qui est plus embêtant…

alors que le code Python est correct…

l'erreur est :

Code:

---

1 2 3 4 5 6

if (!Test(j, k)) { success = false; } break;

---

qui doit être

Code:

---

1 2 3 4 5 6

if (!Test(j, k)) { success = false; break; }

---

reste à éliminer les réponses pour des tableaux qui contiennent toujours le même élément…

le gros point positif de la version Python/Java est la non dégénérescence sur les cas "presque" :
faites un tableau de centaines de triples (1,-1,2) et mettez un vilain canard (par exemple un 0) soit au début, au milieu ou à la fin…
cela ne gênera pas la performance de l'algorithme…

Merci JeitEmgie pour ta mise au point définitive, et la correction de l'erreur ('break' mal plaçé).
Je crois qu'il faut également, dans le code Java, remplacer j<=k par j<k. Cela n'influence pas le résultat quand la période est un 'vrai' diviseur de n mais cela diminue sensiblement la performance.