IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Exercice sur les tableaux


Sujet :

Algorithmes et structures de données

  1. #1
    IDE
    IDE est déconnecté
    Membre régulier Avatar de IDE
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    238
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : Belgique

    Informations forums :
    Inscription : Mai 2004
    Messages : 238
    Points : 89
    Points
    89
    Par défaut Exercice sur les tableaux
    Bonjour à tous, voici un exercice que je dois réaliser :

    Un tableau à une dimension contient des entiers égaux à 0, 1 ou 2. Ecrire un algorithme qui range les éléments de ce tableau dans un deuxième tableau de manière que les 0 soient rangés en tête, puis les 1 puis les 2. Le premier tableau ne sera parcouru qu'une seule fois. Il sera initialisé à sa déclaration et affiché

    Et voici ma solution, mais je ne sais pas si c'est une bonne chose de l'avoir fait de cette manière, merci pour vos remarques.

    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
     
    Constante MAX = 6
    Tableau entier iTableau taille MAX
    <* = {0,0,2,1,2,1} *>
    Tableau entier iEchange taille MAX
    Variable indice iI
     
    Début du traitement
     
       /* Boucle : */
       Initialisation
       Compter avec iI de 0 à 5
     
          Afficher iTableau[iI] Tab
     
       Fin de compter
     
       Fin de ligne
       Fin de ligne
     
       /* Boucle : */
       Initialisation
       Compter avec iI de 0 à 5
     
          /* Alternative : */
          Si iTableau[iI] == 0 Alors
     
    	 iEchange[0] <- 0
    	 iEchange[1] <- 0 
     
    	 /* */
          Sinon
     
    	 si iTableau[iI] == 1 Alors
     
    	    iEchange[2] <- 1
    	    iEchange[3] <- 1 
     
    	 Sinon
     
    	    si iTableau[iI] == 2 Alors
     
    	       iEchange[4] <- 2
    	       iEchange[5] <- 2 
     
    	    Fin de si
    	    Fin de si
          Fin de si
     
       Fin de compter
     
       /* Boucle : */
       Initialisation
       Compter  avec iI de 0 à 5
     
          Afficher iEchange[iI] Tab
     
       Fin de compter
     
      Attente 
     
    Fin du traitement

    Merci pour votre aide.

    Michael

  2. #2
    Membre actif
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    192
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 192
    Points : 231
    Points
    231
    Par défaut
    Ton algo ne marche que si tu as deux 0, deux 1 et deux 2. Dans les autres cas, il ne fonctionne pas.

    Essaie simplement de faire un programme qui commence par compter le nombre de 0, le nombre de 1, le nombre de 2, puis remplit le tableau de résultat sachant ces nombres.

  3. #3
    Expert confirmé
    Avatar de Hephaistos007
    Profil pro
    Enseignant Chercheur
    Inscrit en
    Décembre 2004
    Messages
    2 493
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2004
    Messages : 2 493
    Points : 4 166
    Points
    4 166
    Par défaut
    Un algorithme de tri résoud le problème : http://fr.wikipedia.org/wiki/Algorithme_de_tri

  4. #4
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Citation Envoyé par Hephaistos007
    Un algorithme de tri résoud le problème : http://fr.wikipedia.org/wiki/Algorithme_de_tri
    IDE demande explicitement que la complexité soit en O(n). Et non en O(n ln n) ou O(n²) tel un algorithme de tri classique. Par contre, un algorithme de tri comptage fonctionne (mais cela revient à ce que borisd disait)

  5. #5
    Membre éclairé
    Inscrit en
    Juin 2005
    Messages
    644
    Détails du profil
    Informations professionnelles :
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2005
    Messages : 644
    Points : 754
    Points
    754
    Par défaut
    en O(n) par exemple :
    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
     
     
    const n = 25;
    var T_initial, T_final : array[0..n-1] of byte;
    procedure ordone;
    var i : integer; n1, n2 : integer;
       begin
       for i:=0  to n-1 do T_Initial[i]:=Random(3); // ou mettre les data en question
       n1:=-1; 
       n2:=n;
       for i:=0 to n-1 do
       if T_initial[i]=0 then 
          begin 
          inc(n1); 
          T_final[n1]:=0 
          end
       else
       if T_initial[i]=2 then 
          begin 
          dec(n2); 
          T_final[n2]:=2 
          end;
       if n1 < n2-1 then for i:=n1+1 to n2-1 do 
          T_final[i]:=1;
       end;

  6. #6
    IDE
    IDE est déconnecté
    Membre régulier Avatar de IDE
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    238
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : Belgique

    Informations forums :
    Inscription : Mai 2004
    Messages : 238
    Points : 89
    Points
    89
    Par défaut Suite
    Merci pour toutes ces réponses, je suis allé sur le suite suivant :

    http://fr.wikipedia.org/wiki/Tri_comptage

    qui explique se que je voudrais faire mais je ne comprend pas bien l'algorithme, si quelqu'un pourrait me l'expliquer se serait super sympa, merci

    Michael

  7. #7
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    On sait qu'il faudra trier des entiers entre deux bornes (par exemple de 1 et 12) d'un tableau T.

    On crée un tableau Compte de taille 12 initialisé à 0. Compte[i] correspondra au nombre de i qu'il y aura dans le tableau à la fin de la première partie.

    - Dans un premier temps, il suffit donc de parcourir ton tableau T et incrémenter les bons indices de Compte. Cela revient simplement à incrémenter Compte[T[i]] pour chaque i

    - Ensuite, tu connais pour chaque entier entre 1 et 12, leurs nombres d'occurence dans T

    - Il suffit de parcourir un nouveau tableau (qui correspondra au tableau trié) et d'écrire les éléments triés (en utilisant le tableau Compte) ce qui se fait simplement en parcourant les éléments de Compte un par un.

  8. #8
    Membre éclairé Avatar de HanLee
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    738
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Mai 2004
    Messages : 738
    Points : 871
    Points
    871
    Par défaut
    C'est l'algorithme du drapeau hollandais ton truc non ? ON me l'avait posé en MPSI...

    Nous on avait pas le droit de faire du tri par comptage par contre, donc pas le droit de créer un tableau supplémentaire.

    Il fallait gérer les permutations au fur et à mesure qu'on parcourait le tableau, donc je sais pas si tu peux utiliser les dernières solutions données.

    Pour nous la méthode c'était de garder les coordonnées de la fin de la séquence de 0, de la suite des 1, et ta position. Et donc t'en déduisais les permutations à faire...

  9. #9
    Expert éminent

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Points : 6 911
    Points
    6 911
    Par défaut
    Citation Envoyé par HanLee
    C'est l'algorithme du drapeau hollandais ton truc non ?
    Oui. Voir Dijkstra, a discipline of programming.

  10. #10
    IDE
    IDE est déconnecté
    Membre régulier Avatar de IDE
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    238
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : Belgique

    Informations forums :
    Inscription : Mai 2004
    Messages : 238
    Points : 89
    Points
    89
    Par défaut Suite
    Voici se que j'ai fais mais mon résultat a un petit probleme par apport a ma déclaration de mon tableau et je ne trouve pas mon erreur

    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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
     
    Constante MAX = 5
    Tableau entier iTab taille MAX
    <* = { 4,8,7,12,1 } *>
     
    Variable indice iI,iJ
    Variable entiere iTemp
     
    Variable entiere iMIN
     
    Début du traitement
     
       /* Boucle : */
       Initialisation
     
          iMIN <- iTab[iI]
     
       Compter avec iI de 0 à MAX - 2
     
          /* Boucle : */
          Initialisation
          Compter avec iJ de 1 à MAX - 1
     
    	 /* Alternative : */
    	 Si iTab[iI] < iTab[iMIN] Alors
     
    	    iMIN <- iTab[iI]
     
    	 Fin de si
     
          Fin de compter
     
          iTemp <- iTab[iI]
          iTab[iI] <- iTab[iMIN]
          iTab[iMIN] <- iTemp
     
       Fin de compter
     
       /* Boucle : */
       Initialisation
       Compter avec iI de 0 à MAX - 1
     
          Afficher iTab[iI] Tab
     
       Fin de compter
     
       Attente
     
    Fin du traitement
    et voici mon résultat : 1 4 0 7 8

    Merci pour votre aide

    Michael

  11. #11
    Expert confirmé
    Avatar de Hephaistos007
    Profil pro
    Enseignant Chercheur
    Inscrit en
    Décembre 2004
    Messages
    2 493
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2004
    Messages : 2 493
    Points : 4 166
    Points
    4 166
    Par défaut
    Citation Envoyé par IDE
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    Tableau entier iTab taille MAX
    <* = { 4,8,7,12,1 } *>
    Je croyais que ton tableau ne contenais que 0,1 ou 2 ?!?

    Ensuite, a vu d'oeil ton algorithme ne ressemble pas à un algorithme de tri par comptage.

  12. #12
    IDE
    IDE est déconnecté
    Membre régulier Avatar de IDE
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    238
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : Belgique

    Informations forums :
    Inscription : Mai 2004
    Messages : 238
    Points : 89
    Points
    89
    Par défaut Suite
    Oui je sais mais j'ai fais des recherches sur le net pour essayer de résoudre mon petit probleme et je suis tombé sur un code en C et je l'ai transformé en pseudo code, mais je dois dire que c'est pas tres bien reussi , donc voila pourquoi je demandais un peu d'aide pour m'expliquer mon erreur.

    Michael

  13. #13
    Membre actif
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    192
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 192
    Points : 231
    Points
    231
    Par défaut
    Je pense que ton erreur c'est de ne pas savoir ce que tu fais.
    Ton problème est d'écrire un algorithme qui trie un tableau d'entiers en ne le parcourant qu'une fois, pas de copier bêtement du code trouvé sur internet, code qui ne sert même pas à ce que tu dois faire.
    Nous t'avons donné toutes les références nécessaires et même du code pour t'aider. Maintenant, tu peux faire l'effort de réfléchir 10 minutes sur nos réponses.

  14. #14
    IDE
    IDE est déconnecté
    Membre régulier Avatar de IDE
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    238
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : Belgique

    Informations forums :
    Inscription : Mai 2004
    Messages : 238
    Points : 89
    Points
    89
    Par défaut
    J'ai enfin trouvé la solution et sa fonctionne très bien, voici le 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
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
     
    Constante MAX = 6
    Tableau entier iTab taille MAX
    <* = { 0,1,1,2,0,0 } *>
    Variable entiere iI,iJ,iTemp
     
    Début du traitement
    Initialisation
    Compter avec iI de 0 à MAX - 1
     
       Afficher iTab[iI] Tab
     
    Fin de compter
     
       Fin de ligne
       Fin de ligne
     
       /* Boucle : */
       Initialisation
       Compter avec iI de 0 à MAX - 1
     
          /* Boucle : */
          Initialisation
          Compter avec iJ de iI+1 à MAX - 1
     
    	 /* Alternative : */
    	 Si iTab[iJ] < iTab[iI] Alors
     
    	    iTemp <- iTab[iI]
    	    iTab[iI] <- iTab[iJ]
    	    iTab[iJ] <- iTemp
     
    	 Fin de si
     
          Fin de compter
     
          Afficher iTab[iI] Tab
     
       Fin de compter
     
    Attente
     
    Fin du traitement
    Merci pour vos commentaires, c'est vraiment sympa pour votre aide.

    Michael.

  15. #15
    Expert confirmé
    Avatar de Hephaistos007
    Profil pro
    Enseignant Chercheur
    Inscrit en
    Décembre 2004
    Messages
    2 493
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2004
    Messages : 2 493
    Points : 4 166
    Points
    4 166
    Par défaut
    Je n'arrive pas à voir quel algorithme de tri tu as utilisé. Ca ressemble vaguement à un tri bulle mais ca n'en est pas un.

    Surtout, tu ne respectes pas du tout les consignes de ton exercice :
    • Ecrire un algorithme qui range les éléments de ce tableau dans un deuxième tableau ...
    • Le premier tableau ne sera parcouru qu'une seule fois

  16. #16
    IDE
    IDE est déconnecté
    Membre régulier Avatar de IDE
    Profil pro
    Inscrit en
    Mai 2004
    Messages
    238
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : Belgique

    Informations forums :
    Inscription : Mai 2004
    Messages : 238
    Points : 89
    Points
    89
    Par défaut Suite
    Oui tu as raison, mais j'avais envie de changer car de toute maniere je fais les exercices pour moi, je pense que c'est pas plus mal de n'utiliser qu'un seul tableau pour faire le tri, enfin bon je suis loin d'etre un expert en programmation, je ne suis qu'un novice, mais bon mon résonnement fonctionne, passez une très bonne soirée.

    Michael

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Exercice sur les tableaux
    Par haha1 dans le forum Pascal
    Réponses: 5
    Dernier message: 27/12/2008, 21h13
  2. Exercice sur les tableaux
    Par sayari7 dans le forum Pascal
    Réponses: 2
    Dernier message: 06/12/2008, 16h23
  3. aide pour un exercice sur les tableaux
    Par mimiif dans le forum Caml
    Réponses: 9
    Dernier message: 30/05/2008, 16h49
  4. Réponses: 11
    Dernier message: 04/02/2008, 21h37

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