SVP je souhaite trier un tableau par la fréquence d’occurrence : si j'ai un tableau 1, 2, 2, 1, 2 je souhaite qu'il me retourne 2,2,2,1,1.
Voici mon code et merci d'avance.
// Online C compiler to run C program online
#include <stdio.h>
int main() {
// Write C code here
int tableau[] = {2,4,3,5,4,2,3,1,2};
int tableauOcc[10];
int i,j,k;
for (i=0; i<9;i++){
int occurence=0;
for (j=0;j<9;j++){
if (tableau[i]==tableau[j]){
occurence=occurence+1;
}
}
tableauOcc[i]=occurence;
//printf("%d\n", tableauOcc[i]);
if ( tableauOcc[i] < tableauOcc[i-1] ) {
j = 0;
while ( tableauOcc[j] < tableauOcc[i] ) j++;
int c = tableauOcc[i];
for( k = i-1 ; k >= j ; k-- ) tableauOcc[k+1] = tableauOcc[k];
tableauOcc[j] = c;
}
tableauOcc[i] = tableau[i];
}
for (i=0;i<9;i++){
printf("%d\n", tableauOcc[i]);
}
}
trier C pour créer un tableau F dont les éléments sont {valeur, fréquence} ;
trier F selon le champs fréquence ;
construire le tableau résultat R à partir de F.
Ce que tu essayes de faire pour créer un tableau de fréquence serait plutôt :
créer un tableau F de fréquences de la même taille que le tableau O originel en initialisant chaque position à 0 ;
parcourir le tableau O pour i de 0 à la fin :
si F[i]=0 alors
pour j de i+1 à la fin de O :
si O[i]=O[j] alors
incrémenter F[i]
F[j] = -1
fin si
fin pour
fin si
fin pour.
Le -1 sert à se souvenir que cette valeur a déjà été rencontrée ... et à la fin F contient soit une valeur >0 qui est la fréquence de la valeur au même indice dans O, soit -1 si cette valeur n'est pas la première occurrence.
pour créer ensuite le tableau résultat R :
faire
imax = indice_du_maximum(F)
si F[imax] > 0 alors
ajouter F[imax] fois la valeur O[imax] à la fin de R
F[imax]=-1
fin si
tant que F[imax]>0
Mais cela me semble plus compliqué …
Évidemment les algos sont à prendre avec des pincettes car je te les jette vite fait avec une réflexion minimum … ce ne sont que des idées de départ. Car au départ il y a un algo, l'implémentation vient par la suite.
Edit: évidemment indice_du_maximum(F) renvoie l'indice de la plus grande valeur de F …
> • trier C pour créer un tableau F dont les éléments sont {valeur, fréquence} ; Pas évident pour un débutant ... On peut trier le tableau original en ordre croissant ou décroissant. L'idée sera la même. Où bien on crée un tableau à deux dimensions, ou bien on triche et on met les valeurs dans la position paire et les fréquences dans la position impaire suivante: On pourrait avoir [[1, 2], [2, 3]] ou bien [1, 2, 2, 3] Comme a dit White Crow, on doit trier ce résultat par ordre de fréquences. Ça risque d'être amusant dans les deux cas ... Alors j'aurais [[2, 3], [1, 2]] ou bien [2, 3, 1, 2] Tu recopies chaque premier nombre (valeur) dans la nouvelle liste autant de fois que le second nombre (fréquence) l'indique.
> • trier C pour créer un tableau F dont les éléments sont {valeur, fréquence} ; (...) Où bien on crée un tableau à deux dimensions, ou bien on triche et on met les valeurs dans la position paire et les fréquences dans la position impaire suivante:
(...)
Je pense que l'idée que voulait suggérer White Crow, et qui me semble assez naturelle et pratique, est de créer un type struct avec dedans des membres valeur et fréquence et créer un tableau de struct que l'on puisse remplir avec ces données.
Pour le tri, les permutations deviennent faciles avec une struct, puisque le C va s'occuper tout seul de copier tous les membres lors d'une affectation.
Je n'ai pas vérifié si ton code était exact, mais j'ai essayé de l'exécuter en mettant en entrée ton exemple "1, 2, 2, 1, 2". En sortie ton programme donne :
1 2 2 1 2
et cela ne correspond ni aux fréquences des nombres (qui sont présents 2 ou 3 fois dans ce jeu de données), ni à ce que ton programme est sensé retourner et que tu dis ne pas savoir retourner : 2,2,2,1,1
Alors, la première chose serait de corriger le code qui calcule les fréquences.
Ensuite, lorsque cela est au point, si tu t'obstines à vouloir utiliser 2 tableaux (au lieu d'un seul tableau de struct contenant les deux données), et bien il suffit, lorsque tu tries le tableau des fréquences et que tu fais une permutation, de faire exactement la même permutation dans ton tableau de nombres.
Maintenant le code du PO est incorrect. Je pense avoir décrit ses intentions en deuxième partie de mon premier message … mais il ne semble pas réceptif.
Il me semble que la première étape serait de trier le tableau avant de penser à calculer les fréquences. C'est vrai qu'une structure serait plus simple qu'un tableau de 2-tuples ou un tableau à deux dimensions. Après, le reste est relativement simple. Ton tableau [1, 2, 2, 1, 2] devient [1, 1, 2, 2, 2]
Le Tout est souvent plus grand que la somme de ses parties.
Maintenant le code du PO est incorrect. Je pense avoir décrit ses intentions en deuxième partie de mon premier message … mais il ne semble pas réceptif.
De rien mais si tu utilises ça sans discernement on va voir de suite que tu n'en es pas l'auteur … surtout si tu ne bites pas un mot de ce que je t'ai écrit.
C'est vrai qu'on peut le faire sans trier le tableau de départ. Surtout que j'utilisais un stupide tri par sélection dont la complexité sur les comparaison est O(n²) et et O(n) pour les échanges.
Le Tout est souvent plus grand que la somme de ses parties.
Si ZakAad veut faire son propre code, tout en le guidant un peu, je lui propose de tenter d'implémenter la fonction fsort() sans tri préalable des valeurs, en utilisant une fonction do_count() que l'on appelle dans fsort() :
int do_count(int value, size_t n, struct freq * freq, size_t * indexes_found) {
size_t count = 0;
/* TODO */
return count;
}
int * fsort(size_t n, const int * const array) {
int * res = malloc(sizeof(int) * n);
/* TODO */
return res;
}
de sorte que ces fonctions passent les tests suivants (faire un #include <assert.h> pour utiliser la fonction assert() de la bibliothèque standard) :
/* helper function for testing and do tests */
int cmp_freq(struct freq * f1, struct freq * f2, size_t n) {
for (size_t i = 0; i < n; i++)
if ( !(f1[i].value == f2[i].value &&
f1[i].freq == f2[i].freq) )
return 1;
return 0;
}
int main(void) {
int simple_array[] = {1, 2, 2, 1, 2};
size_t nb_val = 5;
/* test do_count() */
size_t * indexes_found = malloc(sizeof(size_t) * nb_val);
struct freq * freq = calloc(nb_val, sizeof(struct freq));
for (size_t i = 0; i < nb_val; i++)
freq[i].value = simple_array[i];
int count1 = do_count(1, nb_val, freq, indexes_found);
assert(count1 == 2 &&
"1 value has count of 2");
struct freq freq_expected1[] = {
{ .value = 1, .freq = 2 },
{ .value = 2, .freq = 0 },
{ .value = 2, .freq = 0 },
{ .value = 1, .freq = 2 },
{ .value = 2, .freq = 0 },
};
assert(cmp_freq(freq, freq_expected1, nb_val) == 0 &&
"freq expected after processing 1 value");
int count2 = do_count(2, nb_val, freq, indexes_found);
assert(count2 == 3 &&
"2 value has count of 3");
struct freq freq_expected2[] = {
{ .value = 1, .freq = 2 },
{ .value = 2, .freq = 3 },
{ .value = 2, .freq = 3 },
{ .value = 1, .freq = 2 },
{ .value = 2, .freq = 3 },
};
assert(cmp_freq(freq, freq_expected2, nb_val) == 0 &&
"freq expected after processing 2 value");
int done_total = count1 + count2;
assert(done_total == nb_val &&
"we have processed all values for freq");
free(freq);
free(indexes_found);
/* test fsort() with simple_array */
int farray_expected[] = {2, 2, 2, 1, 1};
int * farray = fsort(nb_val, simple_array);
assert(memcmp(farray, farray_expected, sizeof(simple_array)) == 0 &&
"{1, 2, 2, 1, 2} -> {2, 2, 2, 1, 1}");
free(farray);
/* test fsort() with another another_array */
int another_array[]= {6, 5, 2, 6, 6, 1, 0, 6, 2, 5, 6, 8, 6, 3, 6, 4,
0, 7, 3, 0};
nb_val = sizeof(another_array) / sizeof(int);
int farray_expected_another[] = {6, 6, 6, 6, 6, 6, 6, 0, 0, 0, 5, 2,
2, 5, 3, 3, 1, 8, 4, 7};
farray = fsort(nb_val, another_array);
assert(memcmp(farray, farray_expected_another,
sizeof(another_array)) == 0 &&
"test case from White Crow's random array, ordered by freq only: {6, 5, 2, 6, 6, 1, 0, 6, 2, 5, 6, 8, 6, 3, 6, 4, 0, 7, 3, 0} -> {6, 6, 6, 6, 6, 6, 6, 0, 0, 0, 5, 2, 2, 5, 3, 3, 1, 8, 4, 7}");
free(farray);
/* done */
printf("all tests pass\n");
return 0;
}
Les tests devraient être parlants sur le comportement attendu de ces deux fonctions.
Maintenant, on procède ainsi :
Avec les fonctions vides contenant seulement les TODO, le code doit compiler, mais le premier assert doit échouer lors de l'exécution, constater cela.
faire les changements minimums au code pour faire passer le test, constater qu'il passe
refactoriser et améliorer le code et vérifier que le test passe toujours
passer au test suivant qui échoue
répéter les opérations précédentes 1 à 3 en vérifiant l'absence de régression, jusqu'à ce que tous les tests passent
ZakAad aura terminé son oeuvre
P.S.
@White Crow: ton code est très intéressant. Par exemple, c'est astucieux d'écrire "sizeof *freq" plutôt que "sizeof(struct freq)" dans struct freq *freq=calloc(n, sizeof *freq);, car cela permet, si on change demain le type, d'éviter d'avoir à penser à faire un autre changement dans le contenu de sizeof(). Il y a plein d'autres choses qui sont très particulières à ta façon de coder, et sans doutes un poil complexe (les VLA dans les paramètres de fonctions avec des arguments static systématiques...).
Edit : correction du test pour another_array (sizeof, résultat ordonné seulement sur les fréquences et suppression de l'appel à display_array())
@White Crow: ton code est très intéressant. Par exemple, c'est astucieux d'écrire "sizeof *freq" plutôt que "sizeof(struct freq)" dans struct freq *freq=calloc(n, sizeof *freq);, car cela permet, si on change demain le type, d'éviter d'avoir à penser à faire un autre changement dans le contenu de sizeof(). Il y a plein d'autres choses qui sont très particulières à ta façon de coder, et sans doutes un poil complexe (les VLA dans les paramètres de fonctions avec des arguments static systématiques...).
- Edité par Dlks il y a moins de 30s
En effet, le sizeof d'une variable est bien plus souple qu'un sizeof d'un type. La notation VLA est, quant à elle, recommandée dans la future norme C23 dans les prototypes de fonctions qui contiennent une taille de tableau et le tableau. Le static indique au compilo que le paramètre passé est non nul et qu'il pointe vers une zone valide contenant au moins n valeurs valides (section 6.7.6.3.6).
Merci edgarjacobs. Je ne me rappelais pas comment transtyper une structure dans une fonction. Voici la variante améliorée: int compare(const void *f1, const void *f2){ if(((const Frequency *)f1)->fre > ((const Frequency *)f2)->fre) return -1; if(((const Frequency *)f1)->fre == ((const Frequency *)f2)->fre) return ((const Frequency *)f1)->val - ((const Frequency *)f2)->val; return 1; } C'est supposé être plus élégant, mais c'est plus lourd.
J'aurais pu me faire une macro du genre: #define CAST (const Frequency *)
J'ai également écrit la variante où je trie le tableau avant de calculer les fréquences. Ça n'est pas plus gros ou compliqué, et ça serait plus efficace avec de gros tableaux.
- Edité par PierrotLeFou 27 octobre 2021 à 18:05:58
Le Tout est souvent plus grand que la somme de ses parties.
Je ne me rappelais pas comment transtyper une structure dans une fonction. Voici la variante améliorée: int compare(const void *f1, const void *f2){ if(((const Frequency *)f1)->fre > ((const Frequency *)f2)->fre) return -1; if(((const Frequency *)f1)->fre == ((const Frequency *)f2)->fre) return ((const Frequency *)f1)->val - ((const Frequency *)f2)->val; return 1; } C'est supposé être plus élégant, mais c'est plus lourd.
Il y a beaucoup plus simple.
1. utiliser des variables pour alléger les écritures
2. se rappeler que qsort attend une fonction de comparaison qui retourne un nombre dont le signe indique de quel côté ça penche. Pas necessairement 0, 1 ou -1.
3. Mon seul souvenir du cours de philo "comparer c'est étudier les différences". Et quand on compare des nombres, la soustraction fait le job
int compare_frequency(const void *p1, const void *p2){
const Frequency
*f1 = p1,
*f2 = p2;
return f1->fre - f2->fre;
}
- Edité par michelbillaud 27 octobre 2021 à 19:15:00
Je retourne -1 ou +1 parce que c'est commode. Mais je retourne la différence des valeurs si les fréquences sont égales. C'est vrai que j'aurais pu définir 4 variables du genre: fre1, fre2, val1 et val2. Dans le code republié par edgarjacobs, c'est presque ça que je faisais.
Le Tout est souvent plus grand que la somme de ses parties.
Ah j'ai pas remarqué que tu faisais une comparaison portant sur 2 critères : fréquence puis valeur. Et je me suis planté sur le sens voulu
Dans ce cas, prenons le temps de bien nommer la fonction, ça évitera d'avoir à mettre des commentaires :
int compare_by_desc_frequency_then_asc_value (const void *p1, const void *p2){
const Frequency
*f1 = p1,
*f2 = p2;
int difference = f2->fre - f1->fre; // descending frequency
if (difference == 0) {
difference = f1->val - f2->val; // ascending value
}
return difference;
}
Truc : Pour se rappeler du sens, penser aux entiers
1 vient avant 2
la différence 1-2 est négative
donc pour une fonction qui exprime une comparaison entre a et b, réponse négative si a vient avant b dans l'ordre voulu.
edit : quand il y a plein de critères (>=3 par exemple) on peut prendre ce schéma
int r = a->machin - b->machin;
if (r != 0) return r
r = a->truc - b->truc;
if (r != 0) return r
r = a->chose - b->chose;
if (r != 0) return r
r = a->bidule - b->bidule;
return r;
qui évite de s'embrouiller les pieds dans un tas de if emboités.
- Edité par michelbillaud 27 octobre 2021 à 21:55:47
Heureusement que je n'ai pas dix critères, le nom serait particulièrement long. C'est certain que ta façon d'écrire le code est nettement plus claire. Je suis un one-liner invétéré. Pour le sens de l'ordre, j'espère que la remarque n'était pas pour moi ... Ça fait longtemps que je connais l'équivalence entre "plus petit" et "vient avant". Pour les critères multiples, on est avantagé dans une fonction. On fait des return aux endroits voulus aulieu d'essayer d'aller à la fin pour faire son return.
Le Tout est souvent plus grand que la somme de ses parties.
On a toujours dit que les fonctions, c'était utile et pratique pour programmer.
Le probleme c'est que le plus souvent, c'est un sujet qui vient relativement tard dans l'apprentissage de la programmation. Les élèves ont donc appris à s'en servir après des exercices plus ou moins longs où ils s'en passaient (exemple le plus ou moins). Resultat, quand on en cause, ça apparaît comme un truc pas très utile, dont l'utilisation apporte des complications. Et on a l'habitude de faire autrement. Pas motivant, quoi.
Faut dire qu'apprendre avec C, ça n'aide pas, parce que ça oblige à aborder le sujet maudit des pointeurs pour peu qu'on veuille avoir, conceptuellement un passage de paramètres "en entrée sortie". Genre "fonction qui échange deux entiers".
Mais bon, même du bon vieux temps de fortran, pour le problème résoudre une équation du second degré, j'ai jamais vu dans les bouquins un découpage lecture + un sous programme pour chaque niveau de dégénérescence. (A different de zero etc)
Ps enchainement de tests : si on n'a pas découpé, on fait un goto. Ou un do while(false) dont on sort prématurément par des breaks. Ou un truc tordu avec un switch a une seule branche.
Exemple
int r = 0;
switch (0) {
default:
r = comparaison 1;
if (r != 0) break;
r = comparaison 2;
if (r != 0) break;
...
}
La definition exotique de "switch" en C laisse une vaste place à la créativité. Heureusement, on fait généralement croire aux débutants que les breaks sont là pour marquer syntaxiement la fin d'une branche. C'est pour leur bien, c'est mieux qu'ils ne sachent pas la vérité.
- Edité par michelbillaud 28 octobre 2021 à 7:07:34
Un exemple tordu du switch à une branche serait de faire un faux if: switch (valeur) { case 1: case 2: case 3: printf("C'est bon\n"); break; // Syntaxe magique ... default: printf("C'est mauvais\n"); } Je n'ai jamais vu en Fortran une fonction ou subroutine qui affichait des tableaux de dimensions variables. Une fonction pour afficher (comme dans cet exercice) devrait être une des premières qu'on enseignerait.
Le Tout est souvent plus grand que la somme de ses parties.
Je n'ai jamais vu en Fortran une fonction ou subroutine qui affichait des tableaux de dimensions variables.
Bah, si, ça se faisait largement à l'époque. Pour rafraichir mes souvenirs de fortran IV et 77 j'ai fait un exemple.
program hello
integer t1(2, 3)
integer t2(3, 4)
write(*, *) "hello !"
call fill_array(t1, 2, 3)
call fill_array(t2, 3, 4)
write(*, *) "tableau de 2 sur 3"
call print_array(t1, 2, 3)
write(*,*) "tableau de 3 sur 4"
call print_array(t2, 3, 4)
end program hello
C -----------------------------------------------------
subroutine fill_array(tableau, lignes, colonnes)
integer lignes, colonnes
integer tableau(lignes, colonnes)
integer ligne, colonne
do 10, ligne = 1, lignes
do 20, colonne = 1, colonnes
tableau(ligne, colonne) = 100*ligne + colonne
20 continue
10 continue
end
C -----------------------------------------------------
subroutine print_array(tableau, lignes, colonnes)
integer lignes, colonnes
integer tableau(lignes, colonnes)
integer ligne, colonne
do 10, ligne = 1, lignes
write(*, *) (tableau(ligne, colonne), colonne = 1, colonnes)
10 continue
end
avec le compilo gfortran, et en restant compatible fortran 77 (à part les noms qui étaient limités à 6 caractères significatifs en fortran 77, limite poussée à 31 en fortran 90, parce que bon, ça va bien un moment les conneries)
Execution
hello !
tableau de 2 sur 3
101 102 103
201 202 203
tableau de 3 sur 4
101 102 103 104
201 202 203 204
301 302 303 304
les âmes sensibles font défaillir sur la boucle implicite de la ligne 40. et encore je leur ai épargné les formats..
Pour en revenir au découpage de l'eq du 2nd degré, voila l'idée :
C
C résolution équation second degré
C
program equation
call afficher_solutions (1.0, 0.0 ,-4.0)
end program equation
subroutine afficher_solutions (a, b, c)
real a, b, c
if (a .ne. 0.0) then
call afficher_solutions_2 (a, b, c)
else if (b. ne. 0.0) then
call afficher_solutions_1 (b, c)
else
call afficher_solutions_0 (c)
end if
end
C
C équation du 2nd degré non dégénérée
C
subroutine afficher_solutions_2 (a, b, c)
real a, b, c
write(*,*) "TODO, 2nd degré", a, "x^2 + ", b, "x +", c, " = 0"
end
C
C équation du 1er degré non dégénérée
C
subroutine afficher_solutions_1 (b, c)
real b, c
write(*,*) "TODO, 1er degré", b, "x +", c, " = 0"
end
C
C équation triviale
C
subroutine afficher_solutions_0 (c)
real c
if (c .eq. 0.0) then
write (*,*) "tout nombre x est solution"
else
write (*,*) "pas de solution"
end if
end
- Edité par michelbillaud 28 octobre 2021 à 8:44:20
trier un tableau par frequence d'occurence
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
On écrit "j'ai tort", pas "tord" qui est le verbe "tordre" à la 3ème personne de l'indicatif présent
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.