Fusion

Résolu/Fermé
Anna - 7 déc. 2016 à 22:46
 Anna - 7 déc. 2016 à 23:23
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 :

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.
A voir également:

1 réponse

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
7 déc. 2016 à 23:01
Bonjour,

Il faut bien comprendre qu'une seule de ces deux boucles sera utilisée.

La boucle principale
TantQue (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 avec
TantQue (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 boucle
TantQue (j <= m)
1
Donc, la correction est correcte ?
0
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
7 déc. 2016 à 23:16
Oui
0
Merci
0