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 habitué
    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 confirmé
    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 habitué
    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 confirmé
    Fais un effort : c'est pas bien compliqué de stocker cette valeur et de la comparer à celles qui sortiront ensuite…

  5. #5
    Membre habitué
    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 confirmé
    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
    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 confirmé
    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 habitué
    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 habitué
    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 confirmé
    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
    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 habitué
    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
    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 habitué
    @: 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 confirmé
    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
    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 confirmé
    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 habitué
    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.