Discussion :

[blackbird1]

Salut,
Je souhaite parcourir une seule fois cette liste :

2 5 2 5 8 11 14 17 15 8 14 13 12 11 10

pour avoir ce résultat :

2,5, est une suite arithmétique de raison = 3

2,5,8,11,14,17, est une suite arithmétique de raison = 3

15,8, est une suite arithmétique de raison = -7

14,13,12,11,10, est une suite arithmétique de raison = -1

L'algorithme que j'ai trouvé est O(N²).
S'il vous plaît, aidez moi à trouver un algorithme dont la complexité est O(N).
Merci

[dinobogan]

Le pseudo-code ressemble à quelque chose comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
raison = t2 - t1
afficher t1 et t2
pour i = 3 jusqu'à la fin de t
  si ti - t(i-1) != raison alors
    afficher la raison
    raison = ti - t(i-1)
    afficher t(i-1) et ti
  sinon afficher ti
fin pour
afficher la raison

[anapurna]

salut

je ne suis pas certain que l'algo fournis fonctionne
a priori il a oublié de réinitialiser a chaque nouvelle serie
exemple entre 5,2,5 les raison successif sont -3 et 3

reprenons le pseudo code
avec des petites modif

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
 
raison = t2 - t1
afficher t1 et t2
i:= 2 
tans que  i <= fin de t faire
   si ti - t(i-1) != raison alors
     afficher la raison
     Inc(i)
      raison := ti - t(i-1);
     afficher t(i-1) et ti
  sinon 
   afficher ti
  inc(i)
fin tans que 
afficher la raison