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 :

Réarranger les éléments d'un tableau


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Étudiant
    Inscrit en
    Novembre 2009
    Messages
    74
    Détails du profil
    Informations personnelles :
    Âge : 36

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Novembre 2009
    Messages : 74
    Points : 39
    Points
    39
    Par défaut Réarranger les éléments d'un tableau
    Ecrire un algorithme qui réarrange les éléments du tableau T de telle façcon que tous les nombres nuls apparaissent au début,suivis des nombres positifs, puis des nombres négatifs.L'algorithme ne doit parcourir le tableau T qu'une seule fois et ne doit pas utiliser de tableau intermédiaires.
    j'ai pas trouvé une idée pour cet exercice

  2. #2
    Invité
    Invité(e)
    Par défaut
    salut,

    un peu relou mais...
    tu peux considérer trois intervalles I_0, I_n, I_p (respectivement contenant nuls, négatifs et positifs)
    chacun de ces intervalles est représenté par une taille resp t_0, t_n, t_p (si taille == 0, signifie l'intervalle est vide)
    (donc tu stockes pas les valeurs dans les intervalles mais tu te sers des tailles pour mettre à jour le tableau au fur et à mesure que tu avances en calculant les index respectifs)

    pour chaque el du tableau
    si el==0
    tu place el à la taille de t_0.
    tu mets à jour t_0
    vu que t'ecrases un element (qui par def n'est pas nul) alors il faut bouger cet el
    si cet el est negatif, alors tu le mets à t_0+t_1
    donc faut mettre à jour t_1 et bouger eventuellement lelem que t'écrases
    ....

    c'est relou car il faut être précis sur les indices..

  3. #3
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Bonjour

    chacun de ces intervalles est représenté par une taille resp t_0, t_n, t_p
    Tu ne connais aucune de ces tailles. À moins de parcourir deux fois le tableau. Ce qui est interdit.
    La vérité est ailleurs
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  4. #4
    Invité
    Invité(e)
    Par défaut
    hello Flodelarab,

    je suis vraisemblablement pas assez clair.
    l'intervalle est représenté virtuellement (pour comprendre ce qui se passe)
    mais concrètement il suffit de trois variables t0,t1,t2 représentant le nombre de fois qu'on a trouvé resp nul, négatif, positif.

    un seul parcours de tableau suffit cf pseudo code (qui n'est pas exacte mais qui devrait suffire pour intuiter l'algorithme)
    A chaque itération, on ecrit au minimum 0 fois si le tableau est déjà trié (même sil faut mettre à jour le t_{0,1,2} correspondant) et au plus trois fois (si le lelement qu'on place en t0 ecrase un el négatif (qu'il faut déplacer en t0+t1-1) et que lel remplacé est positif (qu'il faut als déplacer en t0+t1+t2-1)

  5. #5
    Expert éminent sénior
    Homme Profil pro
    Responsable Données
    Inscrit en
    Janvier 2009
    Messages
    5 188
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Responsable Données

    Informations forums :
    Inscription : Janvier 2009
    Messages : 5 188
    Points : 12 744
    Points
    12 744
    Par défaut
    Bonjour,
    Une idée, en vrac: tu parcours le tableau, si tu tombes sur un null tu le mets en première position, si tu tombes sur un positif tu le mets en dernière position, sinon tu ne fais rien.
    Au final tu dois retrouver les null en premier, les positif en dernier et les négatifs vont naturellement finir au milieu.
    Il y a peut-être une subtilité dans la gestion du "pointeur". Mais comme il s'agit d'un exercice, je ne te donnes pas la solution complète…

    Tatayo.

  6. #6
    Membre averti
    Profil pro
    Inscrit en
    Février 2010
    Messages
    264
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2010
    Messages : 264
    Points : 360
    Points
    360
    Par défaut Tri a bulle bullshort
    Pour l'exercercice il faut faire un tri à bulle de complexité o n ln n . Tu parcoures une fois le tableau en trouvant le max sur la moitié de la liste et tu Swap le max dans la cellule precedente avec le suivant

  7. #7
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Est-ce que le problème ne serait pas plus simple si on réécrivait la fonction qui donne la valeur d'un élément du tableau...

    ...en s'arrangeant pour que cette valeur "virtuelle" permette de trier le tableau dans le bon ordre avec les algos standards.

    Par exemple
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    int VirtualValue(int a) {
     si (a==0) return 0;
     si (a>0)  return 1;
     si (a<0)  return 2;
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #8
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    C'est un exercice 'scolaire' . Donc pas question d'utiliser un outil externe pour faire le tri.
    Je pense que Tatayo a proposé la bonne piste.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  9. #9
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Réarranger les éléments d'un tableau
    Bonjour,

    Citation Envoyé par emna1987 Voir le message
    Ecrire un algorithme qui réarrange les éléments du tableau T de telle façcon que tous les nombres nuls apparaissent au début,suivis des nombres positifs, puis des nombres négatifs.
    L'algorithme ne doit parcourir le tableau T qu'une seule fois et ne doit pas utiliser de tableau intermédiaires ...
    La condition imposée du parcours unique constitue la grosse difficulté. Elle peut être contournée en définissant un nombre suffisant d'indices auxiliaires.

    Soit donc le tableau de (N) termes:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    VAR Liste: ARRAY[1..N] OF Type_Nombre;
    Il est possible:
    a) que le tableau commence une suite ininterrompue de (Iz) termes nuls, et
    b) qu'il s'achève par une autre suite ininterrompue de (In) termes négatifs,
    ce que l'on repère aisément par des instructions du type:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Iz:= 0;
    WHILE (Liste[Iz+1]=0) DO Inc(Iz);
    k:= N + 1;
    WHILE (Liste[k-1]<0)DO Dec(k);
    In:= N + 1 - k;
    Il est encore possible (soyons optimistes) que l'on trouve ensuite:
    c) une suite ininterrompue de (Ip1) termes positifs succédant aux termes nuls, et
    d) une suite analogue de (Ip2) termes positifs précédant les termes négatifs,
    ce que l'on trouvera facilement:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    k:= Iz;
    WHILE (Liste[k+1]>0) DO Inc(k);
    Ip1:= k - Iz;
    k:= N + 1 - In;
    WHILE (Liste[k-1]>0) DO Dec(k);
    Ip2:= N + 1 - In - k;
    On a ainsi parcouru une fois - et une seule - un certain nombre de termes du tableau (N1 = Iz + Ip1 + Ip2 + In), situés aux deux extrémités de la liste (à moins évidemment qu'ils ne soient tous nuls: N1 >= 0).
    Reste à traiter les (N - N1) termes restants, dont les positions vont de (Iz + Ip1 + 1) à (N - In - Ip2).

    Cela doit pouvoir se traiter par des transferts de 2 termes, et variation des indices précédents, jusqu'à ce que l'on obtienne (condition d'arrêt):
    N = Iz + Ip1 + Ip2 + In .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #10
    Invité
    Invité(e)
    Par défaut
    je ne sais pas ce qui définit "la" bonne piste mais voici la variante que je proposais au début...
    pr rappel les intervalles sont stackés de gauche à droite.

    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
     
        n taille du tableau
        v le tableau
        pour i=0,i<n,++i
            el = v[i]
     
            si el==0
                ind=i0
                tmp=v[ind]  //element qu'on va ecraser
                v[ind] = el //on ajoute lelement a la fin de notre intervalle virtuel
                i0++
     
                si ind == i
                    //on a placé lelement courant à sa place
                    //a noter que ca correspond au cas ou le tableau commence par des el nuls.
                    //on peut y sortir de la boucle...
                    continuer
                finsi
                si tmp == 1
                    ind = i0+i1-1   //on retranche -1 car i0+i1 représente l'élement suivant de I1 SAUF que i1 ne change pas taille donc on accède au dernier et non au suivant
                    tmp2 = v[ind]    //element qu'on va ecraser
                    v[ind] = tmp   //de même on n'incremente pas i1 car l'intervalle n'a toujours pas changé de taille. On a juste fait une "rotation par la gauche"
     
                    si ind == i
                        //comme à gauche de i nous sommes tjs triés
                        //c'est "equivalent" à avoir permuté lelem courant qqpart à gauche et on peut arrêter la réflexion
                        //sinon ca signifie qu'on a rembourré lelem 0 au début de I1 et que le début de I1 s'est retrouvé dans lelem courant
                        //et on peut s'arrêter :)
                        continuer
                    finsi
     
                    ind = i0+i1+i2-1 //meme raison.
                    v[ind] = tmp2 //ya pas d'autres intervalles apres i2...
                sinon //le terme à déplacer positif
     
                    ind = i0+i1+i2-1
                    v[ind] = tmp
     
                finsi
     
            sinon si el==1
                ...
            sinon
                ...
            finsi
        finpour

  11. #11
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Le code correspondant à ce que Tatayo proposait :

    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
     
    Constantes 
      DEBUT
      MILIEU
      FIN_TABLEAU
    fin
    nb_lignes_a_traiter est un entier  // = taille du tableau
    ligne_a_traiter est un entier = 0
    nb_lignes_traitees est un entier = 0
    tantque nb_lignes_traitees < nb_lignes_a_traiter
       destination = quelle_destination( tb[ligne_a_traiter] )  //  renvoie un nombre égal à DEBUT , MILIEU ou FIN_TABLEAU    // renvoie DEBUT si tb[xxx] est nul, MILIEU si tb[xxx] est négatif , et FIN_TABLEAU sinon
       selon destination
          cas DEBUT 
                permute ( tb, 0, ligne_a_traiter)
                ligne_a_traiter ++
          cas MILIEU
                // rien à faire
                ligne_a_traiter ++
          cas FIN_TABLEAU
                permute ( tb, nb_lignes_a_traiter -1, ligne_a_traiter )
                // et je n'incrémente pas ligne_a_traiter.
       fin selon
       nb_lignes_traitees++
    fin tantque
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

Discussions similaires

  1. Réponses: 3
    Dernier message: 24/05/2006, 23h23
  2. Lister les éléments d'un tableau
    Par uado dans le forum ASP
    Réponses: 8
    Dernier message: 22/05/2006, 13h02
  3. [Tableaux] Tester les éléments d'un tableau dans un if
    Par Leobaillard dans le forum Langage
    Réponses: 3
    Dernier message: 20/05/2006, 17h07
  4. Réponses: 10
    Dernier message: 27/03/2006, 19h38
  5. Réponses: 4
    Dernier message: 11/01/2006, 10h22

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