Empilement de cylindres

Vous avancez prudemment sur une corniche le long d'une falaise ; vous devez accéder au sommet de la paroi.

Vous tombez finalement sur un renfoncement. Au fond de cette petite grotte se trouve un magnifique empilement de quatre gros disques de pierre ! En déplaçant cette pile de disques sur la corniche, vous pourrez l'escalader et atteindre le haut de la falaise.

L'empilement est malheureusement très lourd, même pour votre robot : celui-ci ne peut porter qu'un seul disque à la fois. De plus, il semble évident qu'un disque ne pourra pas supporter un disque plus gros que lui. Moyennant cela, il va vous falloir reformer l'empilement à l'entrée de la grotte, dans un espace très exigu.

Ce que doit faire votre programme :

On peut considérer qu'il y a trois zones dans la grotte :

zone 1 : le fond, où se trouvent les quatre cylindres, empilés du plus large au plus étroit ;
zone 2 : le centre, où vous pouvez placer temporairement des disques les uns au-dessus des autres ;
zone 3 : l'entrée de la grotte, où vous devez reformer l'empilement complet.

Le but est de déplacer tous les disques de la zone 1 à la zone 3 en respectant ces deux règles :

on ne peut déplacer qu'un disque à la fois, car ils sont très lourds ;
on ne peut jamais poser un disque sur un disque plus petit que lui, car sinon l'empilement s'effondrerait !

Commandes pour cet exercice

Le robot peut exécuter cette instruction :

Déplacer zoneSource -> zoneDestination

Lorsqu'il la reçoit, le robot prend le disque se situant au sommet de la zone désignée par zoneSource et le place au sommet de la zone désignée par zoneDestination (au sol si la zone est vide).

Pour identifier une zone, écrivez à la place de zoneSource et zoneDestination le numéro de la zone concernée.

En Python, l'instruction s'écrit :

deplacer(zoneSource, zoneDestination)

N'oubliez pas d'inclure la ligne suivante en haut de votre programme pour l'utiliser :

from robot import *

En guise d'exemple, voici un programme qui effectue quelques déplacements : de la zone 1, il déplace le premier disque dans la zone 3 et le deuxième dans la zone 2 ; puis il remet le premier dans la zone 1.

from robot import *
deplacer(1, 3)
deplacer(1, 2)
deplacer(3, 1)

On a ainsi pu isoler le deuxième disque de l'empilement. Par contre, le programme suivant est invalide, car il construit un empilement instable dans la zone 2 :

from robot import *
deplacer(1, 2)
deplacer(1, 2)

Afficher/cacher les programmes minimaux à compléter

Chargement de l'éditeur…

Éditer son programme

Tester son programme (interface minimale — éditeur de tests)

Avant de soumettre, testez votre programme en lui fournissant une entrée ci-dessous :

Avant de soumettre, testez votre programme sur les exemples du sujet et sur vos propres tests :

Retour à l'éditeur interactif

Conseils automatiques

0 conseil demandé sur 2 disponibles :

Pour vous inspirer, vous pouvez expérimenter l'énigme avec de vrais objets : vous pouvez par exemple découper 4 bouts de papier de taille différente, et les déplacer sur une table en respectant les règles de l'énigme pour voir ce que vous pouvez obtenir.

Une fois que vous avez trouvé la solution, il ne vous reste plus qu'à écrire les différentes étapes dans votre programme !
Pour déplacer le plus gros cylindre, il faut d'abord déplacer les 3 cylindres les plus petits dans la seconde zone, c'est-à-dire arriver à cette situation :

Essayez donc de commencer par déplacer seulement 3 cylindres !

Poser une question

Comment ça marche ?

Si malgré les conseils automatiques vous n'arrivez plus à avancer, n'hésitez pas à poser une question. Les utilisateurs et utilisatrices qui ont déjà résolu ce sujet ou les entraîneurs de France-IOI vous apporteront de l'aide. Ils ne vous donneront pas la solution mais seulement des astuces et des indications pour vous accompagner dans la réalisation de votre programme et vous permettre d'être plus autonome dans la suite de votre progression.

Les personnes qui vous aideront pourront voir toutes vos soumissions de l'onglet Activité ainsi que votre code dans l'éditeur. Vous n'avez donc pas besoin de copier-coller votre code dans votre message, ni les erreurs que vous avez obtenues. Si vous n'avez fait aucune soumission, assurez-vous que vous avez mis dans l'éditeur le programme que vous souhaitez présenter.

