# Algo Prog 2021-2022: TP5 (récursivité) ###### tags: `algo` `bourg` `c++` `iut` `tp` ## Exercice 1: PGCD Le PGCD de deux nombres peut être calculé récursivement en utilisant la formule de récurrence suivante: $pgcd(a,b)=pgcd(b,r)$ où $r$ est le reste de la division Euclienne de a par b. En utilisant cette formule, l'algorithme d'Euclide explique que le PCGD est le dernier reste non nul dans la suite des divisions. 1. Ecrivez une fonction **récursive** ``int pgcd(int a,int b)`` qui retourne la valeur du pgcd. Testez-là. 2. Complétez votre code pour afficher le nombre total d'appels à la fonction récursive. Combien de fois est-elle appelée pour $a=124$ et $b=38$ ? Pour $a=144$ et $b=89$ ? :::info Pour récupérer cette information, vous pouvez utiliser une variable globale qui est incrémentée à chaque fois que vous rentrez dans la fonction. ::: 3. On fixe $a=244$ et $b<a$. Pour quelle valeur de $b$ le nombre d'appels récursif est-il le plus grand lors du calcul de ``pgcd(a,b)`` ? :::spoiler ````C++ int CPT; int pgcd(int a, int b) { CPT++; if (a % b == 0) { return b; } return pgcd(b, a % b); } int main() { int a = 124; int b = 38; cout << pgcd(a, b) << endl << CPT << " appels à la fonction" << endl; CPT = 0; a = 144; b = 89; cout << pgcd(a, b) << endl; cout << CPT << " appels à la fonction" << endl; int max, bmax; max = 0; a = 244; for (b = 1; b < a; b++) { CPT = 0; if (CPT > max) { bmax = b; max = CPT; } } cout << "Max d'appels pour " << bmax << endl; return 0; } ```` ::: ## Exercice 2 : Recherche d'élément dans un tableau trié On considère le tableau suivant: ``int t[30]={21,-432,-77,84,91,74,45,899,301,2,-1,-987,-456,87,745,79,-4,-56,754,32,145,156,54,-2,-89,963,71,-222,-333,7};`` Copiez-coller cette ligne au début de votre programme. Dans la suite de l'exercice, vous travaillerez tous avec ce tableau déclaré en tant que variable globale. 1. Ecrivez une fonction qui permette de trier ce tableau dans l'ordre croissant. 2. Recherche dichotomique On veut écrire une fonction récursive qui retourne si une valeur entière $v$ est présente dans le tableau ``t`` trié, et si oui, à quel indice. Pour cela, vous allez utiliser une recherche dichotomique (qui est beaucoup plus efficace que parcourir toutes les cases du tableau): - cherchez la case dont l'indice $i_1$ correspond au milieu du tableau (arrondissez à l'entier inférieur si la taille est impaire) - si cette case vaut $v$, alors retournez $i_1$ - sinon: - si $t[i_1]>v$, alors cela signifie que si $v$ est dans le tableau, alors il est à gauche de $i_1$ (comme le tableau est trié). Recommencez le même algorithme pour le sous-tableau dont les indices vont de 0 à $i_1-1$. - si $t[i_1]<v$, alors cela signifie que si $v$ est dans le tableau, alors il est à droite de $i_1$ (comme le tableau est trié). Recommencez le même algorithme pour le sous-tableau dont les indices vont de $i_1+1$ à $taille-1$. - arrêtez la récursivité si vous avez trouvé $v$ ou alors si le sous-tableau est de taille inférieure à $1$. Comme vous allez travailler sur des sous-tableaux, vous aurez besoin de garder comme information l'indice de début et de fin de vos sous-tableaux. Votre fonction pourra donc avoir comme entête ``int recherche_dicho(int t[], int v, int indice_debut, int indice_fin)``. Elle retournera l'indice si la valeur est présente, et $-1$ si l'élément est absent. Testez votre fonction sur le tableau ``t`` en le triant au préalable. Testez-le sur les valeurs $v=45$, $v=0$, $v=963$ et $v=-987$. :::spoiler ````C++ void afficheT() { for (int i = 0; i < N; ++i) cout << t[i] << ", "; cout << endl; } void echange(int& a, int& b) { int tmp = a; a = b; b = tmp; } void triT() { for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { if (t[j] < t[i]) echange(t[i], t[j]); } } } int rechercheDicho(int t[], int v, int debut, int fin) { if (debut > fin) return -1; int milieu = (debut + fin) / 2; if (t[milieu] == v) return milieu; if (t[milieu] > v) return rechercheDicho(t, v, debut, milieu - 1); else return rechercheDicho(t, v, milieu + 1, fin); } int main() { afficheT(); triT(); afficheT(); cout << "45, position: " << rechercheDicho(t, 45, 0, N - 1) << endl; cout << "0, position: " << rechercheDicho(t, 0, 0, N - 1) << endl; cout << "963, position: " << rechercheDicho(t, 963, 0, N - 1) << endl; cout << "-987, position: " << rechercheDicho(t, -987, 0, N - 1) << endl; return 0; } ```` ::: ## Exercice 3: rendu de pièces de monnaie Un distributeur de monnaie contient des pièces (qu'on considèrera toujours en quantité suffisante) de valeur $v_1, v_2, \ldots v_N$. L'objectif pour vous est de calculer, pour une somme à distribuer $S$, le nombre minimum de pièces à rendre pour égaler $S$. Par exemple, si le distributeur a des pièces de valeur $1,2,5,10$, et qu'il faut distribuer $S=14$, alors le nombre minimum de pièces à donner est de 3, en donnant une pièce de valeur 10 et deux pièces de 2. Dans ce qui suit, on supposera toujours que $v_1=1$ pour s'assurer que le problème a toujours une solution. Pour vous aider à trouver un algorithme qui effectue ce calcul, on vous propose de répondre aux questions suivantes: 1. On note $M(s,i)$ le nombre minimum de pièces à distribuer pour une somme $s$, sachant qu'on ne peut utiliser que les pièces de valeur $v_1,\ldots v_i$. Par exemple, si on prend les valeurs des pièces comme ci-dessus, c'est à dire: | v1 | v2 | v3 | v4 | | --- | --- | --- | --- | | 1 | 2 | 5 | 10 | alors $M(14,4)=3$ (c'est l'exemple qui est donné plus haut). En revanche, $M(14,3)=4$ puisqu'on ne peut utiliser que les pièces de valeur 1, 2 et 5 dans ce cas. Que vaut $M(0,i)$ pour tout $i\geq 1$ ? Sachant que $v_1=1$, que vaut $M(s,1)$ pour tout $s\geq 0$ ? :::spoiler $M(0,i)=0$, $M(s,1)=s$. ::: 2. Donner une formule de récurrence entre $M(s,i)$, $M(s,i-1)$ et $M(s-v_i,i)$. :::spoiler $M(s,i)=\min\{M(s,i-1),1+M(s-v_i,i)\}$ ::: 3. On va passer au codage. Déclarez une constante $N$ égale à 4 (correspond au nombre de types de pièces), et le tableau $v$ qui contient les valeurs $v_1, \ldots v_N$ en tant que constante. Vous pouvez utiliser les valeurs de l'exemple ci-dessus en faisant: `` const int v[N+1]={0,1,2,5,10};`` N.B: la valeur ``v[0]`` ne sera jamais utilisée ici. Déclarez aussi la constante $S$ (vous pouvez l'initialiser à 14). 4. En utilisant la formule de récurrence de la question 2, et les valeurs de base de la question 1, écrivez une fonction récursive ``int calculM(int s, int i)`` qui retourne la valeur de $M(s,i)$. Testez votre fonction pour $s=39$ et $i=4$. Même question pour $s=7789$ et $i=4$. :::spoiler ````C++ const int N = 4; const int v[N + 1] = { 0,1,2,5,10 }; const int S = 7789; //formule récurrence: M(s,i)=min { vi + M(s-vi,i) , M(s,i-1) } int M(int s, int i) { //cout << "M(" << s << "," << i << ")" << endl; if (s == 0) return 0; if (i == 1) return s; int res; if (s >= v[i]) { res = min(1 + M(s - v[i], i), M(s, i - 1)); //min c'est un probleme de minimisation } else { res = M(s, i - 1); } return res; } ```` ::: 5. Codez maintenant la fonction ``int calcul_iteratifM(int s, int i)`` qui calcule également $M(S,i)$ mais cette fois-ci, de façon itérative. Pour cela, vous pourrez utiliser un tableau de taile $(N+1)\times (S+1)$ que vous remplirez au fur et à mesure. Testez votre fonction pour $s=39$ et $i=4$. Même question pour $s=7789$ et $i=4$. Comparez la durée d'exécution avec la version récursive. :::spoiler ````C++ int Mit(int s, int i) { int t[N + 1][S + 1]; int cpt = 0; int res; //remplissage for (int s = 0; s <= S; ++s) {//cas avec une seule pièce de 1 t[1][s] = s; } for (int n = 2; n <= N; n++) { for (int s = 0; s <= S; ++s) { if (s >= v[n]) { t[n][s] = min(1 + t[n][s - v[n]], t[n - 1][s]); //min c'est un probleme de minimisation } else { t[n][s] = t[n - 1][s]; } } } return t[i][s]; } ```` ::: 6. Modifiez votre fonction de la question 5 pour qu'elle affiche la répartition des pièces à distribuer. ## Exercice 4 En utilisant le fichier dictionnaire du TP2 ([ici](https://perso.liris.cnrs.fr/eric.duchene/algo/DicFra.csv)), quels sont les mots les plus longs du dictionnaire qui n'ont que des lettres différentes ? (pas de récursivité dans cette question).