TD 5 : Fonctions et tableaux#
Exercice 1 : Échauffement
Quelles sont les valeurs v[0], v[1], …
contenues dans le tableau v à la fin de l’exécution du
programme suivant :
vector<int> v; // Declaration
v = vector<int>(5); // Allocation
for ( int i = 0; i < v.size(); i++ ) { // Initialisation
v[i] = i*i;
}
/// BEGIN SOLUTION
Le tableau contient les éléments 0, 1, 4, 9, 16 (les premiers carrés).
/// END SOLUTION
Exercice 2 : Mystère
On considère la fonction mystère suivante :
int mystere(vector<int> t) {
int m = t[0];
for ( int i = 1; i < t.size(); i++ ){
if ( m < t[i] ) {
m = t[i];
}
}
return m;
}
Exécutez pas à pas le programme suivant :
vector<int> t = { 5, -1, 3, 7, -4, 8, 4 }; int resultat = mystere(t);
Quelle est la valeur de la variable
resultatà la fin de l’exécution? Que fait la fonction mystère?/// BEGIN SOLUTION
En exécutant pas à pas la fonction avec le paramètre donné, on a comme valeurs à chaque début de boucle :
imt[i]
1 5 -1 2 5 3 3 5 7 4 7 -4 5 7 8 6 8 4 7
Donc
resultatvaut 8 (valeur renvoyée par la fonctionmystereappliquée àt).La fonction mystère prend en argument un tableau d’entiers et renvoie le maximum du tableau.
/// END SOLUTION
Modifiez la fonction pour qu’elle calcule le minimum d’un tableau.
/// BEGIN SOLUTION
Il suffit de changer le test du
if:int min(vector<int> t) { int m = t[0]; for ( int i = 1; i < t.size(); i++ ){ if ( t[i] < m ) m = t[i]; } return m; }
/// END SOLUTION
Exercice 3 : Quelques fonctions sur les tableaux
Spécifiez (sous forme de documentation) et implantez (sous forme de code) une fonction qui renvoie vrai si tous les éléments d’un tableau d’entiers sont positifs, et faux sinon.
/// BEGIN SOLUTION
/** Teste si tous les éléments d'un tableau sont positifs * @param tab un tableau d'entiers * @return true si tous les éléments de tab sont positifs, false sinon **/ bool positifs(vector<int> tab) { int taille = tab.size(); for (int i = 0; i < taille; i++) { if (tab[i] < 0) return false; } return true; }
/// END SOLUTION
Spécifiez et implantez une fonction qui incrémente de 1 tous les éléments d’un tableau d’entiers et renvoie le tableau.
/// BEGIN SOLUTION
/** Incrémente de 1 tous les éléments d'un tableau et le renvoie * @param tab un tableau d'entiers * @return le tableau modifié **/ vector<int> incremente(vector<int> tab) { int taille = tab.size(); for (int i = 0; i < taille; i++) { tab[i]++; } return tab; }
/// END SOLUTION
Spécifiez et implantez une fonction qui teste si deux tableaux d’entiers sont égaux.
/// BEGIN SOLUTION
/** Teste si deux tableaux sont égaux (c'est-à-dire tailles égales et * éléments de même indice égaux) * @param tab1 le premier tableau d'entiers * @param tab2 le deuxième tableau d'entiers * @return true si les deux tableaux sont égaux, false sinon **/ bool testEgaux(vector<int> tab1, vector<int> tab2) { if (tab1.size() != tab2.size()) { return false; } for (int i = 0; i < tab1.size(); i++) { if ( tab1[i] != tab2[i] ) { return false; } } return true; }
/// END SOLUTION
Spécifiez et implantez une fonction qui compte le nombre d’éléments strictement plus grands qu’un seuil donné dans un tableau d’entiers.
/// BEGIN SOLUTION
/** Compte les éléments du tableau strictement plus grands qu'un seuil donné * @param tab un tableau d'entiers * @param seuil l'entier que les éléments à dénombrer dépasse. * @return nombre d'éléments du tableau strictement plus grands que le seuil, * les doublons sont comptés plusieurs fois. **/ int nbElementsPlusQueSeuil(vector<int> tab, int seuil) { int cpt = 0; for (int i = 0; i < tab.size(); i++) { if (tab[i] > seuil) cpt = cpt + 1; } return cpt; }
/// END SOLUTION
Spécifiez et implantez une fonction qui renvoie vrai si un tableau d’entiers est trié dans l’ordre croissant, et faux sinon.
/// BEGIN SOLUTION
/** Teste si un tableau est trié en ordre croissant * @param tab un tableau d'entiers * @return true si le tableau est trié en ordre croissant, false sinon **/ bool estTrie(vector<int> tab) { for (int i = 0; i < tab.size() - 1; i++) { if (tab[i] > tab[i + 1]) return false; } return true; }
Remarquez la condition de boucle qui est ici
i < tab.size()-1à cause de l’utilisation detab[i+1]./// END SOLUTION
Notes aux enseignants
L’exo Fibonacci suivant sera repris en TP. Ne le corrigez pas forcément, mais donnez des indications détaillées sur les trois versions afin qu’ils aient bien compris le principe et soient capables de les faire seuls en TP. Ils ont en général du mal à comprendre le principe (par exemple le fait que pour avoir \(u_n\), il faut d’abord avoir calculé toutes les valeurs de \(u_1\) à \(u_{n-1}\), et les calculer dans cet ordre !).
Exercice 4 :
La suite de Fibonacci est définie récursivement par la relation : \(U_{n}=U_{n-1}+U_{n-2}\). Cette définition doit être complétée par une condition d’initialisation, en l’occurrence : \(U_{1}=U_{2}=1\). Introduite par Léonard de Pise (surnommé Fibonacci), cette suite décrit un modèle simplifié de l’évolution d’une population de lapins. Les premiers termes sont donnés par : 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, … Voir aussi https://oeis.org/A000045.
L’objectif est de donner trois implantations de la fonction dont la documentation et les tests sont donnés ci-dessous :
/** Suite de Fibonacci
* @param n un entier strictement positif
* @return le n-ième terme de la suite de Fibonacci
**/
CHECK( fibonacci(1) == 1 );
CHECK( fibonacci(2) == 1 );
CHECK( fibonacci(3) == 2 );
CHECK( fibonacci(4) == 4 );
CHECK( fibonacci(5) == 5 );
CHECK( fibonacci(6) == 8 );
Vérifiez la cohérence entre tests et documentation. Corrigez si nécessaire.
/// BEGIN SOLUTION
Le quatrième test n’est pas correct. Version corrigée :
CHECK( fibonacci(1) == 1 ); CHECK( fibonacci(2) == 1 ); CHECK( fibonacci(3) == 2 ); CHECK( fibonacci(4) == 3 ); CHECK( fibonacci(5) == 5 ); CHECK( fibonacci(6) == 8 );
/// END SOLUTION
Implantez la fonction fibonacci avec une boucle
foret un tableau de taille \(n\) pour stocker tous les éléments de la suite \(U_1,\ldots,U_n\)./// BEGIN SOLUTION
int fibonacciTableau(int n) { if(n == 1 or n == 2) { return 1; } else { vector<int> u(n); u[0] = 1; u[1] = 1; for (int i = 2; i < n; i++) { u[i] = u[i-1] + u[i-2]; } return u[n-1]; } }
/// END SOLUTION
Implantez la fonction fibonacci sans tableau, en utilisant une boucle
foret trois variables dont deux qui, au début de chaque tour de boucle, contiennent respectivement les valeurs de \(U_{k-1}\) et \(U_{k-2}\)./// BEGIN SOLUTION
int fibonacciVariables(int n) { int u1 = 1; int u2 = 1; int tmp = 0; if(n == 1 or n == 2) { return 1; } else { for (int i = 3; i <= n; i++) { tmp = u2; u2 = u1 + u2; u1 = tmp; } return u2; } }
/// END SOLUTION
Implantez une version récursive de la fonction fibonacci.
/// BEGIN SOLUTION
int fibonacciRecursive(int n) { if(n == 1 or n == 2) { return 1; } else { return fibonacciRecursive(n-2) + fibonacciRecursive(n-1); } }
/// END SOLUTION
Laquelle de ces trois implantations est-elle la plus expressive?
/// BEGIN SOLUTION
La fonction récursive : elle traduit littéralement la définition mathématique de la suite.
/// END SOLUTION
\(\clubsuit\) Comparez l’efficacité des trois implantations. Quel phénomène a lieu pour la fonction récursive? Comment pourrait-on le corriger?
/// BEGIN SOLUTION
Les deux premières implantations calculent la valeur en temps linéaire, la première stockant inutilement les valeurs intermédiaires. La troisième implantation, bien que plus expressive, est extrêmement inefficace : le calcul de \(U_n\) nécessite en effet le recalcul complet de \(U_{n-1}\) et de \(U_{n-2}\) et ainsi de suite. Du coup, si l’on note \(C_n\) le nombre d’opérations requis pour calculer \(U_n\), on obtient une nouvelle suite satisfaisant une équation similaire à celle de Fibonacci: \(C_n = C_{n-1} + C_{n-2} + 1\). En particulier, \(C_n \geq U_n\) et croît comme une exponentielle.
Indication : pour visualiser ce phénomène, dessinez un arbre dont les noeuds sont les appels à la fonction récursive pour calculer par exemple \(U_6\). Entourez les noeuds correspondants au calcul de \(U_3\), \(U_4\), \(U_5\) et constatez la redondance massive dans le calcul.
Un moyen de corriger cela est la mémoïsation : voir https://fr.wikipedia.org/wiki/Mémoïsation#Exemple pour un exemple sur la version récursive de la suite de Fibonacci.
/// END SOLUTION
Exercice 5 : \(\clubsuit\)
Que fait la fonction suivante?
vector<int> mystere(vector<int> t) { int n = t.size(); vector<int> r(n); for (int i=0; i<n; i++) { r[i] = t[n-1-i]; } return r; }
/// BEGIN SOLUTION
La fonction mystere prend en paramètre un tableau
tet renvoie un nouveau tableaurqui est le miroir det(le premier élément derest le dernier élément det, etc.)./// END SOLUTION
Un palindrome est un tableau comme \(\{2,8,-1,6,-1,8,2\}\) qui peut se lire de la même façon dans les deux sens. Écrivez une fonction
palindromequi teste si un tableau est un palindrome en utilisant les fonctions déjà vues dans le TD./// BEGIN SOLUTION
bool palindrome(vector<int> t) { return testEgaux(t, mystere(t)); }
/// END SOLUTION
Réécrivez une fonction
palindromeIndependant, testant si un tableau est un palindrome, sans utiliser les fonctions déjà vues dans les exercices précédents./// BEGIN SOLUTION
bool palindromeIndependant(vector<int> t) { int n = t.size(); for ( int i = 0; i < n/2; i++) { if (t[i] != t[n-i-1]) return false; } return true; }
/// END SOLUTION
Commentez les avantages et inconvénients des deux implantations.
/// BEGIN SOLUTION
La première est plus concise et expressive (proche de la définition mathématique). La deuxième est plus optimisée.
/// END SOLUTION