Algo

mode

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : mode

os2

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. TrouverMode(T[1?.N])
2. mode = 0
3. nbmode = 0
4. Pour i = 1 à N
5. nboccurence = 0
6. Pour j = 1 à N
7. Si t(i) = t(j) alors
8. nboccurence = nboccurence + 1
9. Si nboccurence > nbmode
10. nbmode = nboccurence
11. mode = t(i)
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

Publicité

schnapsmann

Zaford Beeblefect

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!"

os2

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

Taz

bisounours-codeur

os2 a écrit :

et l'algo?

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

chrisbk

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 :

int res[256];
//mise de res a 0
for (int i=0;i<N;i++)
res[T[i]]++;
int indexMax = 0;
for (int i=1;i<N;i++)
{
if (res[i] > res[indexMax]
indexMax = i;
}

chrisbk

voir meme N....

Code :

int res[256];
//mise de res a 0
int max =0;
int maxIndex = 0;
for (int i=0;i<N;i++)
{
res[T[i]]++;
if (res[T[i]] > max)
{
max = res[T[i]];
maxIndex = T[i];
}
}

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

philou_a7

\_o< coin ! >o_/

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 )

Taz

bisounours-codeur

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 )

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

schnapsmann

Zaford Beeblefect

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!"

Taz

bisounours-codeur

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:

Publicité

philou_a7

\_o< coin ! >o_/

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

schnapsmann

Zaford Beeblefect

philou_a7 a écrit :

a vi
par contre, l'implementation est un poil plus lourde

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!"

philou_a7

\_o< coin ! >o_/

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

Taz

bisounours-codeur

philou_a7 a écrit :

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

quel langage ?

os2

chrisbk a écrit :

voir meme N....

Code :

int res[256];
//mise de res a 0
int max =0;
int maxIndex = 0;
for (int i=0;i<N;i++)
{
res[T[i]]++;
if (res[T[i]] > max)
{
max = res[T[i]];
maxIndex = T[i];
}
}

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

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

FORUM HardWare.fr

Programmation

Algo

mode

Sujets relatifs
cobol-mode pour emacs	Tracer une ligne entre deux point en mode console
[TurboC] Combinaison mode texte/mode graphique	comment choisir un item par defaut dans combobox en mode dropdownlist
Ouverture en mode partagé ?	Mettre des couleurs dans un prog en mode console ?
[JAVA] Mode plein écran	fopen, fseek, ftell, ... en mode 64 bits
Erreur d'arrondi différentes en mode Debug ou Release	Langages essentiels, à la "mode"?
Plus de sujets relatifs à : mode

Page générée en 0.091 secondes