Fusion
Résolu
Anna
-
Anna -
Anna -
Bonjour,
Je veux vérifier la correction d'un exercice, soit l'exercice suivant :
Ecrire une procédure qui permet de fusionner deux tableaux triés A et B contenant respectivement n et m éléments. Le résultat est un tableau trié C à (n+m) éléments.
la correction est :
la question qui se pose: à quoi sert la dernière partie de la procédure :
Si c'est pour continuer le remplissage du tableau pourquoi on n'a pas initialiser les compteurs de nouveau ?
Qui peut m'expliquer SVP.
Je veux vérifier la correction d'un exercice, soit l'exercice suivant :
Ecrire une procédure qui permet de fusionner deux tableaux triés A et B contenant respectivement n et m éléments. Le résultat est un tableau trié C à (n+m) éléments.
la correction est :
Procédure Fusion(A : Tab1 ; B : Tab2 ; Var C : Tab3)
Var
i, j, k : Entier
Début
i <-- 1 j <-- 1 k<-- 1
TantQue (i <= n) et (j <= m) Faire
Si (A[i] <= B[j]) Alors
C[k]<--A[i]
i<--i + 1
k<--k + 1
FinSi
Si (B[j] <= A[i]) Alors
C[k]<--B[j]
j<--j + 1
k<--k + 1
FinSi
FinTQ
TantQue (i <= n) Faire
C[k]<--A[i]
i<--i + 1
k<--k + 1
FinTQ
TantQue (j <= m) Faire
C[k]B[j]
j<--j + 1
k<--k + 1
FinTQ
Fin
la question qui se pose: à quoi sert la dernière partie de la procédure :
TantQue (i <= n) Faire
C[k] <-- A[i]
i <-- i + 1
k <-- k + 1
FinTQ
TantQue (j <= m) Faire
C[k] <-- B[j]
j<-- j + 1
k<-- k + 1
FinTQ
Fin
Si c'est pour continuer le remplissage du tableau pourquoi on n'a pas initialiser les compteurs de nouveau ?
Qui peut m'expliquer SVP.
1 réponse
-
Bonjour,
Il faut bien comprendre qu'une seule de ces deux boucles sera utilisée.
La boucle principaleTantQue (i <= n) et (j <= m)
gère les cas où il reste des valeurs dans les deux tableaux, mais elle ne permet pas de gérer le cas où l'un des deux tableaux est vide (ce qui arrive à la fin de l'algo)
Si le tableau B est vide avant A, il faut encore remplir le reste du tableau A dans le résultat C, ce que l'on fait avecTantQue (i <= n)
Si par contre c'est le tableau A qui est vide en premier, le tableau B sera vidé dans le résultat C grâce à la boucleTantQue (j <= m)
