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 :

Trier ou pas ?


Sujet :

Algorithmes et structures de données

  1. #1
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut Trier ou pas ?
    Bonjour,
    J'ai un tableaux de 7 valeurs entre 1 et 13 non trié. (index "ind" de 1 à 7)
    J'ai une valeur x entre 1 et 13
    Je voudrais prendre dans le tableau [A] la plus faible valeur supérieure à x.
    Suis-je obligé de trier [A] avant ou y a t-il moyen de s'en passer, et si oui comment (en pseudo code svp)
    Merciiiii.
    Savoir pour comprendre et vice versa.

  2. #2
    Membre éprouvé Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    315
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 315
    Points : 907
    Points
    907
    Par défaut
    Non tu n'es pas obligé, et tu ne devrais pas le faire si tu n'en as pas besoin, car c'est une opération dont le coût est en général en O(nlog(n)), alors qu'ici ce que tu veux faire est en O(n).

  3. #3
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par balkany Voir le message
    Non tu n'es pas obligé, et tu ne devrais pas le faire si tu n'en as pas besoin, car c'est une opération dont le coût est en général en O(nlog(n)), alors qu'ici ce que tu veux faire est en O(n).
    Si je ne trie pas il va me sortir la première valeur supérieure qu'il va trouver, mais pas la plus faible du tableau.
    Tu ne m'aide pas des masses.
    Savoir pour comprendre et vice versa.

  4. #4
    Membre éprouvé Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    315
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 315
    Points : 907
    Points
    907
    Par défaut
    Fais un effort : c'est pas bien compliqué de stocker cette valeur et de la comparer à celles qui sortiront ensuite…

  5. #5
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par balkany Voir le message
    Fais un effort : c'est pas bien compliqué de stocker cette valeur et de la comparer à celles qui sortiront ensuite…
    C'est sûr que quand on sait faire, tout est facile et rien n'est compliqué.
    Mais bon, faut savoir faire, et là ça fait un moment que je mets des instructions dans tous les sens et pour l'instant, j'en suis à trier, vu qu'autrement j'y arrive pô mais comme le tableau est "soudé" à d'autres c'est la panique des index.
    Au secours les bonnes âmes...
    Savoir pour comprendre et vice versa.

  6. #6
    Membre éprouvé Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    315
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 315
    Points : 907
    Points
    907
    Par défaut
    Je ne sais pas si c'est du pseudo-code correct, mais voilà :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    y = INF
    Pour i = 0; i < longueur (A); i = i + 1
      Si x < A[i] et A[i] < y
        y = A[i]
      FinSi
    FinPour
    Et si tu ne peux ou ne veux pas initialiser y avec une valeur « infinie », tu peux découper la boucle en deux temps :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Pour i = 0; i < longueur (A); i = i + 1
      Si x < A[i]
        y = A[i]
        Interruption
      FinSi
    FinPour
     
    Pour j = i; j < longueur (A); j = j + 1
      Si x < A[j] et A[j] < y
        y = A[j]
      FinSi
    FinPour

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

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 770
    Points : 11 990
    Points
    11 990
    Par défaut
    Bonjour

    Et si tu ne peux ou ne veux pas initialiser y avec une valeur « infinie »
    Ce n'est pas une question anodine. On cherche une solution dont on n'a pas prouvé l'existence. "y" doit donc prendre la valeur que doit retourner l'algorithme en cas d'absence de solution.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  8. #8
    Membre éprouvé Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    315
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 315
    Points : 907
    Points
    907
    Par défaut
    Oui, j'ai laissé ce point de côté : à valentin03 de savoir comment il veut identifier la possible non existence d'une solution (on peut aussi affecter un booléen dans la première boucle du second code).

  9. #9
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par balkany Voir le message
    Je ne sais pas si c'est du pseudo-code correct, mais voilà :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    y = INF
    Pour i = 0; i < longueur (A); i = i + 1
      Si x < A[i] et A[i] < y
        y = A[i]
      FinSi
    FinPour
    Et si tu ne peux ou ne veux pas initialiser y avec une valeur « infinie », tu peux découper la boucle en deux temps :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    Pour i = 0; i < longueur (A); i = i + 1
      Si x < A[i]
        y = A[i]
        Interruption
      FinSi
    FinPour
     
    Pour j = i; j < longueur (A); j = j + 1
      Si x < A[j] et A[j] < y
        y = A[j]
      FinSi
    FinPour
    J'ai interprété ton "interruption" comme une sortie de la boucle
    Et ça a l'air de fonctionner, un gros merci.
    Pour les non-solutions je devrais pouvoir m'en sortir, sinon, je reviendrai.
    Merci beaucoup.
    Savoir pour comprendre et vice versa.

  10. #10
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par valentin03 Voir le message
    J'ai interprété ton "interruption" comme une sortie de la boucle
    Et ça a l'air de fonctionner, un gros merci.
    Pour les non-solutions je devrais pouvoir m'en sortir, sinon, je reviendrai.
    Merci beaucoup.
    Pour le premier algo, si je mets pour Y une valeur supérieure au nombre le plus grand du tableau ça fonctionne aussi. mais est-ce que ça va gérer les non solutions et si oui comment ?
    Savoir pour comprendre et vice versa.

  11. #11
    Membre éprouvé Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    315
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 315
    Points : 907
    Points
    907
    Par défaut
    Le truc c'est que le tableau n'est pas connu d'avance, et qu'on ne veut pas avoir à le parcourir une première fois pour savoir quel est le plus grand élément, afin d'initialiser y avec une valeur plus grande encore.
    D'où le recours à une constante connue à priori dans le langage, comme INF en matlab (si je me souviens bien), mais elle n'existe pas forcément partout.

    À partir de là, si en sortie du programme y vaut INF, c'est qu'il n'y avait pas de solution.
    Sinon, tu peux aussi initialiser y à x, et de même, si y vaut x en sortie, c'est qu'il n'y avait pas de solution.

    Ou encore, tu peux initialiser un booléen à FAUX et le faire passer à VRAI dans la première boucle, comme je disais plus haut :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    existenceSolution = FAUX
    Pour i = 0; i < longueur (A); i = i + 1
      Si x < A[i]
        y = A[i]
        existenceSolution = VRAI
        Interruption
      FinSi
    FinPour
    Après ça dépend du langage pour savoir comment tu récupères le booléen et y, c'est pour ça que je n'aime pas beaucoup le pseudo-code…

    +++

    Ceci dit, j'imagine qu'il faut rajouter quelque chose comme
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    Renvoyer y et existenceSolution
    sans se soucier de savoir comment on les renvoie…

  12. #12
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    décembre 2012
    Messages
    3 862
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : décembre 2012
    Messages : 3 862
    Points : 11 327
    Points
    11 327
    Par défaut
    Balkany a raison, dans ce genre de situation, le pseudo-code n'est pas adapté, car si on considère les langages qui ne créent par exemple la case du tableau que l'on initialise, on peut facilement faire un tri implicite au remplissage du tableau et donc connaitre aussi les extrêmes.
    Cordialement.

  13. #13
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Citation Envoyé par disedorgue Voir le message
    Balkany a raison, dans ce genre de situation, le pseudo-code n'est pas adapté, car si on considère les langages qui ne créent par exemple la case du tableau que l'on initialise, on peut facilement faire un tri implicite au remplissage du tableau et donc connaitre aussi les extrêmes.
    Pour ce cas la grandeur du tableau est connue et les nombres sont connus Tous les algos ne sont transcrivables en pseudo code, mais là ça va très bien, c'est plus clair que dans un langage à la syntaxe inconnue.
    Je mets "résolu" si j'y arrive
    Savoir pour comprendre et vice versa.

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

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 770
    Points : 11 990
    Points
    11 990
    Par défaut
    Conceptuellement, on renvoie un pointeur. Un pointeur vers la solution si elle existe, et un pointeur nul, sinon. Je ne crois pas qu'il y ait la nécessité de considérer 2 objets différents (un pour la faisabilité et un pour la solution).

    Le pseudo-code s'intéresse aux actions. Pas au format des données. N'est-ce pas ? (je n'en sais rien).

    transcrivables
    Aïe. Du verbe "transcriver" ? "Transcriptible", par exemple ? Comme pour les verbes inscrire, écrire, réécrire, transcrire. exemple: CD réinscriptible.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  15. #15
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    @: Flodelarab:
    Les "non solution" je les traiterai plus loin. (l'usine à gaz est en bonne voie, pour l'instant tout fonctionne, pourvu que ça dure...).
    Le pseudo code, c'est très merveilleux.
    Le "Transcriptible", le correcteur me l'a souligné en vermicelle rouge; alors j'ai tenté...Autre...Et j'ai encor'raté.
    Savoir pour comprendre et vice versa.

  16. #16
    Membre éprouvé Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    315
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 315
    Points : 907
    Points
    907
    Par défaut
    Le wiktionnaire donne transcrivable comme synonyme populaire de transcriptible : https://fr.wiktionary.org/wiki/transcrivable
    Mais hunspell ne semble effectivement apprécier ni l'un, ni l'autre

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

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 770
    Points : 11 990
    Points
    11 990
    Par défaut
    Le wiktionnaire est l'aspirateur à n'importe quelle ânerie.
    https://fr.wiktionary.org/wiki/transcriptible
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  18. #18
    Membre éprouvé Avatar de balkany
    Homme Profil pro
    Touriste
    Inscrit en
    juillet 2017
    Messages
    315
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Touriste

    Informations forums :
    Inscription : juillet 2017
    Messages : 315
    Points : 907
    Points
    907
    Par défaut
    Bah je trouve pas tant que ça en fait.
    Ils ont leurs critères d'acceptabilité, comme tous les sites de la fondation wikimedia : https://fr.wiktionary.org/wiki/Wikti...s_entr%C3%A9es
    Ce ne sont certes pas ceux de l'académie française, mais ça ne me semble pas si absurde (rapide lecture pour la première fois : ça me rappelle wikipédia (forcément), où j'ai un peu contribué par le passé).
    Mais bon, on s'écarte probablement pas mal du sujet

  19. #19
    Membre actif
    Homme Profil pro
    Développeur de jeux vidéo
    Inscrit en
    février 2013
    Messages
    285
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations professionnelles :
    Activité : Développeur de jeux vidéo

    Informations forums :
    Inscription : février 2013
    Messages : 285
    Points : 211
    Points
    211
    Par défaut
    Je crains que nous ne devions nous soumettre à l'implacable logique de Flodelarab qui a cassé la baraque avec un imparable: "transcriver".
    Savoir pour comprendre et vice versa.

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

Discussions similaires

  1. Trier par pas de 50
    Par rabia dans le forum Excel
    Réponses: 1
    Dernier message: 28/01/2010, 19h04
  2. Une requête que je ne parviens pas à trier
    Par renaud26 dans le forum Requêtes
    Réponses: 16
    Dernier message: 02/04/2008, 20h49
  3. KeyListener, je n'arrive pas a les trier.
    Par Djobird dans le forum AWT/Swing
    Réponses: 2
    Dernier message: 10/05/2007, 09h37
  4. Réponses: 6
    Dernier message: 30/01/2007, 09h05
  5. [MySQL] [SQLyog] comment ne pas trier les attributs sur 1 PK
    Par raoulmania dans le forum Installation
    Réponses: 11
    Dernier message: 19/12/2005, 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