mode

mode - Algo - Programmation

Marsh Posté le 19-09-2003 à 00:42:15    

quel est l'algo le plus efficace pour trouver le mode d?une suite de nombres (c?est-à-dire, le nombre qui apparaît le plus souvent dans la suite?
 
je sais qu'il y a cette méthode:

Code :
  1. 1. TrouverMode(T[1?.N])
  2. 2. mode = 0
  3. 3. nbmode = 0
  4. 4. Pour i = 1 à N
  5. 5.      nboccurence = 0
  6. 6.      Pour j = 1 à N
  7. 7.            Si t(i) = t(j) alors
  8. 8.                   nboccurence = nboccurence + 1
  9. 9.     Si nboccurence > nbmode
  10. 10.           nbmode = nboccurence
  11. 11.           mode = t(i)
  12. 12. Retourner mode


 
 
mais bon c'est du n²
donc poubelle...
 
il y a moyenne de le faire il me semble en une boucle... mais je me rappele pu comment


---------------
Borland rulez: http://pages.infinit.net/borland
Reply

Marsh Posté le 19-09-2003 à 00:42:15   

Reply

Marsh Posté le 19-09-2003 à 00:54:17    

le mieux qui me vienne comme ça, c'est n*log(n)


---------------
From now on, you will speak only when spoken to, and the first and last words out of your filthy sewers will be "Sir!"
Reply

Marsh Posté le 19-09-2003 à 02:53:16    

SchnapsMann a écrit :

le mieux qui me vienne comme ça, c'est n*log(n)


 
et l'algo?


---------------
Borland rulez: http://pages.infinit.net/borland
Reply

Marsh Posté le 19-09-2003 à 04:43:35    

os2 a écrit :


 
et l'algo?

moi je dirai : tu tries et après tu parcours une fois en comptant

Reply

Marsh Posté le 19-09-2003 à 07:38:53    

SchnapsMann a écrit :

le mieux qui me vienne comme ça, c'est n*log(n)


 
on doit pouvoir descendre a 2*N dans certains cas
 
admettons que les valeurs de T vont de 0 a 256
 

Code :
  1. int res[256];
  2. //mise de res a 0
  4. for (int i=0;i<N;i++)
  5. res[T[i]]++;
  7. int indexMax = 0;
  8. for (int i=1;i<N;i++)
  9. {
  10. if (res[i] > res[indexMax]
  11. indexMax = i;
  12. }

 

Reply

Marsh Posté le 19-09-2003 à 08:12:55    

voir meme N....
 
 

Code :
  1. int res[256];
  2. //mise de res a 0  
  3. int max =0;
  4. int maxIndex = 0;
  6. for (int i=0;i<N;i++)
  7. {
  8. res[T[i]]++;
  9. if (res[T[i]] > max)
  10. {
  11. max = res[T[i]];
  12. maxIndex = T[i];
  13. }
  14. }


Message édité par chrisbk le 19-09-2003 à 08:13:03
Reply

Marsh Posté le 19-09-2003 à 08:35:33    

chrisbk a écrit :


 
on doit pouvoir descendre a 2*N dans certains cas
 
admettons que les valeurs de T vont de 0 a 256
 


 
heu, là quand même c'est une restriction forte !
la solution d'os2 (tri + comptage sequentiel) est a mon avis la meilleure pour le cas generale (je vois pas mieux en fait :p)

Reply

Marsh Posté le 19-09-2003 à 08:37:41    

philou_a7 a écrit :


 
heu, là quand même c'est une restriction forte !
la solution d'os2 (tri + comptage sequentiel) est a mon avis la meilleure pour le cas generale (je vois pas mieux en fait :p)

ben c'est analogue au tri dit "de la trieuse"    [:spamafote] mais bon, c'est un ca supair particulier

Reply

Marsh Posté le 19-09-2003 à 09:36:55    

os2 a écrit :


 
et l'algo?


 
insertion de tous les éléments dans un tas binaire: n*log(n), à la fin le plus grand (ou plus petit c'est selon) est en sommet de tas.


---------------
From now on, you will speak only when spoken to, and the first and last words out of your filthy sewers will be "Sir!"
Reply

Marsh Posté le 19-09-2003 à 09:40:10    

SchnapsMann a écrit :


 
insertion de tous les éléments dans un tas binaire: n*log(n), à la fin le plus grand (ou plus petit c'est selon) est en sommet de tas.
 

y avais po pensé  :jap:

Reply

Marsh Posté le 19-09-2003 à 09:40:10   

Reply

Marsh Posté le 19-09-2003 à 10:03:13    

SchnapsMann a écrit :


 
insertion de tous les éléments dans un tas binaire: n*log(n), à la fin le plus grand (ou plus petit c'est selon) est en sommet de tas.
 


 
a vi  ;)  
par contre, l'implementation est un poil plus lourde :D

Reply

Marsh Posté le 19-09-2003 à 10:08:44    

philou_a7 a écrit :


 
a vi  ;)  
par contre, l'implementation est un poil plus lourde :D


 
pas tellement, c'est bidon à implémenter un tas binaire


---------------
From now on, you will speak only when spoken to, and the first and last words out of your filthy sewers will be "Sir!"
Reply

Marsh Posté le 19-09-2003 à 10:09:28    

un petit peu plus qu'un tri quand même ;)

Reply

Marsh Posté le 19-09-2003 à 10:11:02    

philou_a7 a écrit :

un petit peu plus qu'un tri quand même ;)

quel langage ?

Reply

Marsh Posté le 19-09-2003 à 13:52:44    

chrisbk a écrit :

voir meme N....
 
 

Code :
  1. int res[256];
  2. //mise de res a 0  
  3. int max =0;
  4. int maxIndex = 0;
  6. for (int i=0;i<N;i++)
  7. {
  8. res[T[i]]++;
  9. if (res[T[i]] > max)
  10. {
  11. max = res[T[i]];
  12. maxIndex = T[i];
  13. }
  14. }




 
merci c'est cette solution que je cherchais...


---------------
Borland rulez: http://pages.infinit.net/borland
Reply

Sujets relatifs:

Leave a Replay

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