Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
807 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Recherche des deux plus grand éléments d'une liste : tournoi

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Recherche des deux plus grand éléments d'une liste : tournoi

n°1359096
zianvd
Legends Never Die
Posté le 03-05-2006 à 23:04:58  profilanswer
 

Bonjour,
 
Je n'arrive pas à trouver l'algorithme permettant de trouver les deux plus grands éléments d'une liste à l'aide de la méthode du tournoi...tout en ayant une complexité d'ordre n, ou logarithmique...
 
Je vois le principe des arbres où le premier plus grand élément est trouvé au premier tour, et le second plus grand élément est trouvé dés le deuxieme parcours (on aura conservé les perdants face au plus grand élémént du premier tour)...
 
mais je n'arrive pas àmettre en oeuvre.
 
Si quelqu'un a l'algorithme sous la main...  :??:

mood
Publicité
Posté le 03-05-2006 à 23:04:58  profilanswer
 

n°1360489
_PakMan_
Posté le 05-05-2006 à 15:23:17  profilanswer
 

Le plus simple si ta liste n'est pas trie est en complexite O(n) et c'est comme une recherche de max sauf que tu as deux variables au lieux d'une.
Si ta liste est triee alors tu peux avoir une recherche dichotomique: O(log(n)) toujours avec deux variables...


---------------
"Tant qu'il y aura des hommes il y aura de comptoirs"
n°1360762
Trap D
Posté le 06-05-2006 à 01:28:56  profilanswer
 

zianvd a écrit :

Bonjour,
 
Je n'arrive pas à trouver l'algorithme permettant de trouver les deux plus grands éléments d'une liste à l'aide de la méthode du tournoi...tout en ayant une complexité d'ordre n, ou logarithmique...
 
Je vois le principe des arbres où le premier plus grand élément est trouvé au premier tour, et le second plus grand élément est trouvé dés le deuxieme parcours (on aura conservé les perdants face au plus grand élémént du premier tour)...
 
mais je n'arrive pas àmettre en oeuvre.
 
Si quelqu'un a l'algorithme sous la main...  :??:


Salut
 
je viens de mettre en oeuvre la méthode en C, l'algo fonctionne bien, mais on doit pouvoir faire sans doute mieux.
 
On suppose qu'on a un tableau T du style
________________________________________
|  5 |  1 | 10 |  3 | 15 | 19 |  5 |  8 | 20 | 30 |
________________________________________
   0     1     2    3     4     5     6    7    8     9
 
On va construire une suite de tableaux de ce style
 
T1
__________________
|  0 |  2 | 5 |  7 | 9 |  
__________________
 
On mémorise 0 car T[0] est plus grand que T[1].
On mémorise 2 car T[2] est plus grand que T[3].
On mémorise 5 car T[5] est plus grand que T[6].
 
 
T2
___________
|  2 | 5 | 9 |  
___________
 
On mémorise 2 car T[T1[1]] est plus grand que T[T1[0]].
On mémorise 5 car T[T1[2]] est plus grand que T[T1[3]].
On mémorise 9 car T[T1[4]] est seul.
 
 
T3
________
|  5 | 9 |  
________
 
On mémorise 5 car T[T2[1]] est plus grand que T[T1[0]].
On mémorise 9 car T[T2[3]] est seul.
 
T4
____
|  9 |  
____
On a terminé, T[T4[0]] est le plus grand nombre.
 
Pour pouvoir trouver le second plus grand élément, il faut parcourir la liste des tableaux en sens inverse
J'ai donc créer une structure où je mémorise la place de chaque nombre dans le tableaux précédent.
Mes tableaux T1, T2, et T3 se présentent sous cette forme :
   
T1
__________________
|  0 |  2 | 5 |  7 | 9 |  
__________________
|  0 |  2 | 5 |  7 | 9 |  
__________________
 
 
T2
___________
|  2 | 5 | 9 |  
___________
|  1 | 3 | 4 |  
___________
 
T3
________
|  5 | 9 |  
________
|  1 | 2 |  
________
 
 
T4
____
|  9 |  
____
|  1 |  
____
 
 
Enfin il faut faire attention aux limites de tableaux, donc il faut mémoriser dans un tableaux à part la taille de chaque tableau intermédiaire.


Message édité par Trap D le 06-05-2006 à 09:16:07
n°1361150
Trap D
Posté le 07-05-2006 à 10:41:35  profilanswer
 

Au lieu de s'en tenir au système de l'arbre et du parcours en arrière, en réfléchissant un peu, on peut trouver les deux nombres en même temps : en effet, on mémorisera en même temps le plus grand des nombres à comparer et le plus grand de ceux qu'il aura "dominés".
 
 
On suppose qu'on a un tableau T du style  
___________________________________________
|  5 |  1 | 10 |  3 | 15 | 19 |  5 |  8 | 20 | 4 |30 |  
___________________________________________  
 
 
On va construire une suite de tableaux de ce style  
 
T1  
_________________________
|  5 | 10 |  19 |  8 | 20 | 30 |
_________________________
|  1 |   3 | 15 |  5 |  4 |  MIN_INT
_________________________
 
C'est - à - dire qu'on mémorise le plus grand et l'autre au premier tour.
S'il reste un nombre tout seul, on peut utiliser INT_MIN en plus petit en C.
 
 
T2  
_____________
| 10 | 19 | 30 |  
_____________
|  5 | 15 | 20 |
_____________
 
Cette fois-ci on mémorise 10 car il est plus grand que 5 et comme 5 est plus grand que 3, on mémorise en second plus grand 5
On mémorisera enxsuite 19 car il est plus grand que 8 et on garde 15.
Enfin on mémorise 30 et 20 en plus petit
 
T3  
_________
| 19 | 30 |  
_________
| 15 | 20 |
__________
 
On garde (19, 15) et (30,20)
 
T4  
_____
| 30 |  
_____  
| 20 |
_____
On a terminé, 30 et 20 sont bien les deux plus grands nombres !


Message édité par Trap D le 07-05-2006 à 10:42:23

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Recherche des deux plus grand éléments d'une liste : tournoi

 

Sujets relatifs
Selection dans une ListeListe de mot sur fichier txt dans lequel le script doit piocher
Liste déroulante et Zone de liste [ Access ]Ouvrir un tableau avec une liste modifiable
Changer dynamiquement l'élément selected d'une liste déroulant ?Fonction de recherche en PHP
Recherche d'une librairie de reconnaissance d'imageListe imbriquées refusées par le W3C ?
Liste chainée dans un fichierPackages et liste générique
Plus de sujets relatifs à : Recherche des deux plus grand éléments d'une liste : tournoi


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR