Génération de séquences par récursivité
La récursivité est une technique puissante pour générer toutes les combinaisons possibles de séquences répondant à certains critères. Dans cette section, nous allons explorer deux exercices classiques de génération de séquences.
Exercice 1
Séquences croissantes de longueur k
Étant donné deux entiers positifs n et k, affiche toutes les séquences croissantes de longueur k telles que les éléments de chaque séquence sont obtenus à partir des n premiers nombres naturels.
Exemple 1
Entrée
k = 2, n = 3
Sortie
1 2 1 3 2 3
Exemple 2
Entrée
k = 5, n = 5
Sortie
1 2 3 4 5
Solution - Exercice 1
L'idée est de créer un tableau de longueur k. Le tableau stocke la séquence en cours.
Pour chaque position dans le tableau, nous vérifions l'élément précédent et, un par un, mettons tous les éléments supérieurs à l'élément précédent.
S'il n'y a pas d'élément précédent (première position), nous plaçons tous les nombres de 1 à n.
fonction Sequence(n, k, taille, donnees):
si taille == k:
afficher(donnees)
retourner
debut = 1 si taille == 0 sinon donnees[taille-1] + 1
pour i de debut à n:
donnees[taille] = i
Sequence(n, k, taille + 1, donnees)def afficher(donnees, k):
"""Affiche une séquence de longueur k"""
for i in range(k):
print(donnees[i], end=" ")
print()
def Sequence(n, k, taille, donnees):
"""
Génère récursivement toutes les séquences croissantes
Paramètres:
n: nombre maximum d'éléments (1 à n)
k: longueur des séquences
taille: longueur actuelle de la séquence en cours
donnees: tableau contenant la séquence en cours
"""
# si la taille de la séquence est devenue k, afficher la séquence
if taille == k:
afficher(donnees, k)
return
# déterminer la valeur de départ pour la position actuelle
# si taille est 0 (premier élément), on commence à 1
# sinon, on commence à l'élément précédent + 1 pour garantir l'ordre croissant
i = 1 if taille == 0 else (donnees[taille - 1] + 1)
# Mettre tous les nombres (qui sont plus grands que l'élément précédent)
# à la nouvelle position
while i <= n:
donnees[taille] = i
Sequence(n, k, taille + 1, donnees)
i += 1
# Exemple d'utilisation
k = 3
n = 7
donnees = [0] * k
taille = 0
print(f"Séquences croissantes de longueur {k} avec des nombres de 1 à {n} :")
Sequence(n, k, taille, donnees)Sortie (k=3, n=7)
1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 3 4 1 3 5 1 3 6 1 3 7 1 4 5 1 4 6 1 4 7 1 5 6 1 5 7 1 6 7 2 3 4 2 3 5 2 3 6 2 3 7 2 4 5 2 4 6 2 4 7 2 5 6 2 5 7 2 6 7 3 4 5 3 4 6 3 4 7 3 5 6 3 5 7 3 6 7 4 5 6 4 5 7 4 6 7 5 6 7
Exercice 2
Génération de tableaux alternés à partir de deux tableaux triés
Soit deux tableaux triés A et B, générer tous les tableaux possibles de sorte que le premier élément est pris de A, puis de B, puis de A, et ainsi de suite dans l'ordre croissant jusqu'à ce que les tableaux soient épuisés. Les tableaux générés doivent se terminer par un élément de B.
Exemple
Entrée
A = [10, 15, 25] B = [1, 5, 20, 30]
Sortie
10 20 10 20 25 30 10 30 15 20 15 20 25 30 15 30 25 30
Explication : On génère toutes les séquences qui alternent entre A et B, en commençant par A et en terminant par B, tout en respectant l'ordre croissant.
Solution - Exercice 2
L'idée est d'utiliser la récursivité. Dans la fonction récursive, un drapeau est passé pour indiquer si l'élément en sortie doit être extrait de "A" ou de "B".
- Si le drapeau indique qu'on doit prendre un élément de A, on parcourt les éléments de A à partir de l'indice courant et on les ajoute à la séquence s'ils sont plus grands que le dernier élément.
- Si le drapeau indique qu'on doit prendre un élément de B, on parcourt les éléments de B à partir de l'indice courant et on les ajoute à la séquence s'ils sont plus grands que le dernier élément.
- On alterne le drapeau à chaque appel récursif.
def afficher(C, taille):
"""Affiche la séquence actuelle stockée dans C jusqu'à la position taille"""
for i in range(taille + 1):
print(C[i], end=" ")
print()
def generer_tableaux(A, B, C, i, j, m, n, taille, drapeau):
"""
Génère récursivement tous les tableaux alternés
Paramètres:
A, B: les deux tableaux triés
C: tableau résultat en cours de construction
i: indice courant dans A
j: indice courant dans B
m, n: longueurs des tableaux A et B
taille: longueur actuelle de la séquence dans C (index du dernier élément)
drapeau: True si on doit prendre un élément de A, False pour B
"""
if drapeau: # ajouter un élément de A
# Afficher la séquence actuelle si elle n'est pas vide
if taille >= 0:
afficher(C, taille)
# parcourir les éléments de A à partir de l'indice i
for k in range(i, m):
# si c'est le premier élément ou si l'élément est plus grand que le dernier
if taille == -1:
C[0] = A[k]
generer_tableaux(A, B, C, k + 1, j, m, n, 0, not drapeau)
elif A[k] > C[taille]:
C[taille + 1] = A[k]
generer_tableaux(A, B, C, k + 1, j, m, n, taille + 1, not drapeau)
else: # ajouter un élément de B
# parcourir les éléments de B à partir de l'indice j
for l in range(j, n):
if B[l] > C[taille]:
C[taille + 1] = B[l]
generer_tableaux(A, B, C, i, l + 1, m, n, taille + 1, not drapeau)
# Exemple d'utilisation
A = [10, 15, 25]
B = [5, 20, 30] # Note: B doit être trié, ici [5,20,30]
m = len(A)
n = len(B)
C = [0] * (m + n + 1) # Tableau résultat (assez grand pour contenir tous les éléments)
print("Tableaux alternés générés à partir de A et B :")
generer_tableaux(A, B, C, 0, 0, m, n, -1, True)Sortie
10 20 10 20 25 30 10 30 15 20 15 20 25 30 15 30 25 30
Explication du fonctionnement
La fonction récursive explore toutes les possibilités en alternant entre les deux tableaux :
- On commence toujours par prendre un élément de A (drapeau = True).
- Après avoir ajouté un élément de A, on bascule sur B (drapeau = False).
- Après avoir ajouté un élément de B, on rebascule sur A, etc.
- On affiche la séquence après chaque ajout d'un élément de A (pour avoir des séquences se terminant par B).
- On s'assure que les éléments sont ajoutés dans l'ordre croissant en vérifiant qu'ils sont plus grands que le dernier élément.
Points clés à retenir
- La récursivité est idéale pour générer toutes les combinaisons possibles de séquences.
- Il est important de bien gérer les indices et les conditions de base pour éviter les récursions infinies.
- Dans le premier exercice, on garantit l'ordre croissant en commençant à l'élément précédent + 1.
- Dans le deuxième exercice, on utilise un drapeau pour alterner entre les deux tableaux.
- Les tableaux intermédiaires doivent être dimensionnés suffisamment grand pour contenir les séquences générées.
- Ces techniques sont à la base de nombreux algorithmes de backtracking.
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.