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

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 1
    Points
    1

    Par défaut Trier des points algorithme

    Bonjour j'aurai besoin d'aide pour un algorithme, dans mon programme l'utilisateur rentre le nombre de points qu'il veut trier, après cela les coordonnées x et y de chacun des points, ce que je dois faire c'est afficher les points du plus proche de l'axe au plus éloigné.
    Par exemple, pour trois points (4,5) (2,3) (1,2) la réponse sera (1,2) (2,3) (4,5)

  2. #2
    Expert éminent sénior

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    juin 2007
    Messages
    5 142
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 5 142
    Points : 16 942
    Points
    16 942

    Par défaut

    Comment as-tu trié ces trois éléments?
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • jamais signifie "sauf si j'ai passé trois jours à prouver que je peux".
    • La plus sotte des questions est celle qu'on ne pose pas.
    Pour faire des graphes, essayez yEd.
    le ter nel est le titre porté par un de mes personnages de jeu de rôle

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 1
    Points
    1

    Par défaut

    j'ai compris que je dois rentrer ces elements dans un tableau, mais c'est justement la le probleme je n'arrive pas trouver l'algorithme qui me permette de trier les points en fonction de leur distance

  4. #4
    Expert éminent
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    mai 2010
    Messages
    2 560
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : cyber-paléontologue

    Informations forums :
    Inscription : mai 2010
    Messages : 2 560
    Points : 7 812
    Points
    7 812

    Par défaut

    Citation Envoyé par gaddielnabet Voir le message
    je dois faire c'est afficher les points du plus proche de l'axe au plus eloigne.
    Lequel des axes ? Soit tu trie par rapport à X , soit par rapport à Y , soit tu fait une moyenne des deux , tout dépend de ce que tu souhaite faire !
    Sinon il existe Qsort

  5. #5
    Membre expert
    Avatar de gerald3d
    Homme Profil pro
    Conducteur de train
    Inscrit en
    février 2008
    Messages
    2 047
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Conducteur de train
    Secteur : Transports

    Informations forums :
    Inscription : février 2008
    Messages : 2 047
    Points : 3 955
    Points
    3 955
    Billets dans le blog
    4

    Par défaut

    Bonjour.

    Je vais émettre une remarque sûrement stupide mais elle a le mérite de ne rien coûter, alors...

    Si tu dois classer des points en fonction de leur distance à l'origine, pourquoi ne pas calculer justement cette distance à ce point ? Bon, c'est coûteux en temps de calcul, mais je suppose que l'exercice n'est pas axé sur la performance.
    Tu pourrais disposer d'une structure contenant les coordonnées du point et la distance. Le tri se ferait alors assez facilement il me semble. Tu pourrais même te passer d'une telle structure avec un algorithme pensé en amont.

    Une autre remarque qui ne mange pas de pain. En français "c" s'écrit "c'est" ou "s'est". C'est selon... Ce n'est pas plus cher à écrire et beaucoup plus sympa pour les lecteurs que nous sommes .

    Citation Envoyé par gaddielnabet Voir le message
    j'ai compris que je dois rentrer ces elements dans un tableau, mais c'est justement la le probleme je n'arrive pas trouver l'algorithme qui me permette de trier les points en fonction de leur distance
    Petite question. Sais-tu calculer la distance d'un point dans un plan ?
    Utilisation de Glade avec Gtk+ - N'oubliez pas de consulter les FAQ Gtk et les cours et tutoriels Gtk

  6. #6
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 1
    Points
    1

    Par défaut

    Oui je connais la formule de la distance ...x^2+y^2 sous la racine carre mais cela ne change pas grand chose, et justement le programme doit avoir une complexite de temps de nlogn (n represente le nombre de points que l'on souhaite rentrer) et nous n'avons pas appris a utiliser les structures donc impossible d'utiliser ca...

  7. #7
    Rédacteur/Modérateur

    Homme Profil pro
    Network game programmer
    Inscrit en
    juin 2010
    Messages
    5 774
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : juin 2010
    Messages : 5 774
    Points : 25 361
    Points
    25 361

    Par défaut

    Citation Envoyé par gaddielnabet Voir le message
    nous n'avons pas appris a utiliser les structures donc impossible d'utiliser ca
    Les structures sont justes là pour structurer le code de manière plus logique.
    Tu peux très bien avoir 2 tableaux pour les coordonnées au lieu d'un unique tableau d'une struct Point. C'est super moche, si un étudiant me montrait ça je l'insulterais, mais si c'est imposé alors la faute revient au prof.

    Citation Envoyé par gaddielnabet Voir le message
    mais cela ne change pas grand chose
    Ben ça change que c'est la façon de faire

    L'exercice consiste à réimplémenter une fonction de tri.

    Citation Envoyé par gaddielnabet Voir le message
    le programme doit avoir une complexite de temps de nlogn
    Donc un Merge sort correspond d'après le tableau précédent.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  8. #8
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 1
    Points
    1

    Par défaut

    Merci pour ton aide,j'avais egalement pense a utiliser merge sort mais je n'arrive pas a trouver de quel maniere...

  9. #9
    Membre expert
    Avatar de gerald3d
    Homme Profil pro
    Conducteur de train
    Inscrit en
    février 2008
    Messages
    2 047
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Conducteur de train
    Secteur : Transports

    Informations forums :
    Inscription : février 2008
    Messages : 2 047
    Points : 3 955
    Points
    3 955
    Billets dans le blog
    4

    Par défaut

    La distance d'un point est bien égale à à la racine carrée de (x2 + y2) (merci M. Pythagore ). On peut d'ors et déjà se passer de la racine pour gagner en temps de calcul.

    Ensuite il faut connaître l'intervalle des points traiter. Peuvent-ils avoir des coordonnées négatives ? Quels sont les limites de ces mêmes coordonnées ? La réponse à ces deux questions va permettre de traiter le signe de la distance (même si mathématiquement c'est bien entendu faux) et de savoir de quel type devra être le tableau qui va recevoir les valeurs des distances calculées.

    En admettant que les coordonnées peuvent être négatives voila un pseudo-code possible :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    index = 0
     
    tant qu'il y a un point à traiter
      sauver le point dans un tableau point à la position index
      distance = x*x + y*y
      si x ou y négatif alors distance égale -distance
      sauver distance dans le tableau dist
      incrémenter l'index
    fin tant que
    À la sortie on dispose d'un tableau dist [] dans lequel on a toutes les distances non triées. Il suffit ensuite de le trier en utilisant l'algorithme mergesort dont le lien du post précédent de Bousk te donne le code source et le pseudo-code !

    Lors du tri il faut sauver dans un nouveau tableau indextri [] pas exemple non pas les distances triées mais les index du tableau dist [] trié. Ainsi, il suffira pour afficher les points triés d'utiliser les valeurs du tableau indextri [] comme index pour le tableau point [].
    Utilisation de Glade avec Gtk+ - N'oubliez pas de consulter les FAQ Gtk et les cours et tutoriels Gtk

  10. #10
    Expert confirmé
    Inscrit en
    mars 2005
    Messages
    1 426
    Détails du profil
    Informations forums :
    Inscription : mars 2005
    Messages : 1 426
    Points : 4 166
    Points
    4 166

    Par défaut

    S'il s'agit de trier les points par rapport à leur éloignement à une droite alors le critère de comparaison est la valeur du produit scalaire du vecteur de projection orthogonale avec lui-même, soit le carré de sa norme.

    On a le choix de calculer ce produit scalaire :

    • à l'avance, une fois pour chaque point et réaliser plusieurs parcours de la collection ;
    • à chaque comparaison (donc plusieurs fois pour chaque point dans le cas général) et réaliser un seul parcours de la collection.

    La mise en cache utilise moins de temps processeur mais plus de mémoire et c'est l'inverse pour la seconde méthode.


    Quoiqu'il en soit il y a au moins deux fonctions à écrire :

    1. la fonction d'ordre, qui attend deux points et est indépendante ;
    2. celle qui implémente l'algorithme de tri, qui attend une collection d'éléments (peu importe qu'il s'agisse de points, de chaînes ou de nouilles) et fait appel à la fonction d'ordre.

  11. #11
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 1
    Points
    1

    Par défaut

    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
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    void EnterMessage();
    void EnterPoints();
    void SortedPoints();
    void TopDownMergeSort(int A[],int B[],int n,int sorter_point[]);
    void TopDownSplitMerge(int B[],int iBegin,int iEnd,int A[],int sorter_point[]);
    void TopDownMerge(int A[],int iBegin,int iMiddle,int iEnd,int B[],int sorter_point[]);
    void CopyArray(int A[],int iBegin,int iEnd,int B[]);
     
    int main()
    {
    EnterMessage();
    int number_points;
    scanf(" %d",&number_points);
    int points[number_points][number_points];
    int distance[number_points];
    int help_array[number_points];
    int sorter_points[number_points];
    for (int i=0;i<number_points;i++){
            EnterPoints();
            for (int j=0;j<2;j++){
            scanf(" %d", &points[i][j]);
            distance[i]+=(points[i][j]*points[i][j]);}
        }
    TopDownMergeSort(distance,help_array,number_points,sorter_points);
    printf("%d",sorter_points[0]);
      return 0;
    }
    void EnterMessage(){
    printf("Enter number of points: ");}
    void EnterPoints(){
        printf("Enter point: ");}
    void SortedPoints(){
    printf("Sorted points: ");}
     
     
     
     
     
     
    void TopDownMergeSort(int A[],int B[],int n,int sorter_point[])
    {
        CopyArray(A, 0, n, B);
        TopDownSplitMerge(B, 0, n, A,sorter_point);
    }
     
    void TopDownSplitMerge(int B[],int iBegin,int iEnd,int A[],int sorter_point[])
    {
        if(iEnd - iBegin < 2)
            return;
     
     
        int iMiddle = (iEnd + iBegin) / 2;
        TopDownSplitMerge(A, iBegin,  iMiddle, B,sorter_point);
        TopDownSplitMerge(A, iMiddle,iEnd, B,sorter_point);
     
     
        TopDownMerge(B, iBegin, iMiddle, iEnd, A,sorter_point);
    }
     
    void TopDownMerge(int A[],int iBegin,int iMiddle,int iEnd,int B[],int sorter_point[])
    {
    int    counter=0;
        int i = iBegin, j = iMiddle;
        for (int k = iBegin; k < iEnd; k++) {
            if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
                B[k] = A[i];
                sorter_point[counter]=i;
                i = i + 1;
                counter++;
            } else {
                B[k] = A[j];
                sorter_point[counter]=j;
                j = j + 1;
                counter++;
            }
        }
    }
     
    void CopyArray(int A[],int iBegin,int iEnd,int B[])
    {
        for(int k = iBegin; k < iEnd; k++)
            B[k] = A[k];
    }

    MErci a tous pour vous reponses qui m'ont deja beaucoup aide, mais le programme ne fonctionne pas encore totalement je pense que le probleme se situe lorsque j'essaye de trier les distances et les index en meme temps...

  12. #12
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 23
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 1
    Points
    1

    Par défaut

    Merci pour l'idee mais je bloque justement sur le tri et l'agencement du tableau des index en meme temps...

Discussions similaires

  1. Algorithme de selection des points dans une grille
    Par Senadin dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 18/12/2013, 18h16
  2. Algorithme pour joindre des points
    Par tommytom78 dans le forum Mathématiques
    Réponses: 5
    Dernier message: 06/07/2012, 09h46
  3. Réponses: 10
    Dernier message: 05/03/2010, 14h37
  4. Réponses: 0
    Dernier message: 28/03/2009, 18h51
  5. Réponses: 24
    Dernier message: 01/06/2007, 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