Add the two exams correction

[Algorithmic_C.git] / exam1 / ExamenAlgo1correction.c

diff --git a/exam1/ExamenAlgo1correction.c b/exam1/ExamenAlgo1correction.c
new file mode 100644 (file)
index 0000000..24f014e
--- /dev/null
+++ b/exam1/ExamenAlgo1correction.c
@@ -0,0 +1,145 @@
+/******************************************************************************/
+/*              examen algo I : correction et implantation                    */
+/******************************************************************************/
+
+/*
+1)
+appel mystere(6 9 4 8 12 , 2)
+T[2]=4 T[3]=8
+T[2]=4 <= T[3]=8 donc retourner appel recursif avec k=3
+       appel mystere(6 9 4 8 12 , 3)
+       T[3]=8 T[4]=12
+       T[3]=8 <= T[4]=12 donc retourner appel recursif avec k=4
+               appel mystere(6 9 4 8 12 , 4)
+               k=4 et n-1=4 donc retourner VRAI
+reponse de mystere(6 9 4 8 12 , 2) = Vrai
+
+2)
+appel mystere(6 9 4 8 12 , 0)
+T[0]=6 T[1]=9
+T[0]=6 <= T[1]=9 donc retourner appel recursif avec k=1
+       appel mystere(6 9 4 8 12 , 1)
+       T[1]=9 T[2]=4
+       T[1]=9 > T[2]=4 donc retourner FAUX
+reponse de appel mystere(6 9 4 8 12 , 0) = Faux
+
+3)
+La fonction mystere(t, k) retourne Vrai si la suite d'entiers contenue dans
+le tableau t a partir de l'indice k est croissante et retourne Faux sinon.
+
+4)
+Le pire des cas correspond a l'appel mystere(t,k) pour un tableau croissant 
+a partir de l’indice k. Il y a dans ce cas n-k appels recursifs en comptant 
+l'appel initial.
+
+5) voir, plus bas, la fonction estDans(int *T, int x, int k, int n) implantant l'algorithme.
+*/
+
+
+#include <stdio.h>
+#include <stdlib.h>
+
+
+void affichertab(int *T, int taille)
+{
+    int i;
+    for (i = 0; i < taille; i++) {
+       printf("%d ", T[i]);
+    }
+}
+
+
+int mystere(int *T, int k, int n, int coltab)
+{
+    int i = 0;
+    for (i = 0; i < coltab; i++)
+       printf("\t");
+    printf("appel mystere(");
+    affichertab(T, n);
+    printf(", %d)\n", k);
+
+    if (k == n - 1) {
+       for (i = 0; i < coltab; i++)
+           printf("\t");
+       printf("k=%d et n-1=%d donc retourner VRAI\n", k, n - 1);
+       return 1;
+    }
+
+    for (i = 0; i < coltab; i++)
+       printf("\t");
+    printf("T[%d]=%d T[%d]=%d\n", k, T[k], k + 1, T[k + 1]);
+
+    if (T[k] > T[k + 1]) {
+       for (i = 0; i < coltab; i++)
+           printf("\t");
+       printf("T[%d]=%d > T[%d]=%d donc retourner FAUX\n", k, T[k], k + 1,
+              T[k + 1]);
+       return 0;
+    }
+
+    for (i = 0; i < coltab; i++)
+       printf("\t");
+    printf
+       ("T[%d]=%d <= T[%d]=%d donc retourner appel recursif avec k=%d\n",
+        k, T[k], k + 1, T[k + 1], k + 1);
+    return mystere(T, k + 1, n, coltab + 1);
+}
+
+
+
+int estDans(int *T, int x, int k, int n)
+{
+    if (k > n - 1)
+       return 0;
+    if (T[k] == x)
+       return 1;
+    return estDans(T, x, k + 1, n);
+}
+
+
+/*****************************************************************/
+main()
+{
+    int T[] = { 6, 9, 4, 8, 12 };
+    int n = 5;
+
+    int reponse = mystere(T, 2, n, 0);
+    printf("reponse = %d\n", reponse);
+
+    printf("\n");
+
+    reponse = mystere(T, 0, n, 0);
+    printf("reponse = %d\n", reponse);
+
+    printf("\n");
+    printf("estDans(T,9,0) = %d\n", estDans(T, 9, 0, n));
+    printf("estDans(T,9,2) = %d\n", estDans(T, 9, 2, n));
+    printf("estDans(T,12,3) = %d\n", estDans(T, 12, 3, n));
+    printf("estDans(T,12,5) = %d\n", estDans(T, 12, 5, n));
+}
+
+
+/** trace d'execution *********************************
+appel mystere(6 9 4 8 12 , 2)
+T[2]=4 T[3]=8
+T[2]=4 <= T[3]=8 donc retourner appel recursif avec k=3
+       appel mystere(6 9 4 8 12 , 3)
+       T[3]=8 T[4]=12
+       T[3]=8 <= T[4]=12 donc retourner appel recursif avec k=4
+               appel mystere(6 9 4 8 12 , 4)
+               k=4 et n-1=4 donc retourner VRAI
+reponse = 1
+
+appel mystere(6 9 4 8 12 , 0)
+T[0]=6 T[1]=9
+T[0]=6 <= T[1]=9 donc retourner appel recursif avec k=1
+       appel mystere(6 9 4 8 12 , 1)
+       T[1]=9 T[2]=4
+       T[1]=9 > T[2]=4 donc retourner FAUX
+reponse = 0
+
+estDans(T,9,0) = 1
+estDans(T,9,2) = 0
+estDans(T,12,3) = 1
+estDans(T,12,5) = 0
+*********************************************************/