Résolution du jeu⚓︎

Le plateau de jeu

Le plateau de jeu est composé de 3 piles. On peut créer un plateau de la manière suivante :

>>> plateau = Plateau()

On peut accéder aux piles du plateau comme pour un tableau : plateau[0], plateau[1] et plateau[2].

Après sa création, le plateau ne contient aucun disque et les 3 piles sont vides.

>>> plateau = Plateau()
>> est_vide(plateau[0]) and est_vide(plateau[1]) and est_vide(plateau[2])
True

Pour connaître le contenu de plateau, il suffit d'utiliser print :

>>> print(plateau)
vide  vide  vide

Bien entendu, on peut manipuler les 3 piles du plateau, comme n'importe quelle pile :

>>> print(plateau)
vide  vide  vide
>>> empile(plateau[0], 5)
>>> empile(plateau[0], 4)
>>> empile(plateau[2], depile(plateau[0]))
>>> print(plateau)
5  vide  4

Exercice 3

Compléter le code de la fonction nouvelle_partie qui prend en paramètre un entier nb_disques et qui renvoie un nouveau plateau sur lequel se trouve nb_disques disques empilés dans l'ordre sur la première pile du plateau. Les disques ont une taille allant de 1 à nb_disques, le plus petit étant au sommet.

Rappels sur la fonction range

range(n)

Lorsqu'on n'utilise qu'un seul paramètre avec la fonction range, on obtient un itérable qui parcourt la liste des valeurs allant de 0 à n-1.

Évaluations restantes : ∞/∞

range(de, jusqu_a)

La fonction range peut aussi prendre 2 paramètres. Dans ce cas le premier paramètre indique la valeur de départ et la valeur avant laquelle on doit s'arrêter. Ainsi range(0, n) est équivalent à range(n).

L'itérable range(a, b), où a et b sont des entiers avec \(a<b\), prendra successivement toutes les valeurs entières de l'intervalle \([a;b[\). Il y aura donc \(b-a\) tours de boucles.

Évaluations restantes : ∞/∞

range(de, jusqu_a, pas)

La fonction range peut également prendre 3 paramètres. Les deux premiers paramètres ont la même utilité que dans l'exemple précédent. Le troisième permet de modifier l'écart entre chaque valeur. Au lieu d'aller de 1 en 1, on peut aller de 2 en 2 ou de 15 en 15.

Dans l'exemple suivant, vous pouvez regarder ce qui se passe quand on part de 0 ou de 1. Vous pouvez également essayer d'autres valeurs.

Évaluations restantes : ∞/∞

Compte a rebours

Si le troisième paramètre est un nombre négatif, et que le premier paramètre est supérieur au deuxième, on obtient un compte à rebours :

Évaluations restantes : ∞/∞

Autre approche

On n'est pas obligé de rajouter directement la valeur de i (la variable de boucle) à la pile, mais on peut utiliser une formule, comme par exemple : empile(pile, i+1).

>>> plateau = nouvelle_partie(5)
>>> print(plateau)
1/2/3/4/5  vide  vide

Évaluations restantes : ∞/∞

Exercice 4

Compléter le code de la fonction deplace_1_disque qui prend en paramètres deux piles origine et cible qui déplace le disque au sommet de la pile origine vers le sommet de la pile cible. Si le déplacement n'est pas possible parce qu'il ne respecte pas les règles du jeu ou que origine est vide, il ne se passe rien.

>>> plateau = nouvelle_partie(5)
>>> deplace_1_disque(plateau[0], plateau[1])
>>> deplace_1_disque(plateau[0], plateau[2])
>>> print(plateau)
3/4/5  1  2
>>> deplace_1_disque(plateau[0], plateau[2])  # mouvement interdit
>>> print(plateau)
3/4/5  1  2

Évaluations restantes : ∞/∞

Exercice 5

Compléter le code de la fonction récursive deplace_n_disques qui prend en paramètres un entier n et trois piles origine, cible et stockage, et qui déplace les n premiers disques de la pile origine sur la pile cible en utilisant éventuellement stockage comme pile intermédiaire. On suppose que tous les déplacements nécessaires sont possibles. On ne s'intéressera pas aux cas où la fonction est appelée dans des cas incorrects.

>>> plateau = nouvelle_partie(5)
>>> deplace_n_disques(3, plateau[0], plateau[1], plateau[2])
>>> print(plateau)
4/5  1/2/3  vide

Évaluations restantes : ∞/∞

Exercice 6

Compléter le code de la fonction resolution qui prend en paramètre un plateau dans son état initial et qui fait tous les mouvements nécessaires permettant de déplacer tous les disques sur la dernière pile.

On rappelle que la fonction taille permet de connaître le nombre de disques sur une pile.

>>> plateau = nouvelle_partie(5)
>>> resolution(plateau)
>>> print(plateau)
vide vide 1/2/3/4/5

Évaluations restantes : ∞/∞

Exercice 7 (bonus)

Compléter le code de la fonction récursive nb_etapes qui prend en paramètre un entier n, qui renvoie le nombre d’étapes nécessaires pour déplacer une pile de n disques, avec n > 1. Une étape correspond au déplacement d’un disque. Il ne faut pas utiliser de piles pour cette fonction, mais juste faire le calcul.

>>> nb_etapes(30)
1073741823
>>> nb_etapes(53)
9007199254740991

Évaluations restantes : ∞/∞