TD 2: Fonctions, Recursivité, Pointeurs

Rappels

• La section Outils du TD 1 est utile!
• Page du Cours

Exercice 1: Fonctions, #include, déclarations

1. Écrire un fichier 1.1.cc contenant uniquement une fonction int LaSolution(int x) qui renvoie toujours x + 42. Vérifiez-la avec le fichier 1.1.main.cc suivant (donc en faisant g++ 1.1.main.cc && ./a.out):

   #include <iostream>
   using namespace std;
   
   #include "1.1.cc"
   
   int main() {
     cout << LaSolution(3) << endl;
     cout << LaSolution(-1) << endl;
   }

   RENDU: 1.1.cc
   
   
2. Copiez 1.1.main.cc dans 1.2.main.cc puis modifiez ce dernier en enlevant #include "1.1.cc", et tentez de le compiler manuellement avec g++. Comment faire pour que ça marche?
   Indices:
   • g++ peut prendre plusieurs fichiers en arguments
   • Ajoutez une déclaration de la fonction LaSolution.
   
   RENDUS: 1.2.main.cc et un fichier 1.2.txt contenant la ligne de commande pour compiler
   
   

Exercice 2: Récursivité (ou pas), stack overflow

1. Écrire un fichier 2.1.cc contenant juste une fonction FactorielleMod qui prend un entier n et qui calcule n! modulo 1000000007.
   La fonction devra être récursive: sans utiliser de boucle for, while ou do.
   Attention aux overflow: un entier int ne va pas au-dessus de 2³¹-1. Un entier long va jusqu'à 2⁶³-1 par contre.
   
   Testez-le et corrigez-le avec ce fichier main.cc, comme avant.
   Note: 100! mod 1000000007 = 437918130.

   #include <iostream>
   using namespace std;
   
   #include "2.1.cc"
   
   int main() {
     cout << "Entrez un entier n: ";
     int n;
     cin >> n;
     cout << FactorielleMod(n) << endl;
   }

   RENDU: 2.1.cc
   
   
2. Essayez avec n=10000000 (10 millions). Que voyez-vous?
   
   C'est un stack overflow! Pour s'en sortir, deux solutions:
   1. Augmenter la taille maximum de la pile (stack). Cf aide en ligne:
      • Ajouter #include <sys/resource.h> dans votre main
      • Et au début de la fonction main(), ajoutez ces lignes:

        struct rlimit r;
        getrlimit(RLIMIT_STACK, &r);
        r.rlim_cur = 100 << 20;  // 100 MB.
        setrlimit(RLIMIT_STACK, &r);

      C'est à éviter en général, sauf cas très rare.
      
      
   2. Transformer votre code récursif en code itératif, qui est bien plus dans l'esprit de C++:
      
      Recodez une autre version FactorielleMod2(n) dans un nouveau fichier 2.2.cc, sans récursion mais avec une boucle for. Vous pouvez le tester avec le main d'avant, sans oublier de changer le 2.1.cc en 2.2.cc et FactorielleMod en FactorielleMod2.
      
      RENDU: 2.2.cc
      
   
   
3. Optionnel (non compabilisé, à faire en fin de TD): vous pouvez comparer les vitesses de FactorielleMod() et FactorielleMod2(), par exemple, en calculant la somme de n! pour n allant de 1 à 10000).
   Que cela donne-t-il?.
   
   
4. Écrivez dans un fichier 2.4.cc une fonction récursive FiboRec qui calcule le n-ième terme de la suite de Fibonacci, donnée par:
   F_n = F_n-1 + F_n-2 et F₀ = F₁ = 1.
   Essayez de calculer FiboRec(60). Que se passe-t-il? Pourquoi?
   
   RENDU: 2.4.cc
   
   
5. Écrivez dans un fichier 2.5.cc une fonction FiboIter qui calcule F_n, mais itérativement cette fois. Changez sa valeur de retour en double.
   Comparez les valeurs de FiboIter et FiboRec pour de petits nombres, puis essayez de calculer FiboIter(60), puis FiboIter(1000).
   
   RENDU: 2.5.cc
   
   
6. Écrivez dans un fichier 2.6.cc une fonction récursive Pgcd qui calcule le plus grand diviseur commun entre deux long.
   
   Vérifiez que Pgcd(2250, 1000) = 250; et essayez Pgcd(129387194869817412L, 19827398170419240L) et Pgcd(1000000007, 1). Si ca ne marche pas (ou prend trop de temps), essayez un autre algorithme plus efficace!
   
   RENDUS: 2.6.cc et une brève explication (dans un fichier 2.6.txt) de pourquoi on a pas le problème de stack overflow avec cette fonction
   
   

Exercice 3: Pointeurs, tableaux, algorithmes

1. Étant donné le fichier 3.1.cc suivant:

   #include <iostream>
   using namespace std;
   
   // Ne touchez pas à cette fonction! Utilisez-là telle qu'elle est.
   void GetDate(int* year, int* month, int* day) {
     *year = 2018;
     *month = 9;
     *day = 19;
   }
   
   int main() {
     // TODO: Utilisez GetDate() pour récuperer la date dans des
     // variables y, m et d de type int.
   
     // Affichage de la date.
     cout << y << "-" << m << "-" << d << endl;
   }

   Téléchargez-le et complétez-le.
   Vérifiez en le compilant et en l'éxecutant: il doit marcher, et afficher 2018-09-19.
   Rappel: Pour compiler et éxecuter d'une seule traite: g++ votre_code.cc && ./a.out
   
   RENDU: 3.1.cc (complété!)
   
   
2. Écrivez un fichier 3.2.cc contenant une fonction Strip() qui enlève tous les espaces d'une chaîne de caractères.
   Indications:
   • On utilisera le type char* pour representer une chaîne de caractères.
   • Une chaîne de caractères étant un tableau, on peut le modifier en place dans une fonction. Pas besoin de renvoyer une autre chaîne de caractères.
   • Le caractère "espace" (de type char) s'écrit avec les guillemets simples: ' '
   
   Vérifiez votre fonction en téléchargeant 3.2.test.cc dans le même repertoire que 3.2.cc et en le compilant/exécutant.
   
   RENDU: 3.2.cc
   
   
3. Écrivez un fichier 3.3.cc qui #include "3.2.cc" et qui contient une fonction main() pour que votre programme execute la fonction Strip sur son premier argument, et l'affiche (avec un saut de ligne à la fin). Donc, si vous faites ça:

   g++ 3.3.cc
   ./a.out " Bonjour  madame     la marquise H E L L O    W    ORL D  "

   Vous devez obtenir: BonjourmadamelamarquiseHELLOWORLD
   
   Indications:
   • Il va falloir utiliser la fonction main() standard, et non sa version abrégée comme on a fait jusque-là: int main(int argc, char** argv)
   • Le premier argument de votre programme sera stocké dans argv[1], qui est modifiable.
   
   RENDU: 3.3.cc