Exercices corrigés sur les fonctions récursives-TD3-
Exercice 1
É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 est obtenu de n premiers nombres naturels.
Exemple :
k = 2, n = 3
1 2 ; 1 3 ; 2 3
k = 5, n = 5
1 2 3 4 5
1 2 ; 1 3 ; 2 3
k = 5, n = 5
1 2 3 4 5
L'idée est de créer un tableau de longueur k. Le tableau stocke la séquence en cours.
Pour chaque position dans un 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.
Pour chaque position dans un 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.
def afficher(donnees, k):
for i in range(k):
print(donnees[i], end=" ")
print()
def Sequence(n, k, taille, donnees):
# si la taille de la séquence est devenue k
# afficher la séquence
if (taille == k):
afficher(donnees, k,)
return
# position actuelle
# Si taille est égal à 0, il n'y a pas d'éléments précédents dans donnees[]
# alors commencez à mettre les nouveaux nombres avec 1
# Si longueur n'est pas 0, commencez à partir de la valeur
# de l'élément précédent+1.
i = 1 if(taille == 0) else (donnees[taille - 1] + 1)
taille += 1
# Mettez tous les nombres (qui sont plus grands que l'élément précédent)
# à la nouvelle position.
while (i <= n):
donnees[taille - 1] = i
Sequence(n, k, taille, donnees)
i += 1
# C'est important. La variable 'len' est partagée entre tous les appels récursives.
# Sa valeur doit être diminuée avant la prochaine itération
taille -= 1
k = 3
n = 7
donnees = [0]*k
taille = 0
Sequence(n, k, taille, donnees)
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
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 épuisés. Les tableaux générés devraient se terminer par un élément de B.
Exemple :
A = {10, 15, 25} ; B = {1, 5, 20, 30}
10 20
10 20 25 30
10 30
15 20
15 20 25 30
15 30
25 30
10 20
10 20 25 30
10 30
15 20
15 20 25 30
15 30
25 30
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".
def afficher(donnees, k):
for i in range(k):
print(donnees[i], end=" ")
print()
def Generer_tableaux(A, B, C, i, j, m, n, taille, drapeau):
if (drapeau): # ajouter un élément valid de A
if (taille):
afficher(C, taille+1)
# parcourir les éléments à partir de l'indice i
for k in range(i, m):
# ajouter le premier élément
if (not taille):
C[taille] = A[k]
Generer_tableaux(A, B, C, k+1, j, m, n, taille, not drapeau)
else:
# parcourir les éléments à partir de l'indice i
if (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 valid de A
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)
A = [10, 15, 25]
B = [5, 20, 30]
n = len(A)
m = len(B)
C = [0]*(n+m+1)
Generer_tableaux(A, B, C, 0, 0, m, n, 0, True)
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa
