X-Git-Url: https://git.piment-noir.org/?p=Algorithmic_C.git;a=blobdiff_plain;f=exam1%2FExamenAlgo1correction.c;fp=exam1%2FExamenAlgo1correction.c;h=24f014e16f35d50eb27212c0bf1d5d26802c216f;hp=0000000000000000000000000000000000000000;hb=a0a33bfafcc44708265d9b96fe35682c7c416925;hpb=26317590ee567f7cd092fc2fa85381545a63c63d

diff --git a/exam1/ExamenAlgo1correction.c b/exam1/ExamenAlgo1correction.c
new file mode 100644
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
+*********************************************************/