Discussion :

[direct]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 */

[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.

[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 ?

[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.

[direct]

Salut, oui bien sur avec tri on pourra la faire plus simplement mais il faut pas l'utiliser merci !!!

[Jedai]

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.

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ï

[Zavonen]

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

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:

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

[direct]

Zavonen J'ai rien compris !!

[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.