Insertion

Résolu
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

  1.  KX Modérateur
    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
    1. 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
    2. KX Modérateur
      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
    3. 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
    4. KX Modérateur
      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
    5. 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
  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