Sujet NSI — Terminale — Métropole — Bac 2024

EXERCICE 1 (6 points) Cet exercice porte sur les listes de listes ainsi que la programmation orientée objet. Le solitaire bulgare est un jeu de cartes dans lequel on forme des piles de cartes dont seul le nombre de cartes est important. On dispose au départ les cartes sur une seule pile. À chaque tour, on prend une carte de chaque pile et on forme une nouvelle pile à l’aide de ces cartes. Quand une pile a été vidée, on considère qu’elle disparait. L’ensemble des tailles des piles est appelé l’état et on peut le représenter par une liste triée d’entiers dans l’ordre croissant. Par exemple, si les piles contiennent respectivement 4, 6 et 10 cartes, elles seront représentées par la liste . Pour passer à l’étape d’après, on pioche la [4, 6, 10] carte au sommet de chacune de ces piles. On pioche ainsi trois cartes et les piles sont de tailles respectives 3, 5 et 9. On ajoute les trois cartes sur une nouvelle pile et on obtient alors quatre piles de tailles 3, 3, 5 et 9, représentées par la liste [3, 3, 5, 9]. On pourra noter cet enchainement d’état. [4, 6, 10] → [3, 3, 5, 9] Si le jeu de départ comporte 15 cartes, on commence avec une unique pile représentée par . On ne peut piocher qu’une carte, ce qui amène aux deux piles . En [15] [1, 14] continuant, on pioche deux cartes, se faisant la pile de taille 1 est vidée alors qu’on rajoute une pile de taille 2. La situation est alors . On a donc l’enchainement [2, 13] . [15] → [1, 14] → [2,13] Si on continue, la partie se déroule ainsi : [15] → [1, 14] → [2, 13] → [1, 2, 12] → [1, 3, 11] → [2, 3, 10] → [1, 2, 3, 9] → [1, 2, 4, 8] → [1, 3, 4, 7] → [2, 3, 4, 6] → [1, 2, 3, 4, 5] → [1, 2, 3, 4, 5] etc. On constate que l’état se réduit sur lui-même : on pioche cinq [1, 2, 3, 4, 5] cartes, on vide ainsi la première pile et on se ramène à des piles de taille 1, 2, 3 et 4 auxquelles on rajoute cette nouvelle pile de cinq cartes. On retombe alors sur [1, 2, . On dit que l’état est stable. 3, 4, 5]