Discussion: Tri par sélection

  1. #1
    Nouveau Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2017
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Saône et Loire (Bourgogne)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2017
    Messages : 4
    Points : 1
    Points
    1

    Par défaut 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. #2
    Nouveau Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2017
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Saône et Loire (Bourgogne)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2017
    Messages : 4
    Points : 1
    Points
    1

    Par défaut Tri par sélection

    S'il-vous-plait, j'ai besoin d'aide ...
    Je pense qu'il faut mettre nombre_aleatoire dans la première case à compléter ??

  3. #3
    Membre émérite

    Homme Profil pro
    Justicier
    Inscrit en
    avril 2006
    Messages
    620
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France

    Informations professionnelles :
    Activité : Justicier
    Secteur : Service public

    Informations forums :
    Inscription : avril 2006
    Messages : 620
    Points : 2 585
    Points
    2 585
    Billets dans le blog
    1

    Par défaut

    Citation Envoyé par Nonimamie Voir le message
    Je pense qu'il faut mettre nombre_aleatoire dans la première case à compléter ??
    C'est exact, c'est ce qui est demandé dans l'énoncé : "générer 20 nombres aléatoires".

    Pour l'algorithme de tri, cela ressemble au tri classique à bulle mais en version tordue. Pour trier il faut comparer. Le deuxième blanc correspond donc à un élément du tableau à comparer. Comme on comparer avec L1(K) et qu'on fait une boucle sur I et J, et que I=K (pour une raison qui m'échappe), dans ce cas cela devrait être L1(J).

    Enfin les deux autres blancs correspondent à une inversion. En sachant que si tu veux inverser, par exemple, A et B, tu es obligée de passer par une valeur temporaire, le principe est A=>T, B=>A, T=>B, tu devrais donc pouvoir compléter avec les valeurs attendues.

    On dirait aussi que la liste L2 ne sert à rien.

  4. #4
    Membre expert
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 474
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 474
    Points : 3 905
    Points
    3 905

    Par défaut

    salut

    le tri sélection est un trie simple et fortement documenté

    Le principe est simple : Trouver un élément specifique (le plus grand ou le plus petit), le placer a une place defini (en fin ou en début de tableau),
    recommencer avec le second specifique en excluant le premier trouvé (deja correctement placé) (le second plus grand ou plus petit),
    le placer en avant-dernière position (ou en seconde position) et ainsi de suite jusqu'à avoir parcouru la totalité du tableau.

    Voici le pseudo code

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    FONCTION max(tab[], taille)
    DEBUT
        i=0  
       i_max=0
       TANSQUE(i < taille) FAIRE
       DEBUT
            SI (tab[i] > tab[indice_max]) ALORS
                i_max = i
            FINSI
            INCREMENTE(i)
        FIN
        RETOURNE i_max;
    FIN
    
    PROCEDURE echanger(tab[], x,y)
    DEBUT
        tmp = tab[x];
        tab[x] = tab[y];
        tab[y] = tmp;
    FIN
    
    PROCEDURE tri_selection(tab[],taille)
    DEBUT
        si (taille > 1) Alors
        DEBUT     
          echanger(tab, taille-1, max(tab, taille)); 
          tri_selection(tab, taille-1);
        FIN
    FIN
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  5. #5
    Nouveau Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2017
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Saône et Loire (Bourgogne)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2017
    Messages : 4
    Points : 1
    Points
    1

    Par défaut Tri par sélection

    Alors, serait-ce cela ?? Merci d'avance pour votre réponse ...

    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

    J'espère que vous pourrez m'aider.

  6. #6
    Nouveau Candidat au Club
    Femme Profil pro
    Lycéen
    Inscrit en
    novembre 2017
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Saône et Loire (Bourgogne)

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : novembre 2017
    Messages : 4
    Points : 1
    Points
    1

    Par défaut Tri par sélection

    Voilà ce que j'ai fait :
    Merci de regarder mon algorithme et la traduction Python.

    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
    Imprimer la liste
    Fin

    Et voici la traduction :
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    for I in range(0,20):
        n=random.randit(1,20):
            L1 = append(n)
        for I in range(1,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
    imprime.liste()

Discussions similaires

  1. Réponses: 54
    Dernier message: 09/03/2013, 16h27
  2. [À télécharger] [Tri] Tri par sélection
    Par 3DArchi dans le forum Téléchargez
    Réponses: 0
    Dernier message: 06/11/2010, 20h45
  3. Tri par sélection du minimum récursif
    Par thechieuse dans le forum Pascal
    Réponses: 2
    Dernier message: 05/11/2008, 17h03
  4. problème tri par sélection
    Par scary dans le forum Général Algorithmique
    Réponses: 2
    Dernier message: 19/05/2008, 12h40
  5. Améliorer tri par sélection
    Par katrena99 dans le forum Pascal
    Réponses: 8
    Dernier message: 05/03/2007, 16h30

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo