Jean-Jacques BOURDIN

Université Paris 8
Dépt. Programmation et Informatique Fondamentale
2, rue de la Liberté
93526 Saint-Denis Cedex
FRANCE


Programmation Impérative
Imperative Programming

Spring 2024


Tous les exercices

Overview

Ch I) Let's try!

Ch II) Easy C

    II.A) Variables, Expressions, Types, Instructions

    II.A) Operators

    II.B) Control Flow

    II.C) Data Structures

    II.D) Compilation

Ch III) C Addresses

    III.A) Déjà vu

    III.B) Arrays

    III.D) Lists

    III.D) Trees

    III.C) Functions' Pointeers

Ch IV) C more than that

 

 

 

 


Ch III) Adresses C


    III.A) Principles / Principes, Rappels

A variable is a set of three things: a name, a type and a location.
It is in this location that one can find the value of the variable. The address is known by the operator &.

Une variable est un triplet < nom, type, emplacement>. C'est à cet emplacement que, selon le type, on trouve la valeur. On peut connaître l'emplacement, l'adresse, de la variable "a" en utilisant l'opérateur & :
void voirou1 () {
  int i, j;
  printf("i est en %u, j est en %u\n", (int)&i, (int)&j);
}

One may also set this adress into a new variable, a "pointer". The content of such a variable is available, and the content of the pointed variable can be found with the unary operator *.
On peut aussi mettre cette adresse dans une variable spéciale qui contient des adresses, un pointeur. On peut aussi savoir ce qu'il y a à une certaine adresse avec l'opérateur unaire *.
void voirou () {
  int *pi, *pj;
  int i, j;

  printf("i est en %d, j est en %u\n",(int) &i,(int) &j);
  pi = & i;
  pj = & j;
  i  = 7;
  j  = 9;
  printf("En %u il y a %d\n", (int) pi, * pi);
  printf("En %u il y a %d\n", (int) &j, j);  
}

On peut se servir des adresses pour modifier le contenu d'une variable extérieure.
void iv (int * pa, int * pb) {
   * pa = * pa + * pb;
   * pb = * pa - * pb;
   * pa = * pa - * pb;
}
int main () {
   int a, v;
   a = 5;
   v = 8;
   voirou1();
   voirou();
   printf("a = %d\t v = %d\n",a,v);
   iv (&a, &v);
   printf("a = %d\t v = %d\n",a,v);
}
/* dhcp13.ai.univ-paris8.fr: a.out
a = 5	 v = 8
a = 8	 v = 5
*/

Ici, les variables et leurs adresses :
      nom  adresse contenus
main   a   400     5    puis 13        puis 8
main   v   404     8            puis 5
iv     pa  408     400    
iv     pb  416     404
Amusant, non ?
/* une autre version */
#include <stdio.h>

void nrut (int * px, int * py) {
  * px = * px + * py;
  * py = * px - * py;
  * px = * px - * py;
}
void lookatit (int n) {
  int x, y;
  int * px, * py; /* adresses de int */

  x  = n; 
  y  = 3; 
  px  = & x; 
  py  = & y;
  printf("adresses de x %p et y %p\n",px, py);
  printf("Avant : valeurs de x %d et y %d\n",x, y);
  nrut(px,py);
  printf("Avant : valeurs de x %d et y %d\n",x, y);
}
int main () {
  lookatit(5);
}
/*
adresses de x 0x7ff7b32b7768 et y 0x7ff7b32b7764
Avant : valeurs de x 5 et y 3
Apres : valeurs de x 3 et y 5
*/
Voici un autre exemple, que vous reconnaîtrez aisément :
/* Fait par JJ B en 2010 */

typedef int * pint;

void fct (int nb, int rg, pint a, pint b) {
  if (nb > rg) {
    *a = *a + *b;
    *b = *a - *b;
    fct (nb, rg + 1, a, b);
  }
}
main () {
  int i, n, a, b;

  n = 10;
  for (i = 0; i <= n; i++) {
    a = 1;
    b = 1;
    fct (i, 0, &a, &b);
    printf("%d => %d\n", i, b);
  }
}

 

 

    III.B) Arrays and pointers / Vecteurs et Tableaux

  1. Retour
    What is an array? Nothing else than a pointer.
    Qu'est-ce qu'un tableau ? Un pointeur ! On peut parcourir un tableau, case à case, par un pointeur :
    /* Fait par JJ B */
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct vecteur {
      int nbe;
      float tab [100];
    } vecteur_t;
    
    typedef float * pfloat;
    
    float somv (vecteur_t v) {
      int i;
      float som;
      pfloat p;
      p = v.tab;
      som = 0;
      for (i = 0; i < v.nbe; i++) {
        som = som + *p;
        p ++;
      }
      return som;
    }
    
    On suppose que le vecteur a été défini par ailleurs. Voici une illustration du fonctionnement de cette fonction :

    Il vous reste à reprendre quelques exercices faits avec des vecteurs, mais cette fois, en utilisant les pointeurs.

    Exemple avec un vecteur de nombre complexes

    Nous complétons la structure de nombres complexes présentée sur les vecteurs de structures. Ceci serait bien placé dans un fichier Header.
    #include <stdio.h>
    #include <stdlib.h>
    
    
    typedef struct compl {
       float r; // représente la partie réelle
       float i; // représente la partie imaginaire
    } compl_t;
    
    typedef struct vecc {
      int nbc;
      compl_t vc [100];
      float vm [100]; /* le module pour chacun */
    } vecc vecc_t;
    
    vecc_t creevec (int);
    vecc_t calculmodule (vecc_t);
    void affvec (vecc_t);
    int mini (vecc_t);
    	    
    
    Nous donnons trois des fonctions importantes : main, creevec et module (qui calcule le carré du module d'un nombre complexe).

    Les autres fonctions sont à écrire par vous-mêmes.

    #include "comp.h"
    
    int main () {
      vecc_t v, w;
      int n, i;
      float mod, modmoy;
    
      n = 20;
      v = creevec(n);
      printf("Avant le module \n");
      affvec (v);
      v = calculmodule(v);
      printf("Avant le module \n");
      affvec (v);
      i = mini (v);
      printf("le plus petit est le numéro %2d \t %f i%f et son module %f\n", i, v.vc[i].r, v.vc[i].i, v.vm[i]);
    }
    
    vecc_t creevec (int nb) {
      float reel, imag, eps;
      int i;
      vecc_t v;
    
      v.nbc = nb;
      reel = 1.0;
      imag = 2.0;
      eps = 0.13;
      for (i = 0; i < nb; i++) {
        v.vc[i].r = reel;
        v.vc[i].i = imag;
        reel += eps;
        imag -= eps;
        if (reel > 2.0)
          eps = 0.05 - eps;
      }
      return v;
    }
    float lemodule (compl_t c) {
      return c.r * c.r + c.i * c.i;
    }
    
    Qui donne à l‘exécution :
    White.local: a.out
    Avant le module 
     0 : 1.000000 + i 2.000000 module 0.000000
     1 : 1.130000 + i 1.870000 module 0.000000
     2 : 1.260000 + i 1.740000 module 0.000000
     3 : 1.390000 + i 1.610000 module 0.000000
     4 : 1.520000 + i 1.480000 module 0.000000
     5 : 1.650000 + i 1.350000 module 0.000000
     6 : 1.780000 + i 1.220000 module 0.000000
     7 : 1.910000 + i 1.090000 module 0.000000
     8 : 2.040000 + i 0.960000 module 0.000000
     9 : 1.960000 + i 1.040000 module 0.000000
    10 : 1.880000 + i 1.120000 module 0.000000
    11 : 1.800000 + i 1.200000 module 0.000000
    12 : 1.720000 + i 1.280000 module 0.000000
    13 : 1.640000 + i 1.360000 module 0.000000
    14 : 1.560000 + i 1.440000 module 0.000000
    15 : 1.480000 + i 1.520000 module 0.000000
    16 : 1.400000 + i 1.600000 module 0.000000
    17 : 1.320000 + i 1.680000 module 0.000000
    18 : 1.240000 + i 1.760000 module 0.000000
    19 : 1.159999 + i 1.840001 module 0.000000
    Avant le module 
     0 : 1.000000 + i 2.000000 module 5.000000
     1 : 1.130000 + i 1.870000 module 4.773800
     2 : 1.260000 + i 1.740000 module 4.615200
     3 : 1.390000 + i 1.610000 module 4.524200
     4 : 1.520000 + i 1.480000 module 4.500800
     5 : 1.650000 + i 1.350000 module 4.545000
     6 : 1.780000 + i 1.220000 module 4.656800
     7 : 1.910000 + i 1.090000 module 4.836200
     8 : 2.040000 + i 0.960000 module 5.083200
     9 : 1.960000 + i 1.040000 module 4.923200
    10 : 1.880000 + i 1.120000 module 4.788800
    11 : 1.800000 + i 1.200000 module 4.680000
    12 : 1.720000 + i 1.280000 module 4.596800
    13 : 1.640000 + i 1.360000 module 4.539200
    14 : 1.560000 + i 1.440000 module 4.507200
    15 : 1.480000 + i 1.520000 module 4.500800
    16 : 1.400000 + i 1.600000 module 4.520000
    17 : 1.320000 + i 1.680000 module 4.564800
    18 : 1.240000 + i 1.760000 module 4.635201
    19 : 1.159999 + i 1.840001 module 4.731201
    le plus petit est le numéro  4 	 1.520000 i1.480000 et son module 4.500800
    
    Bien évidemment il aura fallu créer la fonction qui calcule le module de tous les complexes du vecteur.

     

  2. Dynamic arrays
    Tableaux dynamiques
  3. We oversize our arrays, is it such a good idea?
    Jusqu'à présent, vous avez un problème avec la taille des tableaux et vecteurs, ce n'est plus la peine grâce aux tableaux dynamiques.
    	  #include<stdio.h>
    	  #include<stdlib.h>
    	  #include<assert.h>
    	  typedef int * pint;
    typedef int table [100];
    
    void fcttab (int nb, table t) {
      int i;
      pint p1, p2, p3;
      p3 = t;
      p2 = t + 1;
      p1 = t + 2;
      
      *p3 = 1;
      *p2 = 1;
      for (i = 2; i <= nb; i+=1) {
    	*p1 = *p2 + *p3;
    	p3 = p2;
    	p2 = p1;
    	p1+= 1;
      }
    }
    void seetab (table t, int nb) {
      pint p;
    
      p = t;
      while (nb > 0) {
    	printf("%d\t", *p);
    	p++;
    	nb--;
      }
      printf("\n");
    }
    main () {
      table tt;
      pint pt;
      int n, nbele;
    
      n = 18;
      nbele = n + 1;
    /* ici, la methode classique ou tt est un tableau */
      fcttab(n, tt);
      seetab(tt, nbele);
      n = 10;
      nbele = n + 1;
    /* la, la methode dynamique de "creation" d'un tableau */
      pt = (pint) malloc ((size_t) (nbele * sizeof(int)));
      assert(pt);
      fcttab(n, pt);
      seetab(pt, nbele);
      free(pt);
    /* c'est plus joli, plus souple, plus dynamique */
    }
    

  4. Exercices

    Refaire toutes les fonctions déjà vues sur les tableaux mais avec des tableaux dynamiques.

  5.  

     

     

    Voici un exemple pour des tableaux d'altitude. Pour une carte, ici, un tableau carré, chaque case (une petite surface du terrain) contient son altitude. Voici l'ensemble du programme qui crée un tableau d'altitudes (la topographie d'un terrain) et l'affiche.

    Let's see some new types to work on the altitude field.
    Créons d'abord les types qui vont nous servir :
    typedef unsigned int uint;
    typedef float * tabalt ;
    typedef struct tableau {
      tabalt t;
      unsigned int nbc;
      unsigned int nbl;
    } tableau;
    

    This type includes the length in columns and lines of the array and the adress of the values.
    Comme vous le voyez, la structure tableau contient maintenant aussi ses dimensions. On peut maintenant créer un tel tableau :
    tableau creetableau (uint nbc, uint nbl) {
      tableau t;
      t.nbc = nbc;
      t.nbl = nbl;
      t.t = (tabalt) malloc ((size_t) (nbc * nbl * sizeof(float)));
      return t;
    }
    

    Once it's created, it is easy to fill the array with values.
    Une fois qu'il sera créé, on peut mettre une valeur dans une des cases, ou récupérer le contenu de l'une des cases :
    void puttab (tableau t, uint i, uint j, float amettre) {
      if (i < t.nbc && j < t.nbl) {
    	*(t.t + i + j * t.nbc) = amettre;
      }
    }
    float valtab (tableau t, uint i, uint j) {
      if (i < t.nbc && j < t.nbl) {
    	return *(t.t + i + j * t.nbc);
      }
      return -1.0;
    }
    

    Il ne reste plus qu'à remplir systématiquement le tableau avec les mêmes valeurs que dans l'exemple donné précédemment :
    void remplirtab (tableau t) {
      uint i, j;
      float val;
    
      for (i = 0; i < t.nbc; i++) 
    	for (j = 0; j < t.nbl; j++) {
    	  val = (float) (30 * i + 20 * i * j + 15 * j);
    	  while (val > 2000.0)
    		val = val - 2000.0;
    	  if (val > 1000.0)
    		val = 2000.0 - val;
    	  puttab(t, i, j, val);
    	}
    }
    

    Puis être en mesure d'afficher toutes les cases du tableau :
    void voirtab (tableau t) {
      uint i, j;
      for (j = 0; j < t.nbl; j++) {
    	printf  ("%6d", j);
      }
      printf("\n");
      for (i = 0; i < t.nbc; i++) {
    	printf ("%4d |", i);
    	for (j = 0; j < t.nbl; j++) {
    	  printf ("%6.2f ", valtab(t, i, j));
    	}
    	printf("\n");
      }
    }
    

    Une fonction main pour faire fonctionner tout cela et le tour est joué.
    int main () {
      uint sx, sy;
      tableau t;
      sx = 10;
      sy = 10;
      t = creetableau (sx, sy);
      remplirtab (t);
      voirtab(t);
    }
    
    Voici un jeu d'essais :
             0     1      2      3      4      5      6      7      8      9
       0 |  0.00  15.00  30.00  45.00  60.00  75.00  90.00 105.00 120.00 135.00 
       1 | 30.00  65.00 100.00 135.00 170.00 205.00 240.00 275.00 310.00 345.00 
       2 | 60.00 115.00 170.00 225.00 280.00 335.00 390.00 445.00 500.00 555.00 
       3 | 90.00 165.00 240.00 315.00 390.00 465.00 540.00 615.00 690.00 765.00 
       4 |120.00 215.00 310.00 405.00 500.00 595.00 690.00 785.00 880.00 975.00 
       5 |150.00 265.00 380.00 495.00 610.00 725.00 840.00 955.00 930.00 815.00 
       6 |180.00 315.00 450.00 585.00 720.00 855.00 990.00 875.00 740.00 605.00 
       7 |210.00 365.00 520.00 675.00 830.00 985.00 860.00 705.00 550.00 395.00 
       8 |240.00 415.00 590.00 765.00 940.00 885.00 710.00 535.00 360.00 185.00 
       9 |270.00 465.00 660.00 855.00 950.00 755.00 560.00 365.00 170.00  25.00 
    
    

    Avec ce tableau, il faut faire quelques fonctions.
    1. pour deux points voisins, (i1,j1) et (i2,j2) donner le dénivelé entre les deux.
    2. pour deux points de la même horizontale, donner la somme des dénivelés positifs entre eux.
    3. pour deux points de la même verticale, donner la somme des dénivelés positifs entre eux.
    4. pour deux points de la même verticale, donner la somme des dénivelés positifs et la somme des dénivelés négatifs entre eux. (utilisation d'une structure ad hoc).
    5. pour deux points donnés, calculer les dénivelés positifs et négatifs entre eux, selon la droite qui les joint.

 

    III.D) Listes Chaînées

  1. Lisp like lists
    Liste Lisp

    Hereafter is a function building a list of n numbers. It's written in scheme, you'll have to translate it.

    Voici une fonction qui construit une liste de n nombres entiers. Elle est en Lisp, il faut donc la transcrire.

    (define (creerl n)
        (if (< n 1)
             ‘(0)
             (cons n (creerl (- n 1)))))
    

  2. Type definition
    Définition des types
    typedef struct cell * liste_t;
    typedef struct cell {
      float obj;
      struct cell * suiv;
    } cell_t;
    

    Here you see that a list is only the adress of a structure.

    Où on voit que la liste est en fait uniquement l'adresse d'une structure qui contient une valeur et une liste.

  3. fonctions simples
    int estvide (liste_t l) {
      if (l == (liste_t) 0) {
        return 1;
      }
      return 0;
    }
    int estnonvide (liste_t l) {
      if (l == (liste_t) 0) {
        return 0;
      }
      return 1;
    }
    
  4. La somme des éléments
    float soml (liste_t l) {
      if (estvide(l)) {
        return 0.0;
      }
      return (*l).obj + soml((*l).suiv);
    }
    
  5. Le nombre d‘éléments
    int howmany (liste_t l) {
      if (estvide(l)) {
        return 0;
      }
      return 1 + howmany ((*l).suiv);
    }
    
  6. La construction
    liste_t cons (int nb, liste_t l) {
      liste_t new;
      new = (liste_t) malloc (sizeof(cell_t));
      assert(new);
      (*new).nb = nb;
      (*new).nxt = l;
      return new;
    }
    liste_t creercours (int nb) {
       liste l;
       int i;
       float x;
       x = 0.1;
       l = (liste_t) 0;;
       while (nb--) {
          l = cons (x, l);
          x += 0.15;
          if (x > 0.5)
             x -= 0.45;
       }
       return l;
    }
    liste_t creeriter (int nb) {
      liste_t debut;
      int i, j, k, t;
      j = 13;
      k = 21;
      debut = (liste_t) 0;
      for (i = 0; i < nb; i++) {
        debut = cons (j, debut);
        t = (j + k) % 31;
        k = j;
        j = t;
      }
      return debut;
    }
    		  
  7. Trois fonctions d‘affichage
    void affl (liste_t l) {
      if (estvide (l)) {
        printf("\n");
      }
      else {
        printf("%5.2f ", (*l).obj);
        affl ((*l).suiv);
      }
    }
    
    Notons que (*l).nxt s‘écrit aussi l->nxt, la flèche, ici "-" et ">", est un nouvel opérateur qui remplace une écriture un peu longue.
    void affll (liste_t l) {
      if (estvide (l)) {
        printf("\n");
      }
      else {
        printf("%5.2f ", l->obj);
        affll (l->suiv);
      }
    }
    void affw (liste_t l) {
      while (estnonvide (l)) {
        printf("%5.2f ", l->obj);
        l = l->suiv;
      }
      printf("\n");
    }
    
    Des entêtes à inclure :
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    La fonction main :
    int main () {
      liste_t l;
      int nb, s;
      nb = 10;
      l = creer(nb);
      affw(l);
      s = soml(l);
      printf("Total : %d\n", s);
      s = howmany(l);
      printf("Il y a %d elements\n", s);
    }
    
  8. Liste d‘exercices à faire.
    1. Trouver le plus grand élément.
    2. Afficher les éléments dans l‘ordre inverse.
    3. Mettre les éléments de la liste en ordre inverse. (Attention, il n‘y a pas besoin de malloc pour faire cette fonction).
    4. Fabriquer une liste avec les n premiers entiers (dans l‘ordre décroissant).
    5. Faire la somme des éléments d‘une liste.
    6. Faire la somme des éléments plus petits que 50 d‘une liste.
    7. Faire la moyenne des éléments d‘une liste.
    8. Enlever le premier élément d‘une liste.
    9. Enlever le dernier élément d‘une liste.
    10. Fonction de concaténation de deux listes.
    11. Dans une liste rangée, insérer une cellule à sa place.
    12. Faire le tri d‘une liste, par insertion.
    13. Trouver le médian des éléments d‘une liste.
    14. Fabriquer une liste des carrés de tous les éléments d‘une autre liste passée en paramètre.
    Exemple de solution
    int plusgrandliste (liste_t l, int candidat) {
       if (l) {
          if (l->nb > candidat)
             return plusgrandliste (l->next, l->nb);
          return plusgrandliste (l->next, candidat);
          
       }
       return candidat; /* il n‘y a plus d‘autre possible*/
    }
    int plusgrandl (liste_t l) {
       if (l)
          return plusgrandliste (l->next, l->nb);
       return INT_MIN; /* impose d‘avoir inclus limits.h */
    }
    
    Ou encore
    int plusgrandliter (liste_t l) {
       int plgd;
       liste_t crt, ptrplgd;
       if (! l)
          return INT_MIN; /* il faut avoir inclus limits.h */
       ptrplgd = l;
       plgd = ptrplgd->nb;
       crt = l->nxt;
       while (crt) {
          if (crt->nb > plgd) {
             plgd = crt->nb;
             ptrplgd = crt;
          }
          crt = crt->nxt;
       }
       return plgd;
    }
    

     

  9. Inversion d‘une liste.
  10. Inversion par la méthode PG/DG.
    (define (re l)
        (ifn (cdr l) l
             (cons (car (re (cdr l)))
                   (re (cons (car l)
                             (re (cdr (re (cdr l)))))))))
    

Quelques solutions vues en cours