Visible par : les personnes ayant déjà résolu le sujet uniquement les entraîneurs

Formatage

Cliquez sur une émoticône pour l'insérer (provenance) :
:)) :'( ?:, :8) |x| 0:) ^:D

Cliquez sur le nom d'un langage pour insérer les balises de mise en forme autour du texte sélectionné :
C, C++, Pascal, OCaml, Java, JavaScool, Python, pseudo-code, entrée, sortie, erreurs.

Pour formater du texte, insérez les symboles indiqués ou cliquez sur le texte ci-dessous :
```code``` ***gras*** ///italique/// ___souligné___ ###~~barré~~### %%%grand%%% ^^^^exposant^^^ ,,,_indice,,,

Pour insérer une image, écrivez sur une ligne :
Image:https://lien/vers/l-image

Pour qu'un lien soit cliquable, placez-le seul sur une ligne, par exemple :
https://www.france-ioi.org/

Pour indenter une citation :
> Ceci a été dit plus haut.

Pour créer une liste :
- Élement avec puce
# Élément avec numéro

Il est aussi possible de construire des tableaux. Le texte suivant :

| ///iCar/// | ///texte[iCar]/// | Sortie |
| 0 | O | <cout>O</cout> |
| 1 | K | <cout>OK</cout> |

deviendra :

iCar	texte[iCar]	Sortie
0	O	↳ O
1	K	↳ OK

Remarque : vous pouvez configurer les options de votre compte afin de recevoir automatiquement un courriel lorsque quelqu'un répondra à votre demande d'aide.

Total des points obtenus sur ce sujet : 70.

Sujet commencé le 07/10/2024 à 23 h 04.

(0) Soumission n° 1 le 07/10/2024 à 23 h 07 en Python

from robot import *
deplacer(1, 3)
deplacer(1, 2)
deplacer(3, 2)
deplacer(1, 3)

Test 1	Échec	Message de l'évaluateur : [ ["startSimu"], ["deplacer", "1", "3"], ["deplacer", "1", "2"], ["deplacer", "3", "2"], ["deplacer", "1", "3"], ["displayMsg", "Tous les disques ne sont pas arrives en zone 3"] ] Erreur dans le résultat.	0 %

TOTAL	Échec	Vous avez réussi 0 test sur 1.	0 %

(0) Soumission n° 2 le 07/10/2024 à 23 h 11 en Python

from robot import *
deplacer(1, 2)
deplacer(1, 3)
deplacer(2, 3)
deplacer(1, 2)
deplacer(3, 1)
deplacer(3, 2)
Deplacer(1, 3)
deplacer(2, 1)

Test 1	Erreur	Erreur d'exécution. Voici ce qui a été affiché : Traceback (most recent call last): line 8 Deplacer(1, 3) NameError: name 'Deplacer' is not defined	0 %

TOTAL	Échec	Vous avez réussi 0 test sur 1.	0 %

(0) Soumission n° 3 le 07/10/2024 à 23 h 12 en Python

from robot import *
deplacer(1, 2)
deplacer(1, 3)
deplacer(2, 3)
deplacer(1, 2)
deplacer(3, 1)
deplacer(3, 2)
deplacer(1, 3)
deplacer(2, 1)

Test 1	Échec	Message de l'évaluateur : [ ["startSimu"], ["deplacer", "1", "2"], ["deplacer", "1", "3"], ["deplacer", "2", "3"], ["deplacer", "1", "2"], ["deplacer", "3", "1"], ["deplacer", "3", "2"], ["deplacer", "1", "3"], ["deplacer", "2", "1"], ["displayMsg", "Tous les disques ne sont pas arrives en zone 3"] ] Erreur dans le résultat.	0 %

TOTAL	Échec	Vous avez réussi 0 test sur 1.	0 %

Test 1

Échec

Message de l'évaluateur :

[
        ["startSimu"], 
        ["deplacer", "1", "2"], 
        ["deplacer", "1", "3"], 
        ["deplacer", "2", "3"], 
        ["deplacer", "1", "2"], 
        ["deplacer", "3", "1"], 
        ["deplacer", "3", "2"], 
        ["deplacer", "1", "3"], 
        ["deplacer", "2", "1"], 
        ["displayMsg", "Tous les disques ne sont pas arrives en zone 3"]
]

