Examen 2015 question 13

Examen 2015 question 13

by Luna Justine Godier Gallay -
Number of replies: 5

Bonjour, 

je me demandais pourquoi dans la question sur les etats intermediaires de L, a la sortie de la boucle avec i=2  L ne vaut pas (1,2,4,7,3) puisque quand i =2, et j=3, L(2) > L(3) donc les valeurs de 3 et 4 devraient s'inverser tel que L(2) devienne 3 et quand j=5, L(2) est sup a L(5) donc elles s'inversent et donnent (1,2,4,7,3).

Pour illustrer ma question, je met en dessous mon raisonnement.

t=5

  1. pour i=1
    L(1) < L(2)
    L(1) < L(3)
    L(1) < L(4)
    L(1) > L(5) donc on inverse et L vaut (1,4,3,7,2)

  2. pour i=2
    L(2) > L(3) donc inverse et L vaut (1,3,4,7,2) et L(2) vaut 3
    L(2) < L(4)
    L(2) > L(5) donc inverse et L vaut (1,2,4,7,3)

  3. pour i=3
    L(3) < L(4) 
    L(3) > L(5) donc inverse et L vaut (1,2,3,7,4)

  4. pour i=4
    L(4) > L(5) donc inverse et L vaut (1,2,3,4,7
Mes etats intermediaires sont donc 

  1. (2 4 3 7 1)
  2. (1 4 3 7 2)
  3. (1 2 4 7 3)
  4. (1 2 3 7 4)
  5. (1 2 3 4 7)

Merci d'avance pour votre aide







In reply to Luna Justine Godier Gallay

Re: Examen 2015 question 13

by Cédric Viaccoz -

Bonjour,


Ce que tu n'as pas pris en compte dans ton raisonnement, c'est que qu'on inverse les éléments de la liste uniquement quand la boucle interne "Pour j de i+1 à t" a terminé son exécution. Les lignes "b ← L[i];  L[i] ← L[k]; L[k] ← b" sont en dehors de cette boucle, et ne se déclenchent qu'à la fin de son exécution. Ce qui fait que  pour i=2 tu obtiens ce déroulement :

  • L(2) > L(3) donc k ← j ce qui fait k == 3
  • L(3) < L(4)
  • L(3) > L(5) donc k ← j à nouveau ce qui fait que k == 5
  • On sort de la boucle vu que j == 5 == t
  • On échange maintenant les valeurs de L(i) avec L(k), donc L(2) avec L(5)
  • On avait (1 4 3 7 2), en échangeant L(2) et L(5), nous obtenons (1 2 3 7 4), comme indiqué dans le corrigé.

In reply to Luna Justine Godier Gallay

Re: Examen 2015 question 13

by Jean-Cédric Chappelier -

> pour i=2
> L(2) > L(3) donc inverse et L vaut (1,3,4,7,2) et L(2) vaut 3

Non : l'inversion est HORS de la boucle en j, pas dedans...