[langage c]Demande aide écriture fonction
Répondre à la discussion
Affichage des résultats 1 à 13 sur 13

[langage c]Demande aide écriture fonction



  1. #1
    invite8b421ec7

    Question [langage c]Demande aide écriture fonction


    ------

    Bonjour,

    J'ai un souci . Je sollicite votre aide. En fait, je cherche à écrire une fonction qui permet de trier dans la meilleure position d'insertion des élements d'une liste chainée simple dans une liste chainée circulaire. Pour évaluer l'insertion je devrais calculer le cout de l'insertion de chaque élement dans les différentes positions et retenir la meilleure position pour l'élement qui a le cout minimum sur l’ensemble des élements. Refaire ceci jusqu’à ce que tous les élements de la liste sont traitées. Je ne sais pas comme faire ? Pourriez-vous m'aider par un début d'implémentation ?
    Voici un exemple pour assimiler comment fonctionne l’algorithme:

    Liste 1 = {1, 2, 3}
    Liste 2 = {0, 0}pour le moment notre liste chainée circulaire contient un seul élément = 0
    1 ère itérationinsérer le premier élément de la liste 1 à savoir 1 dans la meilleure position
    on va tester l'insertion de 1 dans toutes les positions dans la liste 2
    {0,1, 0} ==> cout d'insertion = 2
    résultat la meilleure position de l'élément 1 est position = 1
    Mettre l’élément dans la liste 2
    2 ère itérationinsérer le deuxième élement de la liste 1 à savoir 2 dans la meilleure position
    on va tester l'insertion de 1 dans toutes les positions dans la liste 2
    {0,2,1, 0} ==> cout d'insertion = 2
    {0,1,2, 0} ==> cout d'insertion = 3,
    3 ère itérationinsérer le troisième élement de la liste 3 à savoir 2 dans la meilleure position
    {0,3,1, 2,0} ==> cout d'insertion = 2
    {0,1,3, 2,0} ==> cout d'insertion =1
    {0,1,2,3, 0} ==> cout d'insertion = 4

    le meilleur élement sur tous les élement à insérer en premier lieu c’est le 3 car il permet un cout d’insertion minimum
    Résultat : mettre l’élement 3 dans la liste 2 en 1 ère position. Donc Liste 2 = {0, 3, 0}
    Refaire ceci jusqu’à ce que tous les élements seront traités.
    Merci par avance de vos aides .

    -----

  2. #2
    ProgVal

    Re : [langage c]Demande aide écriture fonction

    Bonjour,

    Citation Envoyé par celine2 Voir le message
    Je ne sais pas comme faire ?
    Le but d'un exercice est justement de te faire chercher. Si tu savais déjà comment faire, il ne servirai à rien.
    Et en faisant l'exercice à ta place, on ne t'aiderai pas, car tu ne saurais toujours pas comment le faire.

    Citation Envoyé par celine2 Voir le message
    Pourriez-vous m'aider par un début d'implémentation ?
    Non, c'est toi qui commence, puis nous qui t'aidons sur ce que tu n'arrives pas. Mais en aucun cas, on ne fera l'exercice à ta place. C'est toi qui est noté, pas nous.

    ProgVal

  3. #3
    invite8b421ec7

    Question Re : [langage c]Demande aide écriture fonction

    Bonjour,

    Ce n'est pas un exercice.
    J'ai un projet que je l'ai composé en divers fonction.
    Je suis bloquée sur cette fonction. Je sollicite vos aides pour démarrer.
    Merci de votre compréhension.

  4. #4
    ventilopomme

    Re : [langage c]Demande aide écriture fonction

    Citation Envoyé par celine2 Voir le message
    Bonjour,

    Ce n'est pas un exercice.
    J'ai un projet que je l'ai composé en divers fonction.
    Je suis bloquée sur cette fonction. Je sollicite vos aides pour démarrer.
    Merci de votre compréhension.
    c'est bizarre j'avais compris dans l'autre sens
    d'un coté j'ai ma liste chainée simple
    1,2,3
    et de l'autre ma liste circulaire
    0
    A chaque itération
    je regarde chaque élément de la ligne simple et je calcule le cout d'insertion de chacun , celui qui a le plus petit coùt est choisi pour être insérer dans la liste circulaire
    Peux tu définir le coût d'insertion ?
    A part le cout pour faire pointer les pointeurs comme il faut
    est ce que le temps de parcours de la liste circulaire est prise en compte ?
    exclu à jamais du présent

  5. A voir en vidéo sur Futura
  6. #5
    ventilopomme

    Re : [langage c]Demande aide écriture fonction

    Citation Envoyé par ventilopomme Voir le message
    c'est bizarre j'avais compris dans l'autre sens
    d'un coté j'ai ma liste chainée simple
    1,2,3
    et de l'autre ma liste circulaire
    0
    A chaque itération
    je regarde chaque élément de la ligne simple et je calcule le cout d'insertion de chacun , celui qui a le plus petit coùt est choisi pour être insérer dans la liste circulaire
    Peux tu définir le coût d'insertion ?
    A part le cout pour faire pointer les pointeurs comme il faut
    est ce que le temps de parcours de la liste circulaire est prise en compte ?
    Je décèle en plus un problème de logique

    Première itération
    indmin=99
    coutmin=99
    i=0
    pour chaque element elt de la liste simple
    si (cout(elt) < coutmin)
    coutmin=cout(elt)
    indmin=i
    fsi
    i++
    finpour
    inserercirculaire(indmin)

    donc a la premiere je trouve 1
    car 2 3 ont le même cout
    a la deuxieme iteration j'ai donc
    la liste simple = 2,3
    la liste circulaire = 0,1

    et ainsi de suite
    exclu à jamais du présent

  7. #6
    invite8b421ec7

    Unhappy Re : [langage c]Demande aide écriture fonction

    Citation Envoyé par ventilopomme Voir le message
    Je décèle en plus un problème de logique

    Première itération
    indmin=99
    coutmin=99
    i=0
    pour chaque element elt de la liste simple
    si (cout(elt) < coutmin)
    coutmin=cout(elt)
    indmin=i
    fsi
    i++
    finpour
    inserercirculaire(indmin)

    donc a la premiere je trouve 1
    car 2 3 ont le même cout
    a la deuxieme iteration j'ai donc
    la liste simple = 2,3
    la liste circulaire = 0,1

    et ainsi de suite
    Bonjour,
    Merci pour votre réponse.
    D'abord, je vous mis mon code pour mieux assimiler mes listes.
    içi l'élement c'est un client qu'on dispose des informations, coordonées, temps de service, horaires de RDV, etc.
    La solution est un ensemble de tournées (ordre de visite des clients).
    Objectif chercher la tournée minimum on se basant sur le principe de l'algorithme de cout d'insertion minimum. En fait, il s'agit de calculer le cout d'insertion des clients (element identifiant dans la liste client liste) dans chaque position dans la liste de solution (tournée).
    Exemple:
    on a la solution suivante
    liste solution(liste circulaire): 0 3 0
    liste chainee simple (liste client): 4 5
    on insére 4 dans les différents positions dans la liste solution
    c a d
    0 4 3 0 ===>on calcule le cout d'insertion qui est égale à (distance entre le client 0 et le client 4 +distance entre le client 0 et le client 3) -(distance entre le client 3 et le client 4) on suppose qui est égale à 3
    ensuite
    0 3 4 0 ==>cout insertion : 2

    ===>meilleur insertion client 4 est position 1 dans la liste cisrculaire (solution)
    met le client 4 dans la position 1 dans la chaine circulaire solution
    etc...

    Regarder ci-dessous pour voir la fonction calcul distance.
    Je suis bloquée sur l' algorithme d'insertion. Comment soustraire de la matrice distance entre les tous les noeuds chaque fois la distance qui correspond au noeud courant.
    Merci par avance de vos aides.
    Voici mes fonctions concernant liste chainee simple:
    Code:
    typedef struct noeud noeud;
    struct noeud
    {
        int identifiant;
        double abscisse;
        double ordonee;
        int demande;
        int temps_service;
        int borne_inf_tw;
        int borne_sup_tw;
        int capacite;
        int visit;
        struct noeud *suivant;
    };
    typedef noeud* llist;
    llist ajouter_noeud(llist client_liste, int id, double abs,double ord,int dde,int tps_service,int b_inf_tw,int b_sup_tw,int cap)
    {
        noeud* nouveau = (noeud*) malloc(sizeof(noeud));
        nouveau->identifiant = id;
        nouveau->abscisse = abs;
        nouveau->ordonee = ord;
        nouveau->demande = dde;
        nouveau->temps_service = tps_service;
        nouveau->borne_inf_tw = b_inf_tw;
        nouveau->borne_sup_tw = b_sup_tw;
        nouveau->capacite = 7;
        nouveau->suivant = client_liste;
    
        return nouveau;
    }
    /*=======================================
    fonction affichage liste client
    ========================================*/
    void afficher_liste(llist client_liste)
    {
        noeud *p = client_liste;
        printf("contenu de la liste\n");
        while (p!= NULL)
        {
            printf("\n %d %lf %lf %d %d %d %d %d\n",p->identifiant,p->abscisse,p->ordonee,p->demande,p->temps_service,p->borne_inf_tw,p->borne_sup_tw,p->capacite);
            p = p->suivant;
        }
    
    }
    /*======================================
    calcul de la matrice distance
    =======================================*/
    double** calculer_distance (llist client_liste)
    {
        noeud *h = client_liste;
        noeud *p1 = client_liste;
        noeud *p2 = client_liste;
        noeud *debut_liste = client_liste;
        int i;
        int j;
        double **distance;
    
        FILE *fichier = NULL;
    
        if ((fichier = fopen("D:\\Codes\\TS2004t3\\test.txt", "r")) == NULL)/*ouverture du fichier en lecture*/
            printf("Error: impossible d'ouvrir fichier donnees.txt\n");
    
        else//non
        {
    
    
            for (i=0;i<5;i++)
    
                fscanf(fichier, "%i %i %i %i %i %i %i %i",&(h->identifiant),&(h->abscisse),&(h->ordonee),&(h->demande),&(h->temps_service),&(h->borne_inf_tw),&(h->borne_sup_tw),&(h->capacite));
            distance = (double **) malloc (5 * sizeof (double*));
            for (i=0;i<5;i++)
            {
    
                distance[i]=(double *) malloc (5 * sizeof(double));
            }
            j=0;
    
            for (p1=debut_liste;p1!=NULL;p1=p1->suivant)
    
            {
                distance[j][j]= 0.0;
                i=j+1;
    
                for (p2=p1->suivant;p2!=NULL;p2=p2->suivant)
                {
    
                    distance[i][j]= distance[j][i]= sqrt((p1->abscisse - p2->abscisse) *(p1->abscisse - p2->abscisse) +(p1->ordonee - p2->ordonee) * (p1->ordonee - p2->ordonee));
                    i++;
                }
                j++;
            }
    
            fclose (fichier);
    
    
        }
        return distance;
    }
    
    /*===================================================
    Fonction affichage matrice distance
    ====================================================*/
    void afficher_matrice_distance (llist client_liste, double **distance)
    {
        int i, j;
        for (i=0;i<5;i++)
        {
            for (j=0;j<5;j++)
            {
    
                printf("\ndistance[%i][%i] = %lf\n",i, j, distance[i][j]);
            }
        }
    }
    /*====================================================
    fonction recherche valeur max dans la matrice distance
    =====================================================*/
    int rechercher_max_distance(double distance[5][5])
    {
        int j;
        double max = 0.0;
        int c;
        for (j=0;j<5;j++)
        {
    
            if (distance[0][j]>max)
            {
                max = distance[0][j];
    
                c = j;
            }
        }
        return c;
    }
    /*============================================
    supprimer le noeud de la liste de client
    ==============================================*/
    llist supprimer_max(llist client_liste, int valeur)
    {
        /* Liste vide, il n'y a plus rien à supprimer */
        if (client_liste == NULL)
            return NULL;
    
        /* Si l'élément en cours de traitement doit être supprimé */
        if (client_liste->identifiant == valeur)
        {
                    noeud* tmp = client_liste->suivant;
                 tmp = supprimer_max(tmp, valeur);
            return tmp;
        }
        else
        {
                    client_liste->suivant = supprimer_max(client_liste->suivant, valeur);
            return client_liste;
        }
    }
    Mes fonctions concernant chaine circulaire
    Code:
    typedef struct Listesolution
    {
        int no;
        int cur_capacity;
        double cost;
        double distance;
        struct Listesolution *suivant;
        int taille;
    
    }solution;
    
    typedef struct client
    {
    
        solution *premier;
        solution *dernier;
        int taille;
    
    
    }Dlist_solution;
    /*initialisation liste circuulaire*/
    void initialisation (Dlist_solution * liste)
    {
        liste->premier = NULL;
        liste->dernier = NULL;
        liste->taille = 0;
    }
    /*insertion premier element liste solution*/
    int ins_liste_solution_vide(Dlist_solution * liste, int val)
    {
        solution *nouveau;
        if ((nouveau = (solution *) malloc (sizeof (solution)))
                == NULL)
            return -1;
    
        nouveau->no = 0;
    
        nouveau->suivant = nouveau;
        liste->premier = nouveau;
        liste->dernier = nouveau;
        liste->taille++;
        return 0;
    }
    
    
    /* insertion dans une liste non-vide */
    int ins_liste_solution(Dlist_solution* liste, solution *courant, int val)
    {
        solution *nouveau;
        if ((nouveau = (solution *) malloc (sizeof (solution)))
                == NULL)
            return -1;
        nouveau->no = val;
    
        if (courant != liste->dernier)
            return -1;
    
        nouveau->suivant = courant->suivant;
        courant->suivant = nouveau;
        liste->dernier = nouveau;
        liste->taille++;
        return 0;
    }
    
    
    /* affichage de la liste */
    void afficher_solution(Dlist_solution * liste)
    {
        solution *courant;
        courant = liste->premier;
        int i;
        for (i=0;i<liste->taille;++i)
        {
            printf ("%d\n", courant, courant->no);
            courant = courant->suivant;
        }
    }
    Programme principale
    Code:
    int main (void)
    {
        llist ma_liste = NULL;
        int id;
        double abs;
        double ord;
        int dde;
        int tps_service;
        int b_inf_tw;
        int b_sup_tw;
        int cap;
        int i,j;
        int max;
        int no;
        solution *courant;
        Dlist_solution *liste;
        if ((liste = (Dlist_solution *) malloc (sizeof (Dlist_solution))) == NULL)
            return -1;
    
        FILE *fp = NULL;
        if (ma_liste!= NULL)
            printf("la liste est non vide \n");
    
        if ((fp = fopen("D:\\Codes\\TS2004t3\\test.txt", "r"))== NULL)
        {
            printf("Impossible d'ouvrir fichier donnees .txt \n");
            exit (-1);
        }
        else
        {
            for (i=0;i<5;i++)
            {
                fscanf(fp,"%d %lf %lf %d %d %d %d",&id,&abs,&ord,&dde,&tps_service,&b_inf_tw,&b_sup_tw,&cap);
                ma_liste = ajouter_noeud(ma_liste,id,abs,ord,dde,tps_service,b_inf_tw,b_sup_tw,cap);
    
            }
        }
    
        double **matrice_distance = calculer_distance(ma_liste);
    
        max = rechercher_max_distance(matrice_distance);
        printf("max est %d\n", max);
        initialisation (liste);
        if (liste->taille == 0)
        {
            ins_liste_solution_vide(liste,0);
        }
        else
        {
            ins_liste_solution(liste,liste->dernier,max);
        }
         printf ("%d elements:deb=%d, fin=%d\n",
                                            liste->taille,
                                            liste->premier->no,
                                            liste->dernier->no);
    
    
    
    
        getchar();
        return 0;
    }

  8. #7
    ventilopomme

    Re : [langage c]Demande aide écriture fonction

    c'est le probleme typique du voyageur de commerce
    ou eventuellement un probleme de tournées de vehicules
    D'un coté tu dois avoir un tableau contenant tes clients
    un tableau qui contient tous les liens entre clients avec leur distance / leur cout
    je pense que je t'ai donné une amorce
    exclu à jamais du présent

  9. #8
    invite8b421ec7

    Re : [langage c]Demande aide écriture fonction

    Citation Envoyé par ventilopomme Voir le message
    c'est le probleme typique du voyageur de commerce
    ou eventuellement un probleme de tournées de vehicules
    D'un coté tu dois avoir un tableau contenant tes clients
    un tableau qui contient tous les liens entre clients avec leur distance / leur cout
    je pense que je t'ai donné une amorce
    Merci ventilopomme de votre réponse.
    Il s'agit du problème de tournées de véhivules avec des contraintes de travail de chauffeur, fenetre de RDV, etc.
    J'ai choisi de stocker les informations de mes clients dans une liste simplement chainee (ordonnee, abscisse, numero, etc).
    J'ai calculé la distance entre tous les clients que j'ai stockées dans une matrice.
    J'ai du mal à représenter les liens entre les clients. Avez-vous une idée?
    Merci encore.

  10. #9
    ventilopomme

    Re : [langage c]Demande aide écriture fonction

    on peut voir une structure du type
    struct client_suivant
    {
    client *clt_suivant;
    int cout;
    }

    et tu as client qui est comme cela

    struct client
    int x
    int y
    int flag_parcouru
    int distance
    struct client_suivant tab[];

    ainsi tu representes le graphe qui va constituer ton parcours .
    bien sur il faut programmer en recursif
    exclu à jamais du présent

  11. #10
    ventilopomme

    Re : [langage c]Demande aide écriture fonction

    mais aussi j'ai vu que tu etais multicriteres , peut etre faire plusieurs graphes car si tu as fenetre de rdv cela implique des notions de vitesse etc
    exclu à jamais du présent

  12. #11
    invite8b421ec7

    Re : [langage c]Demande aide écriture fonction

    Merci beaucoup de votre réponse rapide.
    Citation Envoyé par ventilopomme Voir le message
    int flag_parcouru
    A quoi sert cette variable?

    Personnellement, j'ai pensé à une structure de ce type pour client (qui y compris dépôt)
    Code:
    typedef struct Client
    {
        
        
        int identifiant;
        double abscisse;
        double ordonee;
        int demande;
        int temps_service;
        int borne_inf_tw;
        int borne_sup_tw;
        double **distance;
        struct Client *suivant;
    }client;
    typedef struct ListeRepere {
    		client *debut;
    		client *fin;
    		int taille;
    }llist;
    et une structure de ce type pour résultat (une sorte de liste circulaire). J'ai pensé à ceci car chaque route doit commencer par le dépôt^et y retourner.
    Code:
    typedef struct node_liste
    {
    
        llist * liste_client;
        double cout;
        int capacite;
        struct node_liste *suivant;
        
    }node;
     
    
    typedef struct dl_ListeRepere {
      node *debut;
      node *fin;
      int taille;
    }Liste;
    Concernant le résultat, je ne sais pas si je dois contenter de cette structure ou il me faut une structure plus compliqué comme tableau de liste. Si vous voyez ce que je veux dire.
    Merci par avance de votre retour.

  13. #12
    ventilopomme

    Re : [langage c]Demande aide écriture fonction

    je pense qu'un tableau de liste serait bien cela permettrait de voir les differents chemins retenus
    exclu à jamais du présent

  14. #13
    ventilopomme

    Re : [langage c]Demande aide écriture fonction

    je pense que tu peux faire une structure chemin
    qui contient la liste "idéale" de clients a visiter
    exclu à jamais du présent

Discussions similaires

  1. Aide sur les differentes ecriture de la vitesse
    Par bmce dans le forum Physique
    Réponses: 0
    Dernier message: 05/01/2011, 01h00
  2. langage c++ fonction get
    Par invitedbe5e39e dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 09/10/2007, 13h54
  3. Demande d’avis pour l’écriture d’une fiction
    Par invite48d75f4d dans le forum Biologie
    Réponses: 34
    Dernier message: 26/07/2007, 12h50
  4. aide écriture macro, création d'un tableau récapitulatif
    Par invite709e46e7 dans le forum Logiciel - Software - Open Source
    Réponses: 2
    Dernier message: 11/02/2007, 12h58