Et puisque tu cherches l'indice correspondant à la valeur minimum, pourquoi avoir une variable pour cette valeur minimum? Tu peux comparer tab[i] et tab[min] ...
Le Tout est souvent plus grand que la somme de ses parties.
Ça pourrait avoir l'air de ceci: int indexMinimum(int tableau[], int taille) { int m = 0; for(int i=1; i<taille; i++) if(tableau[i] < tableau[m]) m = i; return m; }
Le Tout est souvent plus grand que la somme de ses parties.
> mais sur le principe ça retrouve bien l'indice du minimum ?
j'ai peut être l'air de radoter, mais on se simplifie les choses en nommant correctement les choses.
> Sinon, je ne vois pas comment comparer tab[i] à tab[min], je ne sais pas à l'avance l'indice de tab[min] si ?
Pour comparer, c'est toujours avec if (tab[i] < tab[min]) :-)
Ce qu'on appelle min ici, c'est une valeur provisoire. Un résultat partiel.
Quand on fait la somme des éléments d'un tableau
int somme_tableau(int tableau[], int taille) {
int somme = 0;
for (int i = 0; i < taille; i++) {
somme = somme + tableau[i];
}
return somme;
}
dans la boucle, la variable somme contient une somme partielle, la somme des éléments qu'on a déjà vus, ceux qui ont un indice entre 0 et i-i.
C'est pas qu'on ne la connait pas à l'avance: on est en train de calculer la somme totale en cumulant dans la variable (somme partielle) tous les éléments du tableau, un par un. Quand on les a tous cumulés, ça nous fait la somme totale.
Même chose avec le code
int indice_minimum(int tableau[], int taille) {
int indice = 0;
for (int i = 1; i < taille; i++) {
if (tableau[i] < tableau[indice]) {
indice = i;
}
}
return indice;
}
la variable indice contient un résultat partiel : l'indice du plus petit élément qu'on a trouvé PARMI CEUX QU'ON A VUS POUR L'INSTANT.
De même que si on cherche la valeur minimum
int valeur_minimum(int tableau[], int taille) {
int valeur = tableau[0];
for (int i = 1; i < taille; i++) {
if (tableau[i] < valeur) {
valeur = tableau[i];
}
}
return valeur;
}
Comme tu vois, tous ces algorithmes ont un air de famille, ils sont construits sur un même schéma : on a une variable qui contient un résultat partiel, et à chaque étape on "l'améliore" en prenant en compte un élément supplémentaire du tableau. Quand on les a tous vus, on tient le résultat.
Merci pour les réponses et explications. Après je me dis que quand on apprends à résoudre des équations (par exemple), on passe parfois par 4 ou 5 lignes de calculs avant le résultat alors qu'avec l'expérience/la compréhension etc..., plus tard, on passera direct au résultat.
Je veux pas dire par là que ce que j'ai fait est bien ou pas bien, mais en tous cas je me dis que c'est déjà un progrès vu que je n'y arrivais pas du tout encore hier.
Si je peux me permettre une comparaison. Je suppose que tu as déjà utilisé une calculette pour additionner des nombres. D'abord, je fais le CLEAR pour mettre à 0. J'entre le premier chiffre et je fais '+' J'entre le suivantet je fais encore '+' ... j'entre le dernier et je fais '=' L'ordinateur n'est pas plus intelligent que la calculette, il est seulement plus puissant. La variable 'somme' de la fonction joue le même rôle que le registre de la calculette.
Le Tout est souvent plus grand que la somme de ses parties.
Je veux pas dire par là que ce que j'ai fait est bien ou pas bien, mais en tous cas je me dis que c'est déjà un progrès vu que je n'y arrivais pas du tout encore hier.
Y pas de raisons. La programmation c'est un monde étrange, faut du temps pour se familiariser.
Au bout d'un moment on a un déclic, et on se dit qu'en fait c'est simple et on se demande pourquoi on y voyait des complications. Mais c'est pas le premier jour, ça prend quand même 2 ou 3 mois en y bossant régulièrement.
Effectivement, d'ailleurs dès demain je regarderai les autres exercices que vous m'avez proposé et ensuite faudra aussi que je reprenne le cours, j'ai arrêté le temps de comprendre un peu mieux le chapitre sur les tableaux
- Edité par SébastienTellier 19 juin 2021 à 12:16:21
C'est de ma faute, c'est moi qui ai donné le prototype. Ou alors on le rend utile en ajoutant un test. Quelque chose du genre : si a et b ne sont pas des indices valides, on ne permute rien. Dans ce cas il faudrait que la fonction retourne un code d'erreur. Mais je ne sais pas si ce serait vraiment intéressant de s'entraîner à manipuler les tableaux en ajoutant ce genre de vérification. (Si cette fonction doit servir pour un tri et si le tri est écrit correctement, les indices seront forcément valides.)
Ce n'est pas dans l'esprit du C, c'est au programmeur a faire attention à ce qu'il fait !
J'avoue que si j'avais vraiment fait un peu + attention j'aurai sûrement pu voir le paramètre inutile.
[...]
Ce qu'il faut surtout faire est d'activer les warnings … ça aide !
Par exemple avec ta fonction :
$ gcc -Wall -Wextra -c p.c
p.c: In function ‘permute’:
p.c:1:29: warning: unused parameter ‘n’ [-Wunused-parameter]
1 | void permute(int tab[], int n, int a, int b) {
| ~~~~^
Après, le parametre est techniquement inutile, mais il y a un autre aspect : quand on réalise une série de fonctions qui agissent sur des objets de même nature, c'est intéressant que les paramètres soient fournis dans un ordre standard. Ca simplifie la vie du programmeur.
Par exemple, ici, on met le tableau d'abord, puis la taille (ça se discute mais bon c'est le choix qui a été fait). Ca serait mal vu que certaines fonctions soient dans l'ordre inverse.
Du coup si on met la "régularité" comme critère important de qualité de l'API (ensemble de fonctions, application programming interface), on peut s'autoriser à avoir des paramètres inutiles.
Pour éviter que le compilateur couine, la solution traditionnelle est de faire semblant de les utiliser avec un "transtypage" à void.
void permuter(int t[], int n, int a, int b)
{
(void) n; // UNUSED
int tmp = t[a];
...
}
Plus tard, quand on sera grands, il y aura un attribut qui signalera notre intention (Ce paramètre n'est pas utilisé) et demandera au compilateur de s'en assurer (dans le code, aucune utilisation sauf éventuellement pour le passer en paramètre à une fonction qui n'en fait rien non plus)
Ps les paramètres inutilisés, ça arrive souvent pour les fonctions qu'on passe en paramètres, à une autre fonction ("callbacks", par exemple)
Le minimum, on ne le connaît qu'à la fin. Donc il faut écrire une boucle qui recherche le minimum et, ensuite, quand on est sorti de la boucle, faire l'échange.
Ou alors il y a la méthode du feignant : appeler la fonction qui recherche l'indice du minimum et utiliser cet indice directement. (Un bon programmeur est un programmeur feignant.)
Il y a quand même de nombreuses pages pour le tri …
Si on part de l'algorithme (en pseudo français) qui est relativement simple :
Algo Trier( tableau, taille_tableau) :
pour début de 1 à taille_tableau-1 faire
indice_du_minimum = rechercher_minimum(tableau, début, taille_tableau)
échanger(tableau, indice_du_minimum, début)
fin pour
Fin algo
On a deux fonctions à écrire : rechercher_minimum et échanger. Ensuite le tri est plié. C'est surtout ce squelette qu'il faut comprendre avant d'avancer et d'écrire du code.
Il faut comprendre que l'algo de White Crow n'est que le début. Ce que ça va donner est uniquement de placer le plus petit de "tout" le tableau en première position. Question: comment je fais pour placer le deuxième plus petirt après le plus petit? Ça va te prendre une autre boucle pour recommencer à partir de la deuxième position ... Autre question: comment j'échange deux valeurs dans le tableau? Ha oui! je tiens le minimum dans ma main et je place la seconde à sa place et je place ce qu'il y a dans ma main à la place de la seconde. C'est clair, non? Non, pour échanger deux cases, il faut pouvoir en placer une dans une case temporaire (une variable). Tu place la première dans la temporaire (pour la sauver). Tu place la seconde dans la première (les deux contiennent la même valeur). Et tu place la temporaire dans la seconde (la temporaire contient l'ancienne valeur de la première).
Le Tout est souvent plus grand que la somme de ses parties.
Je peux l'écrire comme ça, ça m'a l'air de fonctionner, mais ça m'a l'air bien compliqué, sachant que même le code pour trier entièrement le tableau étaient plus court :
void deplaceminimum(int tab[], int n) {
int i, IndiceMinimum = 0;
int premier_element = tab[0];
for (i = 0; i < n; i++) {
if (tab[i] < tab[IndiceMinimum]) {
IndiceMinimum = i;
}
}
tab[0] = tab[IndiceMinimum];
tab[IndiceMinimum] = premier_element;
}
Pourquoi, tu t'attends a tout écrire dans 3 lignes de code? Tu as fait le plus gros. Commence ta boucle avec l'indice 1, sinon tu compares le premier avec le premier ...
Le Tout est souvent plus grand que la somme de ses parties.
Je peux l'écrire comme ça, ça m'a l'air de fonctionner, mais ça m'a l'air bien compliqué, sachant que même le code pour trier entièrement le tableau étaient plus court :
void deplaceminimum(int tab[], int n) {
int i, IndiceMinimum = 0;
int premier_element = tab[0];
for (i = 0; i < n; i++) {
if (tab[i] < tab[IndiceMinimum]) {
IndiceMinimum = i;
}
}
tab[0] = tab[IndiceMinimum];
tab[IndiceMinimum] = premier_element;
}
La complication vient de toi.
Ca serait plus court si tu appelais la fonction qui cherche l'indice du minimum, au lieu de recopier son code.
void deplaceminimum(int tab[], int n) {
int IndiceMinimum = indice_du_minimum(tab, n);
tab[0] = tab[IndiceMinimum];
tab[IndiceMinimum] = premier_element;
}
et puis tu pourrais même permuter
void deplaceminimum(int tab[], int n) {
int i = indice_du_minimum(tab, n);
permuter(tab, n, 0, i);
}
ou encore plus court
void deplaceminimum(int tab[], int n) {
permuter(tab, n, 0, indice_du_minimum(tab, n));
}
Le tri par sélection complet donne ceci, est-ce si long? (fais un copier-coller ppour l'indentation, c'est la variante la plus rapide de ce tri) - // Tri par sélection. void triSelection(int tableau[], int taille) { for(int i=0; i<taille-1; i++) { int minimum=tableau[i]; int m=i; for(int j=i+1; j<taille; j++) { if(tableau[j] < minimum) { minimum=tableau[j]; m=j; } } if(m > i) { int temp=tableau[i]; tableau[i]=minimum; tableau[m]=temp; } } }
Le Tout est souvent plus grand que la somme de ses parties.
Pourquoi, tu t'attends a tout écrire dans 3 lignes de code? Tu as fait le plus gros. Commence ta boucle avec l'indice 1, sinon tu compares le premier avec le premier ...
Pas du tout, mais il semble logique que trier tous les éléments du tableaux demandent plus de code que de simplement inverser le minimum avec le premier élément. Ce qui visiblement n'est pas le cas.
Après je n'ai peut-être pas encore la bonne logique à ce sujet, il est possible que paradoxalement, trier tous les élément demandent moins de lignes de code, visiblement c'est le cas d'ailleurs si je compare à l'algorithme de tri que j'avais trouvé sur un site.
Pas du tout, mais il semble logique que trier tous les éléments du tableaux demandent plus de code que de simplement inverser le minimum avec le premier élément. Ce qui visiblement n'est pas le cas.
Ah si, trier demande plus d'instructions. Si tu as l'impression du contraire, c'est peut-être que tu as vu un programme de tri incluant des fonctions ? Dans ce cas il faut ajouter les instructions des fonctions.
ce n'est pas parce qu'un code source est plus court que le code exécutable le sera aussi et inversement ;
ce n'est pas parce qu'un code est plus court qu'il est plus rapide qu'un code plus long (ex. insertion sort vs quick sort) ;
La notion qui permet d'«estimer le coût en temps et espace de travail» d'un algorithme et de comparer les algorithmes entre eux est la la notion de complexité algorithmique.
Ici, il est question de la compréhension d'un algorithme et de le coder au mieux de son expérience. Et je n'arrive pas à saisir ce que SébastienTellier ne saisit pas, si je peux dire …
Le Tout est souvent plus grand que la somme de ses parties.
Il constate que la recherche du minimum et l'échange avec la première position seulement, ça ne trie pas le tableau.
C'étaient des sous-problèmes qui interviennent dans le tri, ça fait des exercices, mais ça ne suffit pas à faire le job.
Qu'il faut maintenant répéter l'opération pour placer le second plus petit en tableau[1], puis le troisième dans tableau[2] etc.
Et pour cela, on a besoin de généraliser légèrement les opérations. Chercher l'indice du minimum dans un tableau A PARTIR D'UNE CERTAINE POSITION (= le bout du tableau qui n'a pas encore été trié)
× 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.
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.