-
tableaux et repetitions
Bonjour,
J ai un probleme dont je me bloque la dessus,
J ai un tableaux integer a rentré et ensuite voire le nombres des repetitions de chque nombres dans ce tableaux
par exemple A=1,3,4,2,4,5,1
le nombre 1 se repete 2
3 se repete 1
ect..........
pouvez vous m aider dans ce probleme?
merci
-
connais-tu l'ensemble des nombres possible de ton tableau ?
-
Oui , c est un tableaux A(10) par exemple
-
Salut,
Le plus facile consiste bien souvent à parcourir le tableau plusieurs fois:
- tu regarde l'élément en position 0
- tu le compare avec tous les éléments suivant
- tu recommence, mais avec l'élément en position 1
- ...
Ce n'est peut etre pas le plus rapide, mais c'est généralement le plus facile à implémenter ;)
-
Je pense que PRomu@ld pense au tri "du panier" qui ne fonctionne qu'avec des entiers :
si l'écart maximum N des nombres du tableau est assez petit, tu peux créer un tableau de taille N :
Soit Tab 1 .. 10 le tableau des nombres
Soit Resultat 1..N le tableau de tous les nombres possibles
soit mini le plus petit des nombres
tu fais cette boucle
pour i de 1 à 10 faire
Resultat(Tab(i)-mini) = Resultat(Tab(i)-mini) + 1
La répartition est obtenue en parcourant ensuite le tableau Resultat.
J'espère que j'ai été clair :oops:
-
C'est exactement à ça que je pensais (sauf que j'appelle ça le tri postal ;))
En général on peut prendre mini = 0.
Si toutefois les valeurs sont relativement grandes, et que le nombre à traiter n'est pas énorme, on peut s'arranger autrement (en passant par des indirections), mais ça nécessite de faire un tableau de plus et des opérations indirections. Ceci est toujours plus rapide que de faire la méthode brute qui va se faire en O(n^2).
Une autre solution consiste à utiliser une structure de type arbre binaire de recherche et effectuer des opérations d'insertion. A chacun des noeuds, tu maintiens deux choses : le nombre et son nombre d'occurence.
Ensuite, avec un parcours d'arbre, tu as tes nombres dans l'ordre avec leur nombre d'occurence.
Il existe une foultitude d'algorithmes, plus ou moins compliqués (tu peux même faire ça avec un graphe). C'est un formidable exemple qui montre qu'un problème a plusieurs solutions. ;)
-
quel sera l alogorithm dans ce cas?
-
-
autrement dit quel est l algorithm de mon problem?
-
Ce que t'a donné Trap D fonctionne amplement dans ton cas.