Série 6 :
Fonctions (2)

But

Le but de cette série d'exercices est de vous faire pratiquer encore plus les fonctions en C++ : prototypage, définition, surcharge, valeurs par défaut...

Préliminaires :

Avant d'effectuer les manipulations décrites dans cette série, créez le répertoire ~/Desktop/myfiles/cpp/serie06 (i.e. créez le sous-répertoire serie06 dans le répertoire ~/Desktop/myfiles/cpp).

Exercice 1 : Surcharge de fonction (niveau 1)

Exercice n°13 (pages 31 et 212) de l'ouvrage C++ par la pratique.
(pages 32 et 212 dans la 2e édition).
Dans le fichier surcharge.cc, écrivez un programme dans lequel :
  1. vous copiez la fonction echange de l'exercice 4 de la semaine passée ;
  2. vous définissez deux autres fonctions de même nom, l'une qui échange les valeurs de variables de type double et l'autre pour des valeurs de type char.
Utilisez le code main suivant pour tester vos fonctions : 
int main()
{
    int    i(10),      j(55);
    char   a('B'),     b('a');
    double x(3.14159), y(1.414);

    cout << "Avant: i=" << i << " et j=" << j << endl;
    echange(i,j);
    cout << "Après: i=" << i << " et j=" << j << endl << endl;

    cout << "Avant: a=" << a << " et b=" << b << endl;
    echange(a,b);
    cout << "Après: a=" << a << " et b=" << b << endl << endl;

    cout << "Avant: x=" << x << " et y=" << y << endl;
    echange(x,y);
    cout << "Après: x=" << x << " et y=" << y << endl;

    return 0;
}
Si vos fonctions sont correctes, le programme affichera : 
Avant: i=10 et j=55
Après: i=55 et j=10

Avant: a=B et b=a
Après: a=a et b=B

Avant: x=3.14159 et y=1.41
Après: x=1.41 et y=3.14159

Exercice 2 : Factorielle (fonctions récursives, niveau 1)

Exercice n°32 (pages 81 et 251) de l'ouvrage C++ par la pratique.

Pour calculer n! (factorielle n), on peut utiliser deux formules différentes :

  1. La formule itérative :
    n! = 1 * 2 * 3 * ... * n
  2. La formule récursive définissant n! en fonction de (n-1)! :
    0! (factorielle de zéro) = 1
    pour tout entier n>0, n! = n * (n-1)!

Dans un fichier C++, implémentez la fonction :
unsigned int factorielleIterative(unsigned int n)
qui calcule n! en faisant le produit des n premiers entiers à l'aide d'une boucle for.

Dans le même fichier, implémentez la fonction:
unsigned int factorielleRecursive(unsigned int n)
qui calcule n! en utilisant cette deuxième formule. Cette fonction doit donc faire appel à elle-même pour calculer (n-1)!, sauf si n vaut 0, auquel cas elle devra retourner 1.

[Remarque : Le corps de la fonction tient en 4 lignes]

En réutilisant la fonction demander_nombre() déjà utilisée plusieurs fois dans les séries précédentes, écrivez, dans la fonction main(), le programme qui demande à l'utilisateur d'entrer un entier naturel n (entre 0 et 12 si vous utilisez des int ou des long int et entre 0 et 20 si vous utilisez des long long int), et affiche n! en faisant une première fois appel à factorielleIterative(), puis dans un second temps à factorielleRecursive().

Pour terminer, on pourra ajouter une boucle demandant à l'utilisateur s'il souhaite recommencer.

Exemple de déroulement

Entrez un nombre entier compris entre 0 et 12 : 12
Méthode itérative :
    12! = 479001600
Méthode récursive :
    12! = 479001600
Voulez-vous recommencer [o/n] ? o
Entrez un nombre entier compris entre 0 et 12 : 6
Méthode itérative :
    6! = 720
Méthode récursive :
    6! = 720
Voulez-vous recommencer [o/n] ? n

Exercice 3 : Nombres de Fibonacci (fonctions récursives, niveau 1)

Exercice n°33 (pages 82 et 254) de l'ouvrage C++ par la pratique.
Exercice n°14 du MOOC (semaine 4)

Les nombres de Fibonnaci sont définis par la suite :

F(0) = 0
F(1) = 1
F(n) = F(n-1)+ F(n-2) avec n>1

Le but de cet exercice est d'écrire un programme qui calcule la valeur de F(n) selon la définition récursive précédente.

Dans le fichier fibonacci.cc, prototypez puis définissez la fonction

unsigned int Fibonacci(unsigned int n)
qui calcule la valeur de F(n) de manière récursive (cette fonction devra donc faire appel à elle-même) sans utiliser de structure de boucle (for, while, etc...) et sans aucune variable locale.

Pour comparaison, voici une manière itérative (i.e. non récursive) de calculer les n premier termes de la suite : 

