Répondre à la discussion
Affichage des résultats 1 à 26 sur 26

Algorithme Tri par sélection

  1. #1
    Nonimamie

    Red face Algorithme Tri par sélection

    Bonjour,

    Je suis en Terminale S et j'ai un algorithme sur le tri par sélection ou par extraction à compléter, puis à traduire en langage Python. J'ai essayé plusieurs choses mais je n'arrive pas à remplir les blancs.

    Le but de cet algorithme est de générer 20 nombres aléatoires entre 1 et 20 de les trier et de visualiser cette liste tout au long du processus.
    Voici l'algorithme à compléter (les blancs sont représentés par zzzzzzzzz) :

    Variables : I, A, J, K : entiers L1, L2 : listes
    Entrées et initialisation :
    pour I de 1 à 20 faire
    zzzzzzzzz => L1 (I)
    fin
    Traitement et sorties :
    pour I de 1 à 19 faire
    I => K
    pour J de I+1 à 20 faire
    si zzzzzzzzz < L1 (K) alors
    J => K
    fin
    L1 (I) => zzzzzzzzz
    L1 (K) => zzzzzzzzz on échange L1 (I) avec L1 (K)
    A => L1 (K)
    I => K
    fin
    zzzzzzzzz
    fin

    J'espère que vous pourrez m'aider.
    Merci d'avance,
    Noé.

    -----


  2. Publicité
  3. #2
    Jack

    Re : Algorithme Tri par sélection

    Indente le code parce que c'est illisible ainsi présenté (utilise les balises code).

    Essaie également de préciser ce que fait cette ligne par exemple, c'est pas évident: "L1 (I) =>"

  4. #3
    Nonimamie

    Re : Algorithme Tri par sélection

    Merci pour votre réponse mais je ne comprends réellement pas ce qu'il faut ajouter dans les blancs. C'est la première année que je fais du codage, j'ai réussi le reste de l'exercice mais je bloque à cette question. Pourriez-vous m'aider davantage ?

  5. #4
    Jack

    Re : Algorithme Tri par sélection

    Ah, c'est à compléter, je n'avais pas compris cette histoire de blancs.
    Aller, je te fais la première partie:
    Code:
    pour I de 1 à 20 faire
           nombre_aleatoire => L1 (I) 
    fin
    J'ai fait le plus dur.

    Le reste doit être INDENTE comme je te l'ai expliqué. C'est d'autant plus important que tu vas devoir coder l'algorithme en python.
    Les blancs sont représentés par des zzzzzzzz.
    Code:
    pour I de 1 à 19 faire
       I => K 
       pour J de I+1 à 20 faire 
          si zzzzzzzzz < L1 (K) alors 
             J => K 
          fin 
          L1 (I) => zzzzzzzzz
          L1 (K) => zzzzzzzzz on échange L1 (I) avec L1 (K) 
          A => L1 (K) 
          I => K 
       fin 
       zzzzzzzzz
    fin
    Dernière modification par Jack ; 01/11/2017 à 11h15.

  6. #5
    LeMulet

    Re : Algorithme Tri par sélection

    Citation Envoyé par Nonimamie Voir le message
    Merci pour votre réponse mais je ne comprends réellement pas ce qu'il faut ajouter dans les blancs. C'est la première année que je fais du codage, j'ai réussi le reste de l'exercice mais je bloque à cette question. Pourriez-vous m'aider davantage ?
    Si vous n'y parvenez pas c'est que vous n'avez pas compris le principe du tri par sélection.
    L'algorithme n'est ensuite rien d'autre qu'une formalisation des tâches à effectuer.
    Voir donc pour commencer le principe :
    https://openclassrooms.com/courses/le-tri-par-selection
    Bonjour, et Merci.

  7. #6
    Nonimamie

    Re : Algorithme Tri par sélection

    Merci pour vos réponses mais je suis vraiment bloquée, j'ai besoin d'aide ...

  8. #7
    Jack

    Re : Algorithme Tri par sélection

    Essaie au moins de faire la partie échange entre L1 (I) et L1 (K):
    Code:
          L1 (I) => zzzzzzzzz
          L1 (K) => zzzzzzzzz on échange L1 (I) avec L1 (K) 
          A => L1 (K)

  9. #8
    Nonimamie

    Re : Algorithme Tri par sélection

    On a L1(I) échangé avec L1(K) ??

  10. #9
    Jack

    Re : Algorithme Tri par sélection

    Oui, c'est écrit dans ton algo partiel il me semble.

    Il faut bien faire un échange à un moment ou à un autre pour mettre un élément en place.

  11. #10
    Nonimamie

    Re : Algorithme Tri par sélection

    Et comment faire le reste ??

  12. #11
    Jack

    Re : Algorithme Tri par sélection

    Tu n'as toujours pas complété les 3 lignes permettant l'échange.

  13. #12
    Nonimamie

    Re : Algorithme Tri par sélection

    Serait-ce cela ???

    Variables : I, A, J, K : entiers L1, L2 : listes
    Entrées et initialisation :
    pour I de 1 à 20 faire
    L1(J) => L1 (I)
    fin
    Traitement et sorties :
    pour I de 1 à 19 faire
    I => K
    pour J de I+1 à 20 faire
    si L1 (J) < L1 (K) alors
    J => K
    fin
    L1 (I) => L1 (J)
    L1 (K) => L1 (I) on échange L1 (I) avec L1 (K)
    A => L1 (K)
    I => K
    fin
    zzzzzzzzz
    fin

  14. #13
    Jack

    Re : Algorithme Tri par sélection

    Code:
    L1 (I) => L1 (J)L1 (K) => L1 (I) on échange L1 (I) avec L1 (K) 
    A => L1 (K)
    Prends du papier, un crayon et une gomme et essaie. Tu verras que tu ne permutes pas L1 (I) avec L1 (K)

  15. #14
    Nonimamie

    Re : Algorithme Tri par sélection

    Je ne comprends pas pourquoi je ne permute pas L1(I) avec L1(K) grâce à cette ligne :

    L1 (K) => L1 (I) on échange L1 (I) avec L1 (K)

  16. #15
    Jack

    Re : Algorithme Tri par sélection

    Citation Envoyé par Nonimamie Voir le message
    Je ne comprends pas pourquoi je ne permute pas L1(I) avec L1(K) grâce à cette ligne :

    L1 (K) => L1 (I) on échange L1 (I) avec L1 (K)
    Non, tu ne les permutes pas. Il faut que tu échanges la donnée contenue dans L1 (I) avec celle contenue dans L1 (K).
    Toi, ce que tu fais avec cette ligne, c'est copier L1 (K) dans L1 (I). Du coup la valeur originale de L1(I) est définitivement perdue. D'où l'intérêt de la variable A.

  17. #16
    Nonimamie

    Re : Algorithme Tri par sélection

    Autrement dit,
    on a :
    Variables : I, A, J, K : entiers L1, L2 : listes
    Entrées et initialisation :
    pour I de 1 à 20 faire
    A => L1 (I)
    fin
    Traitement et sorties :
    pour I de 1 à 19 faire
    I => K
    pour J de I+1 à 20 faire
    si L1 (J) < L1 (K) alors
    J => K
    fin
    L1 (I) => L1 (J)
    L1 (K) => A
    on échange L1 (I) avec L1 (K)
    A => L1 (K)
    I => K
    fin
    zzzzzzzzz
    fin

  18. #17
    Nonimamie

    Re : Algorithme Tri par sélection

    S'il-vous-plait, j'ai besoin d'aide, c'est urgent !

  19. #18
    Jack

    Re : Algorithme Tri par sélection

    Citation Envoyé par Nonimamie Voir le message
    S'il-vous-plait, j'ai besoin d'aide
    J'essaie, mais il est hors de question que je fasse ton exercice.
    Ton code est toujours aussi mal présenté alors que je l'avais mis en forme pour que tu en fasses de même.

    Je ne vois pas comment tu vas pouvoir te sortir d'un problème de tri si tu n'arrives pas à effectuer une simple permutation de 2 valeurs, ce qui représente à mon avis ce qui peut exister de plus simple au niveau algorithmique.
    De plus, je te donne la solution de la première partie que tu remplaces par:
    Code:
    pour I de 1 à 20 faire 
        A => L1 (I) 
    fin
    C'est comme ça que tu comptes remplir le tableau avec des valeurs aléatoires? Que vaut A dans ton code?

  20. #19
    Nonimamie

    Re : Algorithme Tri par sélection

    Ceci vous semble peut-être simple mais ça ne l'est pas pour moi puisque ce n'est que ma première année. De plus, je ne vous ai jamais demandé de me donner l'exercice tout fait. Cependant, je suis une travailleuse et j'aime lorsque j'obtiens des résultats, et voilà 2 semaines que je tourne en rond ! Je tiens tout de même à vous remercier pour votre aide.

  21. #20
    Jack

    Re : Algorithme Tri par sélection

    Je vois bien que tu essaies, mais je ne sais pas trop par où commencer: je te donne un bout de code fonctionnel et tu le modifies. Je repose donc ma question: que vaut A dans le code du message #18? En quoi ce bout de code va remplir le tableau avec des valeurs aléatoires?

  22. #21
    Nonimamie

    Re : Algorithme Tri par sélection

    Serait-ce mieux comme ça ??

    Variables : I, A, J, K : entiers L1 : liste
    Entrées et initialisation :
    pour I de 1 à 20 faire
    nombre_aleatoire => L1 (I)
    fin

    Traitement et sorties :
    pour I de 1 à 19 faire
    I => K
    pour J de I+1 à 20 faire
    si L1 (J) < L1 (K) alors
    J => K
    fin
    L1 (I) => A
    L1 (K) => L1 (I) on échange L1 (I) avec L1 (K)
    A => L1 (K)
    I => K
    fin
    Ici, je sais que je dois imprimer la liste, mais je ne sais pas comment l'écrire ??
    fin

  23. #22
    Jack

    Re : Algorithme Tri par sélection

    Le code n'est toujours pas indenté C'est pas facile à suivre.

    Bon, ça y est tu as réussi la permutation.

    Ici, je sais que je dois imprimer la liste, mais je ne sais pas comment l'écrire ??
    C'est que tu n'as toujours pas compris l'algorithme. As-tu au moins essayé de l'exécuter instruction par instruction avec papier, crayon, gomme? I sert à désigner le numéro de la valeur à mettre en place dans le tableau. Donc en principe, à chaque tour de la boucle principale (celle contrôlée par I), le Ième élément doit être en place. Il n'y a plus qu'à l'afficher.

  24. #23
    Nonimamie

    Re : Algorithme Tri par sélection

    Je crois qu'il y a des erreurs dans mon programme python ... S'il-vous-plait
    Code:
    for I in range(0,20):
        n=random.randint(1,20)
        L1.append(n)
        for I in range(0,19):
            K = I
            for J in range(I+1,20):
                if L1(J)<L1(K):
                    K = J
                A = L1[I]
                L1[I] = L1[K]
                L1[K] = A
                K = I
    print(L1)

  25. #24
    Jack

    Re : Algorithme Tri par sélection

    Je ne suis pas super compétent en python. Comment sais-tu qu'il y a des erreurs? Tu as essayé ce code?
    Pour imprimer la liste, il me semble que le bon sens soit que tu imprimes les valeurs de celle-ci dans une boucle.

  26. #25
    Nonimamie

    Re : Algorithme Tri par sélection

    J'ai refait quelques modifications ... Une erreur s'affiche dans la ligne IF !
    Code:
    import random
    
    L1 = []
    
    for I in range(0,20):
        n=random.randint(1,20)
        L1.append(n)
        for I in range(0,19):
            K = I
            for J in range(I,20):
                if L1[J]<L1[K]:
                    K = J
                A = L1[I]
                L1[I] = L1[K]
                L1[K] = A
                K = I
    print(L1)

  27. #26
    Jack

    Re : Algorithme Tri par sélection

    Comme je n'arrive plus à mettre la main sur ma boule de cristal pour avoir une idée de l'erreur, j'ai dû installer python.

    L'indentation est incorrecte: une fois que la liste est initialisée, il faut revenir en marge gauche.
    Dernière modification par Jack ; 09/11/2017 à 21h52.

Discussions similaires

  1. selection naturelle versus selection sexuelle.
    Par ansset dans le forum Neuropsychologie et Psychologie
    Réponses: 21
    Dernier message: 21/12/2012, 11h31
  2. Tri par sélection
    Par Square dans le forum Programmation et langages, Algorithmique
    Réponses: 0
    Dernier message: 16/04/2011, 21h33
  3. algorithme de tri par sélection
    Par celine2 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 11/05/2009, 22h10
  4. sélection(s)
    Par Jiav dans le forum Bionique, robotique et vie artificielle
    Réponses: 3
    Dernier message: 01/12/2008, 18h31
  5. SPI selection
    Par uranie-mc dans le forum Électronique
    Réponses: 1
    Dernier message: 24/04/2008, 14h07