Discussion :

[thom's]

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 :

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

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

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

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

[Kaamui]

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 :

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

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

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

[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

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

[larchicha]

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