Discussion :

[laureat]

Bonjour,

Je voudrais écrire l'algorithme ci-dessous en C:

met le noeud zero comme premier noeud à visiter dans Circuit->tableau[0]
ensuite, chercher le noeud qui a la plus grosse demande et qu'on le met dans Circuit->tableau[1]
Après, On recherche le noeud le plus proche que l'on ajoute dans Circuit->tableau[2]. Si le noeud est déjà dans la liste des noeuds visités, on prend le deuxième noeude plus proche,ainsi de suite.

Ci-dessous mon programme. Pourriez-vous me le corriger?
Merci par avance.

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
typedef struct Noeuds Noeuds ;
struct Noeuds
{
      int no;
      double x;
      double y;
      int demand;
 };
 
/* cette strucutre n'est pas indispensable, mais fourni une aide */
typedef struct GestionNoeuds GestionNoeuds;
struct GestionNoeuds
{
      Noeuds tableau[nbreNoeuds]; /* tableau de Noeuds */
      double **distanceEntreVertices;
 
};
struct Circuit
{
     int tableau[nbreNoeuds];
 
};
typedef struct Circuit Circuit;
/**
*allocation dynamique de la structure Circuit
*/
 
Circuit *allocationCircuit(void)
{
     Circuit *pCircuit;
      pCircuit = malloc(sizeof *pCircuit);
 
      return pCircuit;
}
/**
*Cette fonction permet de chercher le noeud qui a la plus grosse demande
*/
 
int chercherIndiceNoeudPlusGrosseDemande(GestionNoeuds *pGestionNoeuds)
{
     int  demandMax = 0;
     int indiceNoeud;
     int i;
     for(i=1; i<nbreNoeuds;i++)
     {
          if(demandMax < (pGestionNoeuds->tableau[i].demand))
          indiceNoeud = i;
     }
 
     return indiceNoeud;
}Circuit* recherchePlusProcheVoisin(GestionNoeuds *pGestionNoeuds)
{
     int i,j,k,tmp;
     int cycle = 0; /* Booléen */
     int visite[nbreNoeuds] = {0}; /* visite[i]=1 : */
     Circuit *pCircuit;
     pCircuit= allocationCircuit();
     int deuxiemeNoeud;
    /* Ici, on va constituer une solution. */
 
    /* On initialise */
     for (i=0 ; i<nbreNoeuds ; i++)
        pCircuit->tableau[i] =-1;
 
     int ind=2; /* Indice du tableau */
     /* Parcours */
     int min; /* Minimum */
     double **distanceEntreNoeuds = calculDistance(pGestionNoeuds);
     pCircuit->tableau[0] = 0;
     deuxiemeNoeud = chercherIndiceNoeudPlusGrosseDemande(pGestionNoeuds);
     pCircuit->tableau[1] =  deuxiemeNoeud;
     visite[deuxiemeNoeud]=1;
     while ( !cycle )
     {
          k=1;
          /* On se place sur le premier sommet non visité */
          while ( visite[k] )
               k++;
          min=distanceEntreNoeuds[deuxiemeNoeud-1][k-1];
          tmp=k;
          for ( j=k+1 ; j<=nbreNoeuds ; j++) /* Recherche du plus */
          /* proche voisin */
          {
               if (distanceEntreNoeuds[deuxiemeNoeud-1][j-1] < min && !visite[j] )
               {
                    min = distanceEntreNoeuds[deuxiemeNoeud-1][j-1];
                    tmp=j;
               }
          }
          ind++;
          pCircuit->tableau[ind]=tmp;
          visite[tmp]=1;
          for ( i=1 ; i<=nbreNoeuds ; i++ )
          /* Calcul du booléen cycle */
          {
               if ( visite[i] )
               cycle=1;
               else
               {
                    cycle=0;
                    break;
               }
          }
          i=tmp;
     }
     ind++;
 
     return pCircuit;
 
}

[skeud]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

/* cette strucutre n'est pas indispensable, mais fourni une aide */

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

/* cette structure n'est pas indispensable, mais fourni une aide */

On écris structure et non pas strucutre

Avec ceci un petit café non?

Plus sérieusemment ça serait bien d'expliquer le problème.......