Exercices - La récursivité¶

Notebook¶

À télécharger

Téléchargez l'archive ZIP suivante, puis dézippez-la dans votre H:\Travail :

Notebook_Recursivite.ipynb - Notebook Jupyter, nécessite une connexion à internet pour le chargement des images.
recursivite_notebook.zip - Archive contenant le notebook Jupyter et fichiers images associés, peut être utilisé sans connexion à internet.

Exercice : Les tours de Hanoï¶

Source : https://www.codingame.com/playgrounds/56923/apprendre-les-bases-de-python-pour-reussir-en-n-s-i-/tours-de-hanoi.

Les tours de Hanoï est un casse-tête composé de trois tours et une pile de disques rangés du plus grand au plus petit comme sur la photo ci-dessous :

Le but est de déplacer la pile de disques sur la tour de droite en ne déplaçant à chaque fois qu'un seul disque et un disque ne peut pas être posé sur un disque plus petit. Voici une animation de ce qu'il faut faire dans le cas où il y a 4 disques.

Vous pouvez consulter Wikipédia par exemple pour plus d'informations.

Nous allons voir qu'il est très simple de créer un programme récursif qui nous dit quoi faire pour résoudre le problème. Tout d'abord on appelle les tours A, B et C. On appelle n le nombre de disque présents au départ dans la tour A. Pour déplacer tous les disques de la tour A vers la tour C, on peut raisonner comme suit :

On déplace n-1 disques de A vers la tour B
On déplace le dernier disque de A vers C
On déplace les n-1 disques de B vers C

L'astuce ici est de créer une fonction hanoi qui prend 4 paramètres : hanoi(n,debut,inter,fin) où n est le nombre de disques à déplacer, debut est la tour de départ de nos n disques, inter est la tour intermédiaire que l'on peut utiliser pour déplacer et fin est la tour ou doivent se trouver les n disques au final.

Ainsi, on va initialement appeler hanoi(n,"A","B","C"), et lorsque l'on voudra déplacer les n-1 disques de A vers B, on appelera hanoi(n-1,"A","C","B") .

Exercice

Écrire cette fonction récursive hanoi(n,debut,inter,fin) de manière à afficher (avec print) à chaque étape le déplacement à effectuer sous la forme "A B" pour un déplacement de la tour "A" vers la tour "B" par exemple.

On souhaite :

donner en entrée : (n,"A","B","C") où n est un entier.
obtenir en sortie : Les instructions à suivre pour déplacer les n disques de la tour "A" à la tour "C" donnée sous la forme "A B" pour signifier un déplacement de A vers B et affiché avec print.

Solution

###

def hanoi(n, A, B, C):bksl-nl if n > 0:bksl-nl hanoi(n-1, A, C, B)bksl-nl print(f"{A} {C}")bksl-nl hanoi(n-1, B, A, C)bksl-nlbksl-nlhanoi(3, "A", "B", "C")bksl-nl

Animation avec Tkinter

Téléchargez et exécutez ce script Python pour observer une animation des tours de Hanoï utilisant le module Tkinter de Python.

Sujets de bac¶

À télécharger

Extrait du sujet zéro B - 2023