Erreur dans le résultat.

0 %

TOTAL

Échec

Vous avez réussi 0 test sur 1.

0 %

(100) Soumission n° 4 le 07/10/2024 à 23 h 15 en Python

from robot import *
deplacer(1, 2)
deplacer(1, 3)
deplacer(2, 3)
deplacer(1, 2)
deplacer(3, 1)
deplacer(3, 2)
deplacer(1, 2)
deplacer(1, 3)
deplacer(2, 3)
deplacer(2, 1)
deplacer(3, 1)
deplacer(2, 3)
deplacer(1, 2)
deplacer(1, 3)
deplacer(2, 3)

Test 1	Succès	[ ["startSimu"], ["deplacer", "1", "2"], ["deplacer", "1", "3"], ["deplacer", "2", "3"], ["deplacer", "1", "2"], ["deplacer", "3", "1"], ["deplacer", "3", "2"], ["deplacer", "1", "2"], ["deplacer", "1", "3"], ["deplacer", "2", "3"], ["deplacer", "2", "1"], ["deplacer", "3", "1"], ["deplacer", "2", "3"], ["deplacer", "1", "2"], ["deplacer", "1", "3"], ["deplacer", "2", "3"], ["displayMsg", ""] ] Exécuté en 0,07 seconde.	100 %

TOTAL	Succès	Félicitations, vous avez résolu ce problème !	100 %

Test 1

Succès

[
        ["startSimu"], 
        ["deplacer", "1", "2"], 
        ["deplacer", "1", "3"], 
        ["deplacer", "2", "3"], 
        ["deplacer", "1", "2"], 
        ["deplacer", "3", "1"], 
        ["deplacer", "3", "2"], 
        ["deplacer", "1", "2"], 
        ["deplacer", "1", "3"], 
        ["deplacer", "2", "3"], 
        ["deplacer", "2", "1"], 
        ["deplacer", "3", "1"], 
        ["deplacer", "2", "3"], 
        ["deplacer", "1", "2"], 
        ["deplacer", "1", "3"], 
        ["deplacer", "2", "3"], 
        ["displayMsg", ""]
]

Exécuté en 0,07 seconde.

100 %

TOTAL

Succès

Félicitations, vous avez résolu ce problème !

100 %

Histoire

Vous avez réussi à déplacer tous les disques et grimpez alors plus haut dans la falaise. Vous arrivez maintenant tout près du sommet de la montagne ! Vous ne savez pas ce qui vous attend et avancez donc tout doucement.

Algorithme

Pour résoudre un problème comme celui-là, il est utile de commencer par étudier des exemples plus petits.

Supposons que l'on ait un seul disque.

On peut alors résoudre le problème très facilement en déplaçant le disque de la zone 1 à la zone 3. Nous pouvons le noter de cette façon :

1 -> 3

Supposons que l'on ait 2 disques.

La séquence suivante permet de résoudre le problème :

-> 2
-> 3
-> 3

Supposons que l'on ait 3 disques.

Pour bouger le plus grand disque, il faut d'abord déplacer les deux autres sur la deuxième zone. Il s'agit donc de déplacer une pile de deux disques d'une zone vers une autre — c'est le problème que l'on vient de résoudre juste avant ! Nous l'avons fait vers la zone 3 ; nous voulons à présent déplacer les deux disques vers la zone 2 pour pouvoir mettre le dernier dans la zone 3.

Il suffit donc de reprendre les mêmes déplacements, en permutant les rôles des zones 2 et 3 ; donc en échangeant les deux numéros dans les instructions. Cela correspond à :

-> 3
-> 2
-> 2

À ce stade, on peut alors bouger le grand disque vers la zone 3.

1 -> 3

Enfin, on peut ramener les deux autres disques, en adaptant encore une fois la solution du problème avec deux disques, cette fois en permutant les rôles des zones 1 et 2.

-> 1
-> 3
-> 3

Et maintenant, avec 4 disques.

On va déplacer les 3 disques du haut sur la deuxième tour, bouger le plus grand en zone 3, puis déplacer les 3 disques au-dessus du grand. Pour déplacer une pile de 3 disques, on utilise la méthode développée ci-dessus.

Programme

Pour clarifier, on a séparé le programme en 3 phases : déplacer en zone 2 les trois plus petits disques, puis déplacer le plus grand, et enfin déplacer à nouveau les trois petits disques.

