--- /dev/null
+/******************************************************************************/
+/* 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
+*********************************************************/