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