Livre_silo 30 août 2013 16:32 Page 141
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
141
5 – Fonctions
4 Écrire une deuxième fonction qui compte les jeux au cours d’un set et s’arrête lorsqu’un joueur gagne
le set. Cette fonction fera appel à la précédente pour savoir qui gagne les jeux. On n’oubliera pas de
prévoir le cas particulier du jeu décisif.
5 Écrire une troisième fonction qui compte les sets et s’arrête lorsqu’un joueur gagne le match. On pourra,
avant de commencer le match, demander en combien de sets gagnants il est joué.
Exercices utilisant la récursivité
Exercice 5.23 Écrire une fonction récursive qui calcule la somme des n premiers entiers. Quelle est la
complexité de cette fonction ?
Exercice 5.24 * Suite de Fibonacci. On considère la suite de Fibonacci définie par :
F 0 = 0
F 1 = 1
Fn = F n−2 + F n−1 pour n ⩾ 2.
Écrire une fonction récursive basée sur ces relations qui prend n en argument et renvoie Fn. Quelle est
sa complexité ?
Accélérer le calcul de Fn en écrivant plutôt une fonction récursive auxiliaire qui prend en arguments F n−1 ,
Fn et k ⩾ 0 et renvoie F n+k (on pourra poser F −1 = 1). Quelle est la nouvelle complexité ?
Exercice 5.25 ** Écrire une fonction récursive qui calcule le PGCD des deux entiers naturels passés en
arguments en suivant l’algorithme d’Euclide. Démontrer la terminaison et la correction de cette fonction.
Exercice 5.26 Modifier la fonction qui calcule les termes de la suite de Syracuse (voir l’encadré page 137)
pour qu’elle affiche les éléments de la suite jusqu’au premier rang n 0 tel que un 0 = 1, ainsi que la valeur
de n 0 .
Exercice 5.27 Définir une fonction récursive qui, étant donné un entier n, décide si l’écriture en base 3
de n ne comporte que des 0 et des 1. Quelle est la complexité de cette fonction ?
Exercice 5.28 ** Les tours de Hanoï. Les tours de Hanoï est un jeu inventé par Édouard Lucas en 1883.
Il est formé de sept disques de tailles différentes répartis en trois colonnes. Au départ, tous les disques
sont empilés sur la colonne de gauche par taille croissante.
hanoi.pdf
Les seuls mouvements possibles sont les déplacements d’un disque situé au sommet d’une colonne vers
le sommet d’une autre colonne, à condition que la colonne d’arrivée soit vide ou que le disque déplacé
soit plus petit que son sommet. On note n -> n' le déplacement d’un disque de la colonne n vers la
colonne n'. Le but du jeu est de déplacer tous les disques vers la colonne de droite.
hanoi2.pdf
Écrire un programme qui affiche une solution du jeu sous la forme d’une suite de mouvements.
Indication : dans une variante, le jeu n’est formé que de six disques. Si l’on sait résoudre le jeu à six disques,
comment résoudre le jeu à sept disques ?
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
141
5 – Fonctions
4 Écrire une deuxième fonction qui compte les jeux au cours d’un set et s’arrête lorsqu’un joueur gagne
le set. Cette fonction fera appel à la précédente pour savoir qui gagne les jeux. On n’oubliera pas de
prévoir le cas particulier du jeu décisif.
5 Écrire une troisième fonction qui compte les sets et s’arrête lorsqu’un joueur gagne le match. On pourra,
avant de commencer le match, demander en combien de sets gagnants il est joué.
Exercices utilisant la récursivité
Exercice 5.23 Écrire une fonction récursive qui calcule la somme des n premiers entiers. Quelle est la
complexité de cette fonction ?
Exercice 5.24 * Suite de Fibonacci. On considère la suite de Fibonacci définie par :
F 0 = 0
F 1 = 1
Fn = F n−2 + F n−1 pour n ⩾ 2.
Écrire une fonction récursive basée sur ces relations qui prend n en argument et renvoie Fn. Quelle est
sa complexité ?
Accélérer le calcul de Fn en écrivant plutôt une fonction récursive auxiliaire qui prend en arguments F n−1 ,
Fn et k ⩾ 0 et renvoie F n+k (on pourra poser F −1 = 1). Quelle est la nouvelle complexité ?
Exercice 5.25 ** Écrire une fonction récursive qui calcule le PGCD des deux entiers naturels passés en
arguments en suivant l’algorithme d’Euclide. Démontrer la terminaison et la correction de cette fonction.
Exercice 5.26 Modifier la fonction qui calcule les termes de la suite de Syracuse (voir l’encadré page 137)
pour qu’elle affiche les éléments de la suite jusqu’au premier rang n 0 tel que un 0 = 1, ainsi que la valeur
de n 0 .
Exercice 5.27 Définir une fonction récursive qui, étant donné un entier n, décide si l’écriture en base 3
de n ne comporte que des 0 et des 1. Quelle est la complexité de cette fonction ?
Exercice 5.28 ** Les tours de Hanoï. Les tours de Hanoï est un jeu inventé par Édouard Lucas en 1883.
Il est formé de sept disques de tailles différentes répartis en trois colonnes. Au départ, tous les disques
sont empilés sur la colonne de gauche par taille croissante.
hanoi.pdf
Les seuls mouvements possibles sont les déplacements d’un disque situé au sommet d’une colonne vers
le sommet d’une autre colonne, à condition que la colonne d’arrivée soit vide ou que le disque déplacé
soit plus petit que son sommet. On note n -> n' le déplacement d’un disque de la colonne n vers la
colonne n'. Le but du jeu est de déplacer tous les disques vers la colonne de droite.
hanoi2.pdf
Écrire un programme qui affiche une solution du jeu sous la forme d’une suite de mouvements.
Indication : dans une variante, le jeu n’est formé que de six disques. Si l’on sait résoudre le jeu à six disques,
comment résoudre le jeu à sept disques ?