Discussion :

[emna1987]

bonjour a tous ,
j'ai un exercice d'une épreuve de concour :
soit un tableau T remplit aléatoirement par n nombres quelconques(positif,négatifs et nuls)
1.Ecrire un algorithme en O(n) qui détermine la tranche du tableau T ayant la somme minimale de ses éléments.Une tranche de T est une suite de composants consécutifs de ce tableau.l'algorithme recoit en paramètre le tableau T[1..n] et retourne l'indice de début,l'indice de fin et la somme de la tranche minimale de T.
j'ai trouvé des diffucultés à résoudre cet exercice et surtout la notion de compléxite.
si quelqu'un peut m'aider a commencer et de me renseigner peut être d'un cour avec lequel je peux commecer je serais trop reconnaissante

[Flodelarab]

Bonjour

Explication par l'exemple en cliquant sur ce lien:
http://imss-www.upmf-grenoble.fr/pre...e/PGSomme.html

[wiwaxia]

Bonjour,

Le problème est aussi exposé ici.

[anapurna]

salut

ne pas prendre les exemple tels quel ... il faut réfléchir un peu
les exemple te donne les montant maxi alors que toi tu veut le mini

pour moi je serait tente de dire que c'est la valeur minimal de ton tableau
la case etant une suite d'un espace

plus sérieusement dans un premier temps il va te faloir determiner
les différente suite

Code :

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

1
2
3
4
5
6
7
8
9
 
  if TAB[i] =  TAB[i+1] Then
    ADDSUITE(NumSuite,TAB[i+1])
  ELSE 
  BEGIN
     NumSuite := CREENEWSUITE(TAB[i+1]) 
  END
  //.....
 reste plus qu'a parrcourir le tableau suite

imaginons que nous ayons un tableau de 10 valeurs
[1][3][2][4][5][6][7][8][10][9]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
[1]
[1][3]
[1][3][2]
[1][3][2][4]
[1][3][2][9]
[1][3][2][15]
[1][3][2][22]
[1][3][2][30]
[1][3][2][30][10]
[1][3][2][30][10][9]

dans mon exemple la suite minimal = 1

[tatayo]

Anapurna: ça ne fonctionne pas, car les nombres peuvent être négatifs.
Avec la suite
[1][3][2][-2][-3][6][-4][8][10][9]

Le suite qui donne le montant mini n'est pas [-4], mais [-2][-3].

Tatayo.

[wiwaxia]

Qu'il s'agisse de la recherche du minimum au lieu du maximum ne paraît pas d'une grande importance, parce que (sauf erreur) cela ne devrait entraîner que des modifications mineures de l'algorithme.

L'énoncé présente par contre une particularité remarquable: l'ordre mutuel des diverses sommes obtenues est complètement modifié lorsque l'on impose une translation à l'ensemble des valeurs du tableau.

Soit en effet deux listes de données mutuellement décalées d'une valeur constante: T2[k] = T1[k] + C ;
les sommes de (m) termes consécutifs (m = j - i + 1) admettent pour expression:
S2[i, j] = S_k=i^k=j(T2[k]) = S_k=i^k=j(T1[k]) + S_k=i^k=j(C) = S1[i, j] + m*C
et présentent entre elles un écart proportionnel au nombre de termes.

L'extremum obtenu dépend donc du décalage (C), et il ne peut être question d'envisager un ensemble de valeurs de même signe - j'ai moi-même été tenté par une transformation analogue.

# Une remarque: l'ensemble des sommes partielles S[i, j] peut être représenté sur une matrice triangulaire supérieure, dont les éléments non nuls se situent sur ou au-dessus de la diagonale principale (i <= j); un tel schéma permet peut-être de mieux saisir l'algorithme.