un algo qui supp le min et le max d'1 tableau à la fois SVP

un algo qui supp le min et le max d'1 tableau à la fois SVP - Algo - Programmation

Marsh Posté le 06-01-2013 à 13:21:07    

Salut à tous je suis nouvelle ici, je souhaite savoir comment peut-on écrire un algorithme simple àfin de supprimer le min et le max d'un tableau, au même temps. ils n'ont pas énoncé si il était trié ou pas :sweat:  
 Merci d'avance


---------------
:)
Reply

Marsh Posté le 06-01-2013 à 13:21:07   

Reply

Marsh Posté le 06-01-2013 à 15:09:47    

Déjà votre problème n'est pas bien énoncé: que faites vous si plusieurs valeurs de vôtre tableau sont la valeur max (ou min)? vous les supprimez toutes?
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 07-01-2013 à 11:21:19    

Tri des valeurs dans l'ordre croissant (cf algos de tri, c'est pas ça qui manque), récupération des valeurs min (1ère dans le tableau) et max (dernière dans le tableau), création d'un tableau temporaire, recopie dans ce tableau des valeurs sauf si elles sont = à la valeur min ou max du tableau source.
 
La question de Gilou est pertinente, mon algo ne recopiera aucune valeur = à min ou max.


Message édité par rufo le 07-01-2013 à 11:21:35

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
Reply

Marsh Posté le 07-01-2013 à 12:56:28    

Sauf que si tu veux pas trier ton tableau, et conserver l'ordre initial, aux retraits près, ça marche pas.
 
Une possibilité
Je note TAILLE la taille du tableau initial.
Si TAILLE < 3 le tableau résultat est vide et on a  fini
Sinon
1) deux variables MIN et MAX initialisées a la première valeur du tableau.
2) on parcourt le tableau, et a chaque étape, on modifie MIN ou MAX si la valeur de la case courante est plus petite que MIN ou plus grande que MAX
3) une variable CNT initialisée a 0
4) on parcourt le tableau a nouveau, si la valeur de la case courante est MIN ou MAX, et on incrémente CNT
Si TAILLE = CNT le tableau résultat est vide et on a  fini
Sinon
1) on crée un nouveau tableau de taille TAILLE - CNT
2) on parcourt le tableau a nouveau, et on a chaque étape, si la valeur courante n'est pas MIN ni MAX, on la copie dans le nouveau tableau
On renvoie le nouveau tableau comme résultat (ou on remplace l'ancien tableau par le nouveau, selon ses besoins).
 
Algo qui est linéaire en O(3*n) [donc en O(n)] ou n est la taille du tableau initial, bref, qui n'est pas couteux.  
Ajouter un tri va au mieux faire passer la complexité à du O(n*log(n)), ce qui n'est pas utile, sauf si on a besoin de retirer les min et max a plusieurs reprises, et qu'on ne veut pas garder l'ordre initial, auquel cas, une fois le tableau trié, ça devient assez trivial.
 
A+,


Message édité par gilou le 07-01-2013 à 13:00:02

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed