exam1/ExamenAlgo1correction.c

   1 /******************************************************************************/
   2 /*              examen algo I : correction et implantation                    */
   3 /******************************************************************************/
   4
   5 /*
   6 1)
   7 appel mystere(6 9 4 8 12 , 2)
   8 T[2]=4 T[3]=8
   9 T[2]=4 <= T[3]=8 donc retourner appel recursif avec k=3
  10         appel mystere(6 9 4 8 12 , 3)
  11         T[3]=8 T[4]=12
  12         T[3]=8 <= T[4]=12 donc retourner appel recursif avec k=4
  13                 appel mystere(6 9 4 8 12 , 4)
  14                 k=4 et n-1=4 donc retourner VRAI
  15 reponse de mystere(6 9 4 8 12 , 2) = Vrai
  16
  17 2)
  18 appel mystere(6 9 4 8 12 , 0)
  19 T[0]=6 T[1]=9
  20 T[0]=6 <= T[1]=9 donc retourner appel recursif avec k=1
  21         appel mystere(6 9 4 8 12 , 1)
  22         T[1]=9 T[2]=4
  23         T[1]=9 > T[2]=4 donc retourner FAUX
  24 reponse de appel mystere(6 9 4 8 12 , 0) = Faux
  25
  26 3)
  27 La fonction mystere(t, k) retourne Vrai si la suite d'entiers contenue dans
  28 le tableau t a partir de l'indice k est croissante et retourne Faux sinon.
  29
  30 4)
  31 Le pire des cas correspond a l'appel mystere(t,k) pour un tableau croissant
  32 a partir de l’indice k. Il y a dans ce cas n-k appels recursifs en comptant
  33 l'appel initial.
  34
  35 5) voir, plus bas, la fonction estDans(int *T, int x, int k, int n) implantant l'algorithme.
  36 */
  37
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41
  42
  43 void affichertab(int *T, int taille)
  44 {
  45     int i;
  46     for (i = 0; i < taille; i++) {
  47         printf("%d ", T[i]);
  48     }
  49 }
  50
  51
  52 int mystere(int *T, int k, int n, int coltab)
  53 {
  54     int i = 0;
  55     for (i = 0; i < coltab; i++)
  56         printf("\t");
  57     printf("appel mystere(");
  58     affichertab(T, n);
  59     printf(", %d)\n", k);
  60
  61     if (k == n - 1) {
  62         for (i = 0; i < coltab; i++)
  63             printf("\t");
  64         printf("k=%d et n-1=%d donc retourner VRAI\n", k, n - 1);
  65         return 1;
  66     }
  67
  68     for (i = 0; i < coltab; i++)
  69         printf("\t");
  70     printf("T[%d]=%d T[%d]=%d\n", k, T[k], k + 1, T[k + 1]);
  71
  72     if (T[k] > T[k + 1]) {
  73         for (i = 0; i < coltab; i++)
  74             printf("\t");
  75         printf("T[%d]=%d > T[%d]=%d donc retourner FAUX\n", k, T[k], k + 1,
  76                T[k + 1]);
  77         return 0;
  78     }
  79
  80     for (i = 0; i < coltab; i++)
  81         printf("\t");
  82     printf
  83         ("T[%d]=%d <= T[%d]=%d donc retourner appel recursif avec k=%d\n",
  84          k, T[k], k + 1, T[k + 1], k + 1);
  85     return mystere(T, k + 1, n, coltab + 1);
  86 }
  87
  88
  89
  90 int estDans(int *T, int x, int k, int n)
  91 {
  92     if (k > n - 1)
  93         return 0;
  94     if (T[k] == x)
  95         return 1;
  96     return estDans(T, x, k + 1, n);
  97 }
  98
  99
 100 /*****************************************************************/
 101 main()
 102 {
 103     int T[] = { 6, 9, 4, 8, 12 };
 104     int n = 5;
 105
 106     int reponse = mystere(T, 2, n, 0);
 107     printf("reponse = %d\n", reponse);
 108
 109     printf("\n");
 110
 111     reponse = mystere(T, 0, n, 0);
 112     printf("reponse = %d\n", reponse);
 113
 114     printf("\n");
 115     printf("estDans(T,9,0) = %d\n", estDans(T, 9, 0, n));
 116     printf("estDans(T,9,2) = %d\n", estDans(T, 9, 2, n));
 117     printf("estDans(T,12,3) = %d\n", estDans(T, 12, 3, n));
 118     printf("estDans(T,12,5) = %d\n", estDans(T, 12, 5, n));
 119 }
 120
 121
 122 /** trace d'execution *********************************
 123 appel mystere(6 9 4 8 12 , 2)
 124 T[2]=4 T[3]=8
 125 T[2]=4 <= T[3]=8 donc retourner appel recursif avec k=3
 126         appel mystere(6 9 4 8 12 , 3)
 127         T[3]=8 T[4]=12
 128         T[3]=8 <= T[4]=12 donc retourner appel recursif avec k=4
 129                 appel mystere(6 9 4 8 12 , 4)
 130                 k=4 et n-1=4 donc retourner VRAI
 131 reponse = 1
 132
 133 appel mystere(6 9 4 8 12 , 0)
 134 T[0]=6 T[1]=9
 135 T[0]=6 <= T[1]=9 donc retourner appel recursif avec k=1
 136         appel mystere(6 9 4 8 12 , 1)
 137         T[1]=9 T[2]=4
 138         T[1]=9 > T[2]=4 donc retourner FAUX
 139 reponse = 0
 140
 141 estDans(T,9,0) = 1
 142 estDans(T,9,2) = 0
 143 estDans(T,12,3) = 1
 144 estDans(T,12,5) = 0
 145 *********************************************************/