Insertion

Résolu
Anna -  
 Anna -
Bonjour,

soit l'exercice suivant:

Etant donné un tableau A de n nombres triés par ordre croissant. Ecrire un algorithme qui permet de lire un réel R et l’insérer dans sa bonne position. Le résultat sera un deuxième tableau B de longueur (n+1) et qui est également trié par ordre croissant.

Pour le faire est ce que je dois utiliser 2 compteurs ou bien un seul compteur est suffisant pour le parcours, comme suit : 


Procédure Insertion(A : Tab1; R : Entier; Var B : Tab2)
Var
i : Entier
Début
i <-- 1
TantQue (A[i] <= R) et (i <= n) Faire
B[i]<-- A[i]
i<-- i + 1
FinTQ
B[i] <-- R
i<-- i + 1
TantQue (i <= n) Faire
B[i]<-- A[i]
i<-- i + 1
FinTQ
Fin

2 réponses

Réponse 1 / 2
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Bonjour,

Quel rapport entre ton exercice et ton algorithme ?

Sinon pour le parcours un seul compteur devrait suffir, en revanche tu auras besoin d'au moins deux autres variables pour stocker le résultat.
0
Anna
 
Merci pour votre réponse et désolé pour la confusion ..
l'exercice est:
Ecrire un algorithme qui permet de lire un réel R et l’insérer dans sa bonne position. Le résultat sera un deuxième tableau B de longueur (n+1) et qui est également trié par ordre croissant.
est ce que la correction ci-dessus est correcte ?
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Ok, et non, l'algo ci-dessus n'est pas correct.

La dernière boucle est fausse car elle ne prends pas en compte l'insertion de R dans B qui devrait tout décaler d'une position.
0
Anna
 
après l'insertion de R le compteur a été incrémenté i<-- i+1 donc la dernière boucle va commencer de la nouvelle i pour terminer le reste du tableau, si non, est ce que je dois utiliser un 2ème compteur pour le tableau B ?
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
Imaginons que i=5 lorsque tu fais B[5] <-- R, c'est à dire que tu as fait B[4] <-- A[4]
Si après tu incrémentes à nouveau i, tu vas faire B[6]<-- A[6]... où est passé A[5] ?
0
Anna
 
Et si je le modifie comme suit ? 


Procédure Insertion(A : Tab1; R : Entier; Var B : Tab2)
Var
i,j : Entier
Début
i <-- 1
TantQue (A[i] <= R) et (i <= n) Faire
B[i]<-- A[i]
i<-- i + 1
FinTQ
B[i] <-- R
j<-- i + 1
TantQue (j <= n) Faire
B[j]<-- A[i]
j<-- j+1
i<-- i + 1
FinTQ
Fin



0
Réponse 2 / 2
Anna
 
Je m'excuse, mais au niveau de l'énoncé de l'exercice,(
Etant donné un tableau A de n nombres triés par ordre croissant. Ecrire un algorithme qui permet de lire un réel R et l’insérer dans sa bonne position. Le résultat sera un deuxième tableau B de longueur (n+1) et qui est également trié par ordre croissant.)

il me demande un algorithme et pas une procédure, aussi la taille du 2ème tableau est différent de la 1er, ça veut dire, qu'il y a encore des fautes au niveau de ma correction.
Donc,svp, est ce que ça devient correcte de la façon suivante : 


Algorithme Insertion
Constante
          n=10
          m=11
Types 
          Tab1= tableau[1..n] de Entier
          Tab2= tableau[1..m] de Entier

Variables
          A: Tab1
          B: Tab2
          i,j,R: Entier
Debut

Ecrire (" saisir un entier:")
Lire (R)
i <-- 1
TantQue (A[i] <= R) et (i <= n) Faire
B[i]<-- A[i]
i<-- i + 1
FinTQ
B[i] <-- R
i<-- i + 1
TantQue (i <= m) Faire
B[i+1]<-- A[i]
i<-- i+1
FinTQ
Fin


S'il y a encore des fautes, qui peut me les indiquer svp et merci d'avance.
0