unsigned int FibonacciIteratif(unsigned int n)
{
  unsigned int Fn(0);    // stocke F(i)  , initialisé par F(0)
  unsigned int Fn_1(Fn); // stocke F(i-1), initialisé par F(0)
  unsigned int Fn_2(1);  // stocke F(i-2), initialisé par F(-1)

  if (n > 0)
    for (unsigned int i(1); i <= n; ++i) {
      Fn   = Fn_1 + Fn_2;    // pour n>=1 on calcule F(n)=F(n-1)+F(n-2)
      Fn_2 = Fn_1;           // et on decale...
      Fn_1 = Fn;
    }
  return Fn;
}

Note : la méthode récursive est coûteuse en temps de calcul (elle est «exponentielle»), ne lancez pas le calcul pour des nombres trop élevés (disons supérieurs à 40).

Exemple de déroulement

Entrez un nombre entier compris entre 0 et 40 : 0
Méthode itérative :
    F(0) = 0
Méthode récursive :
    F(0) = 0
Voulez-vous recommencer [o/n] ? o
Entrez un nombre entier compris entre 0 et 40 : 1
Méthode itérative :
    F(1) = 1
Méthode récursive :
    F(1) = 1
Voulez-vous recommencer [o/n] ? o
Entrez un nombre entier compris entre 0 et 40 : 2
Méthode itérative :
    F(2) = 1
Méthode récursive :
    F(2) = 1
Voulez-vous recommencer [o/n] ? o
Entrez un nombre entier compris entre 0 et 40 : 3
Méthode itérative :
    F(3) = 2
Méthode récursive :
    F(3) = 2
Voulez-vous recommencer [o/n] ? o
Entrez un nombre entier compris entre 0 et 40 : 7
Méthode itérative :
    F(7) = 13
Méthode récursive :
    F(7) = 13
Voulez-vous recommencer [o/n] ? n

Exercice 4 : Calcul approché d'une intégrale (niveau 2)

Exercice n°15 (pages 33 et 214) de l'ouvrage C++ par la pratique.
Exercice supplémentaire n°9 du MOOC (semaine 4)
On peut montrer que pour une fonction suffisamment régulière (disons C-infinie), on a la majoration suivante :

où M8 est un majorant de la dérivée huitième de f sur le segment [a,b].

Ecrivez un programme calculant la valeur approchée d'une intégrale à l'aide de cette formule, c'est-à-dire par

Pour cela écrivez 3 fonctions :

  1. Une fonction f de votre choix, qui corresponde à la fonction dont vous souhaitez calculer l'intégrale.
    (Essayez plusieurs cas avec x2, x3, ..., sin(x), 1/x, etc. Il faudra bien sur recompiler le programme à chaque fois.)
    (Pour utiliser les fonctions mathématiques, n'oubliez pas d'ajouter «#include <cmath>» en début de programme.
    Pour plus de détails, voir la section correspondante dans la mini-référence sur les fonctions)
Utilisez ces fonctions dans le main() pour réaliser votre programme.

Note : Vous pourrez trouver ici une démonstration de la formule [lien externe] donnée plus haut.

(Niveau Avancé)   Remarque :
Comment faire pour ne pas recompiler le programme pour chaque nouvelle fonction ?

En tant que tel, c'est-à-dire laisser l'utilisateur saisir lui-même sa formule, cela est beaucoup trop compliqué pour ce cours d'introduction.
Mais si on simplifie le problème en donnant la possibilité de choisir parmi un ensemble de fonctions préféfinies (inclues alors dans le programme), alors c'est faisable en utilisant des pointeurs sur des fonctions. Les pointeurs seront introduits dans quelques semaines dans le cours.

Exercice 5 : Fonctions logiques (niveau 3)

Exercice supplémentaire n°10 du MOOC (semaine 4)

On vous donne la fonction non_et : 

bool non_et(bool A, bool B)
{
  return not(A and B);
}
qui renvoie la valeur de NON(A ET B). Comment écrire le corps des fonctions correspondant aux 3 opérateurs logiques NON, ET et OU: 
bool non(bool A)

bool et(bool A, bool B)

bool ou(bool A, bool B)
en utilisant UNIQUEMENT la fonction non_et, sans utiliser de if, ni d'opérateurs logiques or, and, not, ||, &&, ou !.

Commencez par écrire la fonction non à l'aide de non_et. Vous pouvez alors utiliser la fonction non en plus de non_et pour écrire la fonction et. La fonction ou peut s'écrire en utilisant les fonctions non et et.

Exercice 6 : LIEN COURS ICC : Recherche dichotomique (fonctions récursives, niveau 2)

Exercice n°34 (pages 83 et 256) de l'ouvrage C++ par la pratique.
Exercice supplémentaire n°11 du MOOC (semaine 4)

Pour illustrer l'utilisation de la récursivité dans la recherche d'un élément dans une liste ordonnée, nous allons jouer à un petit jeu :

