Partage
  • Partager sur Facebook
  • Partager sur Twitter

Exercices tableaux et fonction

fonction sommetableau

    18 juin 2021 à 6:51:04

    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] ...
    • Partager sur Facebook
    • Partager sur Twitter

    Le Tout est souvent plus grand que la somme de ses parties.

      18 juin 2021 à 14:51:31

      Au niveau dénomination, ça donnerai plutôt ça pour s'y retrouver, mais sur le principe ça retrouve bien l'indice du minimum ?

      Sinon, je ne vois pas comment comparer tab[i] à tab[min], je ne sais pas à l'avance l'indice de tab[min] si ?

      • Partager sur Facebook
      • Partager sur Twitter
        18 juin 2021 à 15:30:42

        Ç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;
        }
        • Partager sur Facebook
        • Partager sur Twitter

        Le Tout est souvent plus grand que la somme de ses parties.

          18 juin 2021 à 18:41:07

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



          -
          Edité par michelbillaud 18 juin 2021 à 18:46:21

          • Partager sur Facebook
          • Partager sur Twitter
            18 juin 2021 à 19:52:21

            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.

            • Partager sur Facebook
            • Partager sur Twitter
              18 juin 2021 à 20:02:41

              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.
              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                18 juin 2021 à 21:24:06

                SébastienTellier a écrit:

                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.

                -
                Edité par michelbillaud 18 juin 2021 à 21:29:04

                • Partager sur Facebook
                • Partager sur Twitter
                  18 juin 2021 à 22:25:19

                  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

                  • Partager sur Facebook
                  • Partager sur Twitter
                    20 juin 2021 à 11:42:01

                    Est-ce que j'ai besoin d'une boucle for pour inverser les éléments d'indices a et b ? J'ai l'impression que c'est pas nécessaire sur ce coup si ?

                    Ce code est correct ? Je voyais pas trop comment nommer autrement ma variable sur ce coup-là :

                    void permute(int tab[], int n, int a, int b) {
                    
                        int element_indice_a = 0;
                        element_indice_a = tab[a];
                            tab[a] = tab[b];
                            tab[b] = element_indice_a;
                    }

                    -
                    Edité par SébastienTellier 20 juin 2021 à 11:58:38

                    • Partager sur Facebook
                    • Partager sur Twitter
                      20 juin 2021 à 12:22:46

                      C'est tout à fait ça !

                      La variable où l'on dépose temporairement la valeur de l'élément d'indice a s'appelle souvent "temp" ou quelque chose comme ça.

                      • Partager sur Facebook
                      • Partager sur Twitter
                        20 juin 2021 à 12:26:33

                        SébastienTellier a écrit:

                        Est-ce que j'ai besoin d'une boucle for pour inverser les éléments d'indices a et b ? J'ai l'impression que c'est pas nécessaire sur ce coup si ?

                        Non, c'est inutile !

                        SébastienTellier a écrit:

                        Ce code est correct ? ...

                        Oui, tu aurais pu initialiser element_indice_a directement avec tab[a].

                        Et supprime le paramètre inutile à ta fonction !



                        • Partager sur Facebook
                        • Partager sur Twitter
                          20 juin 2021 à 13:46:40

                          rouloude a écrit:

                          Et supprime le paramètre inutile à ta fonction !

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

                          • Partager sur Facebook
                          • Partager sur Twitter
                            20 juin 2021 à 15:29:53

                            Ce n'est pas dans l'esprit du C, c'est au programmeur a faire attention à ce qu'il fait !



                            • Partager sur Facebook
                            • Partager sur Twitter
                              21 juin 2021 à 21:20:43

                              rouloude a écrit:

                              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.

                              Maintenant j'essaie (vainement pour l'instant lol) de faire la fonction qui met le minimum en première position.

                              • Partager sur Facebook
                              • Partager sur Twitter
                                21 juin 2021 à 22:35:03

                                SébastienTellier a écrit:

                                rouloude a écrit:

                                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) {
                                      |                         ~~~~^



                                • Partager sur Facebook
                                • Partager sur Twitter
                                  22 juin 2021 à 6:10:19

                                  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)

                                  -
                                  Edité par michelbillaud 22 juin 2021 à 6:17:31

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    22 juin 2021 à 16:57:27

                                    Je bloque sur le déplacement du minimum, je vois pas comment je peux faire, avec le code ci-dessous :

                                    void deplaceminimum(int tab[], int n) {
                                    
                                    int i, min_temp = 0;
                                    min_temp = tab[0];
                                    for (i = 0; i < n; i++) {
                                            if (tab[i] < tab[0]){
                                                tab[0] = tab[i];
                                                tab[i] = min_temp;
                                            }
                                    }
                                    }

                                    Dès qu'une valeur inférieur à tab[0] sera rencontré, la condition va s'appliquer et obligatoirement ça "fout la merde"

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      22 juin 2021 à 19:54:20

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

                                      -
                                      Edité par robun 22 juin 2021 à 19:55:07

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        22 juin 2021 à 20:45:20

                                        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.

                                        Edit: typos

                                        -
                                        Edité par White Crow 22 juin 2021 à 20:49:32

                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          23 juin 2021 à 5:06:25

                                          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).
                                          • Partager sur Facebook
                                          • Partager sur Twitter

                                          Le Tout est souvent plus grand que la somme de ses parties.

                                            23 juin 2021 à 13:46:55

                                            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;
                                            }



                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              23 juin 2021 à 15:26:39

                                              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 ...
                                              • Partager sur Facebook
                                              • Partager sur Twitter

                                              Le Tout est souvent plus grand que la somme de ses parties.

                                                23 juin 2021 à 15:33:04

                                                SébastienTellier a écrit:

                                                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));
                                                }



                                                -
                                                Edité par michelbillaud 23 juin 2021 à 15:36:45

                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  23 juin 2021 à 15:49:58

                                                  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;
                                                          }
                                                      }
                                                  }

                                                  • Partager sur Facebook
                                                  • Partager sur Twitter

                                                  Le Tout est souvent plus grand que la somme de ses parties.

                                                    23 juin 2021 à 18:42:03

                                                    PierrotLeFou a écrit:

                                                    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.

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      23 juin 2021 à 19:36:45

                                                      SébastienTellier a écrit:

                                                      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.

                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        23 juin 2021 à 21:59:00

                                                        Attention,

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

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          24 juin 2021 à 2:05:59

                                                          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 …
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter

                                                          Le Tout est souvent plus grand que la somme de ses parties.

                                                            24 juin 2021 à 5:47:55

                                                            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é)

                                                            -
                                                            Edité par michelbillaud 26 juin 2021 à 16:53:08

                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              24 juin 2021 à 6:39:51

                                                              Et on peut ajouter
                                                              jusqu'où va-t-on comme ça?
                                                              Quelle sera la longueur du dernier tableau?
                                                              Quel sera l'indice du début du dernier tableau?
                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              Le Tout est souvent plus grand que la somme de ses parties.

                                                              Exercices tableaux et fonction

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              • Editeur
                                                              • Markdown