Les coefficients binomiaux sont définis pour les entiers naturels n ≥ p ≥ 0 par :
$$C(n, p) = \dfrac{n!}{p! \, (n - p)!}$$
Le triangle de Pascal est une présentation des coefficients binomiaux sous la forme d'un triangle :
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 etc.
Ce qui correspond à :
C(0,0) = 1 C(1,0) = 1 C(1,1) = 1 C(2,0) = 1 C(2,1) = 2 C(2,2) = 1 C(3,0) = 1 C(3,1) = 3 C(3,2) = 3 C(3,3) = 1 etc.
On ne demande pas de démontrer les résultats obtenus, on considérera que les propriétés observées sont justes.
Pour convertir un nombre entier positif n de la base décimale à la base binaire, il faut effectuer des divisions euclidiennes successives du nombre n par 2 jusqu'à obtenir un quotient nul. Les restes de ces divisions, lus du dernier obtenu au premier, forment alors la représentation binaire.
Déroulez à la main les divisions euclidiennes successives pour convertir 13 en binaire (détaillez chaque division, son quotient et son reste), puis vérifiez votre résultat.
En anticipant sur l'exercice 5 de la partie B (fonction récursive binaire), dessinez la pile d'exécution de l'appel binaire(13) : chaque appel empilé correspond à une division par 2, et le dépilement reconstitue les chiffres binaires dans le bon ordre.
On cherche à écrire une version rapide de la fonction de Fibonacci, en donnant à la fonction 2 termes consécutifs de la suite en paramètres (technique vue en partie B, exercice 4). Voici une tentative :
def fibo2(n, a=0, b=1):
if n == 0:
return a
return fibo2(n - 1, a, a + b)Sans utiliser l'ordinateur, calculez à la main ce que renvoie fibo2(3) (avec les valeurs par défaut a=0 et b=1) en déroulant chaque appel. Le résultat attendu est F(3) = 2. Est-ce le cas ? Identifiez l'erreur puis corrigez la fonction sur votre cahier.
L'exemple présenté le plus souvent comme le plus percutant sur la récursivité est le problème dit des Tours de Hanoï car la solution récursive est logique, concise, élégante et ... la seule viable !
Les "Tours de Hanoï" sont une récréation mathématique classique, publiée en 1883 par Édouard Lucas, mathématicien spécialiste de la théorie des nombres, connu pour ses travaux sur les suites récurrentes dont la suite de Fibonacci et la suite de Lucas qui lui est associée.
Des moines d'un monastère indien disposent de trois tours A, B et C et de n disques troués en leur centre et de tailles différentes deux à deux.
Au départ, les n disques sont empilés sur la tour A de telle sorte que chaque disque ait un diamètre inférieur au disque immédiatement en dessous de lui. Ainsi, le plus grand disque de la tour se situe à sa base et le plus petit sur son sommet.
D'après la légende imaginée par É. Lucas, la fin du monde surviendra lorsque les moines auront terminé le transfert de 64 disques d'or de la tour A (tour initiale) vers la tour C (tour finale) en passant par la tour B (tour intermédiaire), en respectant les règles suivantes :
On peut démontrer qu'il faut au minimum 2n - 1 coups pour déplacer les n disques de la tour initiale vers la tour finale. Pour déplacer les 64 disques il faudrait donc 264 = 18 446 744 073 709 551 616 coups (ça laisse du temps devant nous)...
Vous pouvez regarder la vidéo : https://www.youtube.com/watch?v=rOnRbPKvGQg (jusqu'à 9min15s).
Pour illustrer l'inefficacité de certaines récursions, il est courant d'évoquer la suite de Fibonacci que nous avons croisée dans les exercices précédents (fiche TD1).
En reprenant le script déjà codé, utilisez le site pythontutor.com pour visualiser le nombre d'appels pour obtenir fibonacci(5), puis avec fibonacci(10). Que constatez-vous ?
Si on teste, par exemple, fibonacci(37), on va constater que c'est long pour obtenir un résultat.
Le problème de l'algorithme est le nombre d'appels récursifs effectués. On remarque que l'ordinateur passe son temps à calculer plusieurs fois les mêmes valeurs, donc l'algorithme est loin (très loin) d'être optimisé.
Si on note An le nombre d'appels récursifs nécessaires pour le calcul de Fn, on peut démontrer que le nombre d'appels est proportionnel à ((√5 + 1) / 2)n quand n tend vers l'infini (le nombre d'or !) ; la complexité de cet algorithme est donc exponentielle, et c'est l'un des pires cas possibles pour un algorithme !
Il y a alors 2 possibilités : trouver un algorithme itératif qui sera beaucoup plus rapide, ou trouver un autre algorithme récursif.
fibo_iter qui permet de calculer Fn (avec n un entier naturel).fibo2) qui permet de calculer Fn. Pour cela, on va donner un peu de mémoire à la fonction en plaçant dans ses arguments deux termes consécutifs (les 2 premiers) de la suite de Fibonacci. La fonction fibo2 aura donc 3 arguments : n, a et b (où a et b sont 2 termes consécutifs, par exemple 0 et 1 si on considère les 2 premiers).Écrire une fonction récursive binaire permettant d'obtenir la représentation binaire d'un nombre entier n (la valeur retournée sera de type str).
En déduire une fonction récursive binom qui prend en paramètres 2 entiers n et p et qui permet de calculer C(n, p), en utilisant la relation de récurrence trouvée dans la partie A (exercice 1).
Utiliser l'algorithme récursif détaillé dans la partie A (exercice 4) pour créer une fonction hanoi() qui prend 4 paramètres (le nombre de disques et les 3 tours : départ A, arrivée C et intermédiaire B) et qui permet de résoudre le problème.
On se "contentera" d'un affichage du type : "Disque de " ... " vers " ... (... = A, B ou C).
On peut trouver de nombreuses variantes de ce jeu célèbre, nous "jouerons" avec ces règles : deux joueurs A et B sont devant une table, sur laquelle on dispose n allumettes. A joue et enlève 1, 2 ou 3 allumettes. B joue ensuite et fait de même. Celui qui enlève la dernière allumette a perdu.
Quelles sont les valeurs de n pour lesquelles A peut jouer de telle sorte que quelle que soit la manière de jouer de B au tour suivant, B perde au tour d'après ? Faire un raisonnement récursif et en conclure quelles sont les valeurs de n pour lesquelles A est sûr de gagner (on pourra faire un arbre pour représenter les différentes possibilités).
joueurjoue qui prend en paramètres un entier n qui représente le nombre d'allumettes en début de partie et un str joueur (nom du joueur), et retourne le nombre d'allumettes restantes après que le joueur ait joué. On suppose qu'il joue de façon à assurer sa victoire si n est favorable, sinon il joue au hasard. La fonction permettra d'obtenir un affichage du type :
joueur1 joue reste : ...
nim qui prend en paramètre un entier n, un str joueur (défini par défaut à 'joueur1') et un entier nbcoups (défini par défaut à 0) qui compte le nombre de coups joués. Les 2 joueurs qui s'affrontent sont gérés par l'ordinateur et cherchent à gagner en utilisant la fonction joueurjoue. Elle affiche à chaque tour le nom du joueur qui joue et le nombre d'allumettes restantes en utilisant la fonction précédente. À la fin de la partie, elle doit indiquer le nom du vainqueur (celui qui doit prendre la dernière allumette étant le perdant).Exemple d'affichage :
>>> nim(10) joueur1 joue reste : 9 joueur2 joue reste : 6 joueur1 joue reste : 5 joueur2 joue reste : 3 joueur1 joue reste : 1 joueur1 gagne