Refine .gitignore some more.
[Algorithmic_C.git] / exam1 / ExamenAlgo1correction.c
CommitLineData
a0a33bfa
JB
1/******************************************************************************/
2/* examen algo I : correction et implantation */
3/******************************************************************************/
4
5/*
61)
7appel mystere(6 9 4 8 12 , 2)
8T[2]=4 T[3]=8
9T[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
15reponse de mystere(6 9 4 8 12 , 2) = Vrai
16
172)
18appel mystere(6 9 4 8 12 , 0)
19T[0]=6 T[1]=9
20T[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
24reponse de appel mystere(6 9 4 8 12 , 0) = Faux
25
263)
27La fonction mystere(t, k) retourne Vrai si la suite d'entiers contenue dans
28le tableau t a partir de l'indice k est croissante et retourne Faux sinon.
29
304)
31Le pire des cas correspond a l'appel mystere(t,k) pour un tableau croissant
32a partir de l’indice k. Il y a dans ce cas n-k appels recursifs en comptant
33l'appel initial.
34
355) 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
43void 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
52int 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
90int 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/*****************************************************************/
101main()
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 *********************************
123appel mystere(6 9 4 8 12 , 2)
124T[2]=4 T[3]=8
125T[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
131reponse = 1
132
133appel mystere(6 9 4 8 12 , 0)
134T[0]=6 T[1]=9
135T[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
139reponse = 0
140
141estDans(T,9,0) = 1
142estDans(T,9,2) = 0
143estDans(T,12,3) = 1
144estDans(T,12,5) = 0
145*********************************************************/