Exercice 3 - Récursivité · Bac Numérique et Sciences Informatiques Nouvelle-Calédonie 2025 (jour 2)

Exercice 3 [8 points]

Cet exercice porte sur les structures de données, la programmation, les graphes.

Partie A

Le siteswap est une notation mathématique pour codifier les figures de jonglerie. Elle est aujourd'hui utilisée par des jongleurs et jongleuses dans le monde entier. Beaucoup de figures sont alors simplement désignées par leur siteswap, comme par exemple 441, 7531 ou encore 453.

On modélise le jonglage de la manière suivante: au lieu de calculer des trajectoires complexes, on considère simplement un rythme régulier sur lequel on jongle, et une balle est lancée à chacun de ses « temps ».

Les lancers sont caractérisés par un nombre entier positif, représentant simplement le nombre de « temps » au bout duquel la balle revient dans la main du jongleur et peut être relancée.

À un instant donné, on peut représenter ce qu'on appelle un état, c'est-à-dire une sorte de photographie des balles « en l'air ». On notera ces états sous forme de tableaux Python, contenant des 0 et des 1. Un 0 représente un espace vide et un 1 représente une balle.

Si on considère l'état e1 = [1, 0, 0, 1, 1, 0]: son premier élément, e1[0] vaut 1, et représente donc la balle prête à être relancée. Si e1[0] valait 0, aucune balle à relancer ne serait présente. Ensuite chaque e1[i] représente la présence ou non d'une balle qui atterrira dans la main de la jongleuse au bout de i temps.

L'état e1 ci-dessus représente donc un instant d'une figure à 3 balles, l'une est dans la main de la jongleuse, et deux autres balles sont plus haut, et retomberont dans la main dans respectivement 3 et 4 temps puisque e1[3] et e1[4] sont égaux à 1 et les autres à 0.

Comme l'indice maximal est de 5 dans le tableau, on dira que la hauteur maximale est 5.

Lorsque la jongleuse attrape la balle, elle va la relancer, dans un emplacement en l'air qui est « libre », car elle ne souhaite pas recevoir à un moment donné deux balles en même temps.

Dans l'exemple e1 = [1, 0, 0, 1, 1, 0], la jongleuse peut effectuer un lancer de 1, un lancer de 2 ou un lancer de 5, car les emplacements e1[1], e1[2] et e1[5] sont à 0, donc « libres ». Elle ne peut pas lancer un 3 ou un 4.

Si le premier élément de l'état est à 0, cela signifie que la jongleuse n'a aucune balle dans sa main à cet instant. Elle ne peut donc pas lancer de balle, et on appellera ça, par convention, un lancer « 0 ». Un lancer « 0 » n'est possible que dans cette situation.

Lorsqu'on lance une balle, elle vient se placer là où on l'a prévu, puis la gravité fait son effet et toutes les balles redescendent d'un cran.

Ainsi, si depuis l'état e1 = [1, 0, 0, 1, 1, 0] on lance un 2, on obtient l'état [0, 0, 1, 1, 1, 0] puis l'état [0, 1, 1, 1, 0, 0] après effet de la gravité:

On souhaite maintenant générer toutes les suites de lancers possibles à partir d'un état donné, c'est-à-dire tous les lancers consécutifs qu'on peut faire à partir de cet état.

Par exemple, à partir de l'état e1 = [1, 0, 0, 1, 1, 0] on peut lancer un 1, un 2 ou un 5. Si on a lancé un 1 on obtient l'état [1, 0, 1, 1, 0, 0] (on rappelle que cet état est obtenu après le lancer et l'effet de gravité) et on peut lancer un 1, un 4 ou un 5. Et de même pour les états obtenus à partir de lancers 2 ou 5.

On peut alors calculer qu'à partir de e1 on peut faire les séries de lancers de longueur 2 suivants (notés sous forme de listes Python): [1, 1], [1, 4], [1, 5], [2, 0], ou [5, 0].

On aimerait obtenir tous les lancers possibles d'une longueur donnée à partir d'un état.

Pour cela on propose la méthode suivante:

si la longueur demandée est 0, alors la seule séquence possible est la séquence vide;

sinon, on calcule quels sont les lancers possibles à partir de cet état. Pour chacun de ces lancers, on va:

calculer le nouvel état obtenu;

chercher l'ensemble des séquences possibles à partir de ce nouvel état (d'une longueur un de moins);

pour toutes ces séquences, on ajoutera le numéro du lancer au début et on la mettra dans une liste s_possibles à renvoyer au final.

Voici la fonction calcule_sequences partiellement écrite:

1 def calcule_sequences(etat, n):

2 """ etat est un état de jonglerie, n est un entier.

3 Calcule et renvoie l'ensemble des siteswaps (listes

4 d'entiers) de longueur n qu'on peut effectuer à

5 partir de cet état."""

6 if n == 0:

7 return [[]]

8 else:

9 s_possibles = []

10 l_lancers =...

11 for lancer in l_lancers:

12 etat2 =...

13 s_etat2 = calcule_sequences(etat2, n-1)

14 for...

15 s_possibles.append([lancer] +...)

16 return s_possibles

7.

Justifier qu'il s'agit d'une fonction récursive.

8.

Expliquer brièvement pourquoi elle se termine si n est un entier positif. On admet que les boucles for présentes sont bornées et donc terminent.

9.

Recopier et compléter les lignes 10, 12, 14 et 15 de cette fonction.