Pensez très fort à un nombre entre 0 et 100...
voilà !
L'ordinateur doit maintenant le trouver...

Principe

Pour ce faire, il pourrait énumérer tous les nombres les uns après les autres jusqu'à avoir la bonne réponse.
Mais, vous en conviendrez aisément, ce n'est pas une méthode très efficace...

Une autre méthode (plus efficace) est la méthode dite « par dichotomie » : on réduit le champ de recherche à chaque étape et on recommence la recherche sur le nouvel intervalle.

On commence avec la zone complète, puis on choisit un pivot (point central de la zone de recherche). En fonction de la comparaison de ce pivot avec l'élément recherché, plusieurs cas de figures peuvent se présenter:

Mise en pratique

Dans le fichier dichotomie.cc

  1. Prototypez et définissez la fonction :
    unsigned int cherche(unsigned int borneInf, unsigned int borneSup);
    de sorte qu'elle effectue la recherche dans l'intervalle [borneInf, borneSup]

    Cette fonction devra choisir un pivot au milieu de l'intervalle (ou s'arrêter, avec un message d'erreur, si l'intervalle est vide), proposer le pivot à l'utilisateur, puis en fonction de sa réponse (<, > ou =) s'appeler elle-même sur le nouvel intervalle ainsi déterminé, ou arrêter la recherche.

    La fonction retourne la valeur trouvée (ou la borne inférieure en cas d'erreur).

  2. Dans la fonction main(), demandez à l'utilisateur de choisir (dans sa tête) un nombre entre 1 et 100 (définissez deux constantes MIN et MAX).
    Cherchez la solution à l'aide le la fonction cherche puis affichez le résultat trouvé.

Exemple de déroulement

Pensez à un nombre entre 1 et 100.

Le nombre est il <, > ou = à 50 ? <
Le nombre est il <, > ou = à 25 ? >
Le nombre est il <, > ou = à 37 ? <
Le nombre est il <, > ou = à 31 ? >
Le nombre est il <, > ou = à 34 ? <
Le nombre est il <, > ou = à 32 ? >
Le nombre est il <, > ou = à 33 ? =

Votre nombre était 33.

Vous voyez bien sur cet exemple l'intérêt de la recherche par dichotomie par rapport à la recherche linéaire : 6 questions au lieu de 33 (voire au lieu de 68 si l'on demandait en descendant depuis 100 ;-) ).

Exercice 7 : Recherche approchée de racine (niveau 2)

Exercice n°42 (pages 96 et 281) de l'ouvrage C++ par la pratique.
Exercice supplémentaire n°12 du MOOC (semaine 4)

On souhaite écrire un programme calculant, de façon approchée, une solution à une équation de type $$f(x) = 0$$.

La méthode à mettre en œuvre consiste à déterminer, à partir d’une approximation $$x_n$$ de la solution, une meilleure solution $$x_{n+1}$$, et itérer ainsi jusqu’à ce que la valeur absolue de la différence entre $$x_n$$ et $$x_{n+1}$$ soit « suffisamment petite ».

Le calcul de $$x_{n+1}$$ à partir de $$x_n$$ se fait à l’aide de la formule suivante (« méthode de Newton ») :

$$x_{n+1} = x_n − \frac{f(xn)}{f'(x_n)}$$

où $$f'$$ est la dérivée de $$f$$.

Écrire un programme reseq.cc contenant la définition d'une fonction f (à choix) de prototype double f(double).

Le programme demandera un point de départ à l’utilisateur, itérera la recherche d’une solution à partir de ce point, et affichera le résultat trouvé.

Note : Il n’est pas nécessaire d’utiliser un tableau (de taille fixe ou dynamique) pour résoudre ce problème.

Indication : Pour obtenir la valeur de la dérivée d’une fonction en un point, on s’inspire simplement de sa définition :

$$f'(x) = \lim_{\varepsilon\to0}\frac{f(x+\varepsilon)-f(x)}{\varepsilon} ,$$

dont on calcule une approximation pour une valeur ε donnée (par exemple 10−6 ) : définir la constante globale epsilon de valeur « 1e-6 », puis la fonction double df(double x) calculant la valeur approchée de la dérivée de f au point x par : 

(f(x+epsilon)-f(x))/epsilon

Exemple (détaillé) de déroulement

La fonction utilisée dans cet exemple est $$f (x) = (x - 1.0) (x - 1.5) (x - 2.0)$$ :

Point de depart ? 1.55
au point 1.55 :
f(x) = -0.012375
f’(x) = -0.2425
nouveau point = 1.49897
au point 1.49897 :
f(x) = 0.000257739
f’(x) = -0.249997
nouveau point = 1.5
au point 1.5 :
f(x) = -2.18843e-09
f’(x) = -0.25
nouveau point = 1.5
Solution : 1.5
Dernière mise à jour le 4 novembre 2016
 Last modified: Fri Nov 4, 2016