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 111 112
| #include <stdio.h>
#include <conio.h>
#define NMAX 25/*nombre de villes*/
#define NMMAX 20/*nombre maximal de caractere dans le nom d'une ville*/
/*type pour representer les solutions */
typedef struct
{
int table[NMAX];
}sol;
/*type pour representer une vile*/
typedef struct
{
char NOM[NMMAX];/*nom d ela ville*/
int CODE;/*code postale de la ville*/
}VILLE;
/*fonction qui saisit le nombre de villes*/
int saisirnombrevilles()
{
int N;
do
{
printf("Entrez le nombre de villes:\n");
scanf("%d",&N);
}
while ((N<1)||(N>NMAX));
return N;
}
/*procedure permettant de saisir n villes*/
/*la ville de depart est stockee au debut du tableau*/
void saisirvilles(VILLE *v, int n)
{
int i;
printf("Entrer le nom de la ville de depart:\n");
scanf("%s",v[0].NOM);
printf("Entrer le code postale de la ville de depart\n");
scanf("%d",&v[0].CODE);
printf("%s %d: \n",v[0].NOM,v[0].CODE);
for (i=1;i<n;i++)
{
printf("Entrer le nom de la ville a visiter:\n");
scanf("%s",v[i].NOM);
printf("Enter le code de la ville a visiter:\n");
scanf("%d",&v[i].CODE);
printf("%s %d\n",v[i].NOM,v[i].CODE);
}
}
/*procedure permettant de saisir les distances */
void saisirdistance (int *distance, VILLE*VILLES, int n)
{
int i,j;
for (i=0;i<n;i++)
{
distance[i*NMAX+1]=0;/*pas de distance d'une ville a elle meme distance [i][j]=0*/
for (i=0;i<n;i++)
{
printf("distance entre %s et %s :\n",VILLES[i].NOM,VILLES[j].NOM);
scanf("%d",&distance[i*NMAX+j]);
/*la matrice est symetrique:diatance [j][i]=diatance[i][j]*/
distance[j*NMAX+i]=distance[i*NMAX+j];
printf("diastance entre %d et %d=%d\n",i,j,distance[i+NMAX+j]);
}
}
}
/*fonction permettant de verifier si unr sequence est une solution coherente*/
/*retourne 1 si valide,0 sinon*/
int valider (sol sequence,int n)
{
int test=1;
int s=0;
int i,j;
/*la ville de depart doit etre la ville numero 0*/
if (sequence.table[0]!=0)
return 0;
for (i=0;i<n;i++)
{
/*les numeros de villes doivent varier de 1 a n-1*/
if ((sequence.table[i]>n-1) ||(sequence.table[i]<1))
return 0;
/*les numeros de villes doivent etre differents*/
for (i=0;i<n;i++)
{
if (sequence.table[i]==sequence.table[j])
return 0;
}
}
return test;
}
void main ()/*algorithme principal*/
{
int n;
int distance[NMAX][NMAX];
VILLE VILLES [NMAX];
sol s;
int i;
n=saisirnombrevilles();
saisirvilles(VILLES,n);
saisirdistance (distance,VILLES,n);
} |
Partager