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