Déplacer 1 -> 2
Déplacer 1 -> 3
Déplacer 2 -> 3
Déplacer 1 -> 2
Déplacer 3 -> 1
Déplacer 3 -> 2
Déplacer 1 -> 2
Déplacer 1 -> 3
Déplacer 2 -> 3
Déplacer 2 -> 1
Déplacer 3 -> 1
Déplacer 2 -> 3
Déplacer 1 -> 2
Déplacer 1 -> 3
Déplacer 2 -> 3

#include <stdio.h>
#include "robot.h"
int main()
{
   deplacer(1, 2);
   deplacer(1, 3);
   deplacer(2, 3);
   deplacer(1, 2);
   deplacer(3, 1);
   deplacer(3, 2);
   deplacer(1, 2);
   deplacer(1, 3);
   deplacer(2, 3);
   deplacer(2, 1);
   deplacer(3, 1);
   deplacer(2, 3);
   deplacer(1, 2);
   deplacer(1, 3);
   deplacer(2, 3);
}

#include <iostream>
#include "robot.h"
using namespace std;
int main()
{
   deplacer(1, 2);
   deplacer(1, 3);
   deplacer(2, 3);
   deplacer(1, 2);
   deplacer(3, 1);
   deplacer(3, 2);
   deplacer(1, 2);
   deplacer(1, 3);
   deplacer(2, 3);
   deplacer(2, 1);
   deplacer(3, 1);
   deplacer(2, 3);
   deplacer(1, 2);
   deplacer(1, 3);
   deplacer(2, 3);
}

program Solution;
uses Robot;
begin
   deplacer(1, 2);
   deplacer(1, 3);
   deplacer(2, 3);
   deplacer(1, 2);
   deplacer(3, 1);
   deplacer(3, 2);
   deplacer(1, 2);
    
   deplacer(1, 3);    
   
   deplacer(2, 3);
   deplacer(2, 1);
   deplacer(3, 1);
   deplacer(2, 3);
   deplacer(1, 2);
   deplacer(1, 3);
   deplacer(2, 3);
end.

open Robot;;
deplacer 1 2;
deplacer 1 3;
deplacer 2 3;
deplacer 1 2;
deplacer 3 1;
deplacer 3 2;
deplacer 1 2;
 
deplacer 1 3;
deplacer 2 3;
deplacer 2 1;
deplacer 3 1;
deplacer 2 3;
deplacer 1 2;
deplacer 1 3;
deplacer 2 3;

import static algorea.Robot.*;
class Main {
   public static void main(String[] args) {
      deplacer(1,2);
      deplacer(1,3);
      deplacer(2,3);
      
      deplacer(1,2);
      
      deplacer(3,1);
      deplacer(3,2);
      deplacer(1,2);
      
      
      deplacer(1,3);
      
      
      deplacer(2,3);
      deplacer(2,1);
      deplacer(3,1);
      
      deplacer(2,3);
      
      deplacer(1,2);
      deplacer(1,3);
      deplacer(2,3);
   }
}

void main()
{
   deplacer(1,2);
   deplacer(1,3);
   deplacer(2,3);
   
   deplacer(1,2);
   
   deplacer(3,1);
   deplacer(3,2);
   deplacer(1,2);
   
   
   deplacer(1,3);
   
   
   deplacer(2,3);
   deplacer(2,1);
   deplacer(3,1);
   
   deplacer(2,3);
   
   deplacer(1,2);
   deplacer(1,3);
   deplacer(2,3);
}

from robot import *
deplacer(1, 2)
deplacer(1, 3)
deplacer(2, 3)
deplacer(1, 2)
deplacer(3, 1)
deplacer(3, 2)
deplacer(1, 2)
deplacer(1, 3)
deplacer(2, 3)
deplacer(2, 1)
deplacer(3, 1)
deplacer(2, 3)
deplacer(1, 2)
deplacer(1, 3)
deplacer(2, 3)

Un peu de culture

Le problème des tours de Hanoï est un grand classique. Publié en 1892, il est dû au mathématicien français Édouard Lucas. Les tours de Hanoï sont souvent utilisées en informatique pour présenter la récursivité, une notion fondamentale que l'on approfondira par la suite. Si vous continuez à avancer dans le cours, vous serez bientôt capable d'écrire en moins de 10 lignes un programme qui résout le problème des tours de Hanoï pour un nombre quelconque de disques !