Problème d'occurrence !

Version imprimable

Bonjour,
j'ai un soucis concernant ma détermination d’occurrence...

Je dois trouver les occurrences de mes entiers stockés dans un tableau. Une fois que j'ai trouvé ces occurrences, je dois les divisé par le nombre d'entiers contenu dans mon tableau (pour moi, ça sera 10).

J'a donc commencé par déterminer quel sont les occurrences, et que ça me les affiche sur l'écran comme ceci:
Code:

1 2 3 4 5 6 7 8 9 10 11 int occurence(int tab[]) { //ma fonction, qui reçoit mon tableau de 10 entiers en argument int a, b; for (a=0; a < 10; a++) { for (b=0; b < 10; b++) { if (tab[a]==tab[b]) { printf("%d %d donc %d %d", a, b, tab[a], tab[b]); } } } return 0; }
J'aimerai maintenant pouvoir calculer le nombre d'occurence/10 pour chaques entiers.
Et savoir aussi si je suis bien parti ou non...

Merci :)

09/12/2011, 19h07
Kaamui

si tu sais que les valeurs sont restreintes à un petit intervalle, et SEULEMENT dans ce cas, tu peux déclarer un tableau de taille = à ton intervalle, et tu incremente chaque case en passant dans ton tableau.

Cordialement,
09/12/2011, 19h14
thom's

C'est ce que fait mon code non ? Je sais que le tableau possède 10 entiers, j'ai donc mis comme opérateur bolléens: i < 10 et i++
Je suis donc bien parti ?

je ne penses pas que ce sot la même chose, j'essaie de m'expliquer mieux :

admettons un tableau qui contient 7 8 8 7 8 6 5 4 3 8, appelons le T.

voici le code dont je parle (en pseudo-code) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 int T_occ[9] = {0,0,0,0,0,0,0,0,0}; //initialisation du tableau qui va recevoir les occurrences (+1 par rapport à la valeur max, ici 8) int T[10] = {7,8,8,7,8,6,5,4,3,8}; //appel de la méthode que tu auras créé au préalable CalculOccurences(T_occ, T); //MODE DEBUG //on rentre dans la fonction void CalculOccurences(int t_occ[], int t_val[]) { boucle pour //on parcours t_val t_occ[t_val[i]] += 1;//ici, on va faire des +1 directement dans la bonne case, cela permet d'avoir une seule boucle pour fin boucle pour }
ATTENTION, ce code n'est absolument pas une bonne méthode en général, car la complexité en mémoire est potentiellement énorme.

Cordialement

09/12/2011, 20h40
thom's

Merci pour ta méthode, je vais toujours essayer celle là.
Sinon, il existerait donc une autre façon de calculer l'occurrence sans pour cela augmenter la complexité du programme ?
09/12/2011, 20h45
Trademark

@Kamuui: C'est le nombre d'entiers qui est limité, pas leurs valeurs.

Comme tu l'as fait, la méthode naïve est de parcourir l'entièreté du tableau pour chaque entier et encore une fois (boucle imbriquée), pour chaque entier de parcourir le tableau et de compter le nombre d’occurrence à ce moment.

Sinon tu peux aussi commencer par trier ton tableau et puis le parcourir simplement. Mais il existe encore d'autres méthodes, comme utiliser un tableau annexe qui ne contient que des entiers différents et leur nombre d'occurrences. A chaque itération dans ta boucle, tu regardes si ce tableau contient la valeur courante (si oui tu incrémentes, si non tu l'ajoutes avec une occurrence initiale de 1). Pour aller plus loin, tu peux trié le tableau annexe et ainsi accéder à ses éléments de manière dichotomique. Ou encore plus complexe, utiliser une table de hachage (qui garantis presque un accès immédiat).

Il existe peut-être encore d'autres solutions plus efficace.
09/12/2011, 20h50
Kaamui

si bien sur, et ta méthode me semble (j'ai lu en diagonale) bien parti à part que ton type de retour est un int, et que si tu dois appeler ta fonction pour chaque nombre, c'est bizarre. Sinon tu peux utiliser des structures, etc.

@Trademark : lis mon deuxième post
09/12/2011, 20h57
Trademark

Je pensais que vous aviez mal compris :oops:

Votre méthode marche effectivement pour un intervalle réduit comme vous l'avez précisé. On peut ajouter que ça ne marche que pour des entiers positifs.
09/12/2011, 22h48
Kaamui

c'est une remarque pertinente en effet ;)
11/12/2011, 14h16
larchicha

Citation:

Envoyé par Trademark

Sinon tu peux aussi commencer par trier ton tableau et puis le parcourir simplement. Mais il existe encore d'autres méthodes, comme utiliser un tableau annexe qui ne contient que des entiers différents et leur nombre d'occurrences. A chaque itération dans ta boucle, tu regardes si ce tableau contient la valeur courante (si oui tu incrémentes, si non tu l'ajoutes avec une occurrence initiale de 1). Pour aller plus loin, tu peux trié le tableau annexe et ainsi accéder à ses éléments de manière dichotomique. Ou encore plus complexe, utiliser une table de hachage (qui garantis presque un accès immédiat).

Il existe peut-être encore d'autres solutions plus efficace.

Niveau algorithmique, ta méthode, qui est très proche du "tri par comptage", est la plus optimale, me semble t'il... :ccool: