Basic Pascal Tutorial/Chapter 4/Programming Assignment/fr
│
български (bg) │
English (en) │
français (fr) │
日本語 (ja) │
中文（中国大陆） (zh_CN) │
Tutoriel de Pascal Objet : Sous-programmes / Exercice
Un problème classique de récursion, enseigné dans toutes les cours d'introduction en informatique, est les tours de Hanoï. Dans ce problème, vous avez trois piquets verticaux. Il y a une tour en forme de cône sur le piquet le plus à gauche, constitué de disque en forme de donut (i.e. troués en leur centre). Par exemple, voilà à quoi ressemble une tour de quatre étages:
| | | | | | * | | *** | | ***** | | ******* | |
Les piquets sont désignés par 1, 2 et 3 de gauche à droite. Le défi consiste à bouger une tour (quelle que soit la hauteur) du piquet 1 au piquet 3. Dans le procédé, aucun disque ne doit être placé sur un disque plus petit et un seul disque (celui du dessus d'un des piquets) peut être déplacé à la fois.
Le problème semble trivial et il l'est pour 1 ou 2 disques. Pour un disque, vous le déplacez simplement du piquet au piquet 3. Pour 2 disques, déplacer le disque le plus en haut du piquet 1 au piquet 2, puis du 1 au 3 et finalement, vous déplacez le plus petit disque du 2 au 3.
Le problème devient plus dur avec 3 disques ou plus. Pour 3 disques, vous devrez bouger 1 vers 3, puis 1 vers 2, puis encore 3 vers 2. Ceci crée effectivement une tour à 2 étages sur le piquet 2. Déplacez alors le disque le plus grand : 2 vers 1, 2 vers 3, 1 vers 3.
Votre mission, si vous l'acceptez : écrire un programme qui utilise une procédure récursive pour résoudre les tours de Hanoï pour tout nombre de disques. Demandez d'abord à l'utilisateur la hauteur de la tour d'origine. Ensuite, imprimez les instructions pas à pas pour les déplacements individuels des disques d'un piquet vers un autre. Par exemple, un problème à 3 disques pourrait produire la sortie suivante :
1 vers 3 1 vers 2 3 vers 2 1 vers 3 2 vers 1 2 vers 3 1 vers 3
Comme dit dans la section sur la récursion, la récursion est un des sujets les plus difficile à comprendre. Certains regarderont ce problème et le trouverons extrêmement facile. D'autres auront des temps difficiles avec. Pourtant, une fois que vous aurez passé l'obstacle de la compréhension de la récursion, le codage réel du programme est relativement simple.
Donc, si vous souhaitez vous mettre au défi, arrêtez de lire ici. Si vous avez de petits problèmes, lisez un petit conseil.
Conseil : le problème, comme tous les problèmes récursifs, se réduit lui-même, devenant plus simple à chaque étape. Vous rappelez-vous le problème à trois disques ? D'abord, vous créez une tour à deux disques sur le piquet 2, ce qui vous permet de déplacer le disque le plus bas du piquet 1 vers le piquet 3. Ensuite vous déplacez la tour à 2 disques sur le haut du piquet 3.
C'est la même chose avec 4 disques. En premier, vous créez une tour de trois disques sur le piquet 2, puis déplacez le plus grand disque à la cheville sur 3 et déplacez la tour à trois disques sur le piquet 3. Comment créer une tour à 3 disques ? Facile. Nous savons déjà comment déplacer une tour à trois disque du piquet 1 au piquet 3. Cette fois, vous déplacez seulement du piquet 1 au piquet 2, ensuite quand le plus grand piquet est en place, vous déplacez la tour du piquet 2 au piquet 3. Dans la procédure complète, nous pouvons agir comme si le grand disque n'existe pas car il est garanti d'être plus grand que les autres et ne pose ainsi aucun problème. Utilisez seulement la solution à trois disques, en échangeant les numéros autour.
Bonne chance !
| ← | Sommaire | → |
