Elément le plus souvent dans un tableau

Version imprimable

Salut voilà le probleme,
Soit un tableau (T) d'entiers. On suppose que ce tableau n'est pas trié, ecrire un algorithme qui retourne l'élement qui apparaît le plus souvent dans (T) ainsi que son nombre d'occurrence. Si plusieurs éléments sont différents répondent aux problème, votre algorithme doit en fournir "un", quel qu'il soit. Vous ne devez utiliser aucun autre tableau que celui sur lequel vous travaillez.

Je vais poster mon algorithme soon, et j'attend votre aide
tout d'abodr je commence avec l'idée principale :

-Lecture du taille du tableau (T)
-Chargement du tableau (N,T)
-Un appel à la procédure "Traitement" qui compte l'élément le plus souvent dans (T).
==> Fonctionnement de "Traitement"
-Les données du Proc sont le tableau (T) et son taille (N).
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 max <-- 0 Pour i de 1 à N faire cpt <-- 0 Si Fn Verif(T[i],i-1,T) = Faux Alors Pour j de 1 à N Faire Si T[i] = T[j] Alors cpt<--cpt+1 Fin si Fin Pour Si cpt >= max Alors max <-- cpt posF <-- i Fin Si Fin pour
Finalement on annonce à l'élément le plus souvent qui est T[posF] se répéte (max) fois de rang (posF) dans le tableau.

Merci d'avance ?

/*La fonction Verfi vérifie si lélément pointé du (T) est existe précedement ou pas */

24/11/2008, 10h27
Zavonen

Une 'petite' amélioration. Dans ta boucle intérieure (boucle j).Si tu constates que cpt+(N-j) <max pas la peine d'aller jusqu'au bout, tu peux interrompre la boucle j aucune chance de battre max.
Par ailleurs, avant de te lancer dans la calcul du nombre d'occurrences de T[i], commence par vérifier que T[i] est nouveau (pas déjà contenu dans T[0];..T[i-1]). Même si cette vérification est couteuse, il se peut qu'on soit gagnant en termes d'efficacité globale, mais cela reste à voir.
24/11/2008, 11h35
pseudocode

Ca ne serait pas plus rapide de trier le tableau puis de le parcourir en incrémentant un compteur lorsque 2 éléments consécutifs sont égaux ?
24/11/2008, 13h02
ToTo13

Bonjour,

est ce que tu as des contraintes mémoires ou des informations a priori sur les éléments du tableau ?
Car sinon tu peux :
- faire un passage pour trouver le min et le max des éléments.
- faire le début d'un tri par dénombrement.
- et tu as ta réponse ;)

Si tu n'as pas d'informations, fais ce que les autres te proposent.
24/11/2008, 16h08
direct

Salut, oui bien sur avec tri on pourra la faire plus simplement mais il faut pas l'utiliser merci !!! :mouarf:
24/11/2008, 16h09
Jedai

Citation:

Envoyé par ToTo13

Bonjour,

est ce que tu as des contraintes mémoires ou des informations a priori sur les éléments du tableau ?
Car sinon tu peux :
- faire un passage pour trouver le min et le max des éléments.
- faire le début d'un tri par dénombrement.
- et tu as ta réponse ;)

Si tu n'as pas d'informations, fais ce que les autres te proposent.

Citation:

Envoyé par direct

Vous ne devez utiliser aucun autre tableau que celui sur lequel vous travaillez.

Ce qui exclut cette approche, et probablement toutes les approches non-naïves si on prend tableau comme signifiant toute structure de donnée auxiliaire.

Trier le tableau est effectivement meilleur, mais c'est une solution destructrice, l'ordre initial du tableau ne peut être retrouvé (sans tableau auxiliaire en tout cas).

A vrai dire je ne vois pas mieux que O(n²) dans ces conditions... Mais il y a peut-être une astuce.

--
Jedaï

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/env python
import random
import time
 
taille=5000
 
Tab=[random.randint(1,200) for i in xrange(0,taille)]
 
#naïf
def TrouveMax1():
    max=1
    winner=0
    for i in xrange (0,taille):
        count=0
        for j in range (0,taille):
            if Tab[j]==Tab[i]:
                count+=1
        if count>max:
            max=count
            winner=i
    print max
    print Tab[winner]
 
#naïf amélioré
def TrouveMax2():
    max=1
    winner=0
    for i in xrange (0,taille):
        count=0
        for j in range (0,taille):
            if Tab[j]==Tab[i]:
                if j<i:
                    break #déjà traité auparavant on va pas recommencer
                else:
                    count+=1
            if count+taille-j<max:
                break #aucune chance on arrête là
        if count>max:
            max=count
            winner=i
    print max
    print Tab[winner]
 
def main():
    start1=time.time()
    TrouveMax1()
    end1=time.time()
    print end1-start1
    start2=time.time()
    TrouveMax2()
    end2=time.time()
    print end2-start2
 
if __name__ == '__main__':
    main()

Résultats:

Citation:

>>>
40
127
7.48399996758
40
127
1.64100003242
>>>

24/11/2008, 23h27
direct

Zavonen J'ai rien compris !!:evilred:
25/11/2008, 00h06
Zavonen

C'est simple, dans l'algo naïf classique on teste les nombres un à un dans l'ordre en commençant par Tab[0]. Supposons que la valeur Tab[0] apparaisse 28 fois dans le tabeau aux indices 11, 15, 247, ......
Quand dans ta boucle i tu vas passer sur les indices 11,15, etc... tu peux les sauter car le résultat est le même que pour Tab[0], c'est du travail déjà fait. L'idéal serait, comme dans un crible de marquer tous les éléments ayant été comptés, mais ici on ne peut pas car on n'a droit à aucune ressource mémoire supplémentaire.
Comme je n'ai pas cette ressource, je fais comme avec l'algo classique, mais si je trouve une valeur égale à T[i] pour un indice strictement inférieur, j'arrête tout (enfin je passe à l'itération suivante).
L'expérience prouve (voir résultats ci-dessus) que ce truc permet d'économiser 80% du temps.
Si tu ne comprends pas bien fais le avec du papier et un crayon.