Refine .gitignore some more.

[Algorithmic_C.git] / exam1 / ExamenAlgo1correction.c

/******************************************************************************/
/*              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
*********************************************************/