Plus court chement avec le cout
developvbdebut
Messages postés
476
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
2 juin 2012
-
28 mai 2007 à 22:53
The_Guardian Messages postés 317 Date d'inscription vendredi 25 mai 2007 Statut Membre Dernière intervention 19 octobre 2007 - 31 mai 2007 à 22:20
The_Guardian Messages postés 317 Date d'inscription vendredi 25 mai 2007 Statut Membre Dernière intervention 19 octobre 2007 - 31 mai 2007 à 22:20
A voir également:
- Plus court chement avec le cout
- Cout endl - Forum C++ & C++ .NET
- Visual studio cout ✓ - Forum C++ & C++ .NET
- Cout est ambigu - Forum C / C++ / C++.NET
- Coût sybase - Conseils pratiques -SQL
- Cout c++ - Forum C / C++ / C++.NET
6 réponses
developvbdebut
Messages postés
476
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
2 juin 2012
1
28 mai 2007 à 22:56
28 mai 2007 à 22:56
Re
pardon il n'ya pas tout le code du graph.c
Le voici
#include <stdlib.h>
#include <stdio.h>
#include "graph.h"
struct table tab;
struct liste lis;
void result(){
}
void recherche(char tabl[a][b],int distance,char depa,char arriv){
int i;
int n_parcouru, n_precedent;
for(i=0;i<a;i++){
n_parcouru = INFINI;
n_precedent=0;
}
lis.parcouru=0;
}
void saisie()
{
int i,j;
int cout=0;
puts("Bienvenue a la SNCF\n");
for(i=0;i<a;i++){
for(j=0;j<b;j++){
printf(" %s",tableau[i][j]);
}
puts("\n");
}
puts("\n");
puts("Entrer l'indice de la ville du debut de parcours");
scanf("%c",&tab.de);
puts("Entrer l'indice de la ville de fin de parcours");
scanf("%c\n",&tab.ar);
/**/
recherche(tableau,cout,tab.de,tab.ar);
/*fin de programme*/
system("PAUSE");
}
A+
pardon il n'ya pas tout le code du graph.c
Le voici
#include <stdlib.h>
#include <stdio.h>
#include "graph.h"
struct table tab;
struct liste lis;
void result(){
}
void recherche(char tabl[a][b],int distance,char depa,char arriv){
int i;
int n_parcouru, n_precedent;
for(i=0;i<a;i++){
n_parcouru = INFINI;
n_precedent=0;
}
lis.parcouru=0;
}
void saisie()
{
int i,j;
int cout=0;
puts("Bienvenue a la SNCF\n");
for(i=0;i<a;i++){
for(j=0;j<b;j++){
printf(" %s",tableau[i][j]);
}
puts("\n");
}
puts("\n");
puts("Entrer l'indice de la ville du debut de parcours");
scanf("%c",&tab.de);
puts("Entrer l'indice de la ville de fin de parcours");
scanf("%c\n",&tab.ar);
/**/
recherche(tableau,cout,tab.de,tab.ar);
/*fin de programme*/
system("PAUSE");
}
A+
The_Guardian
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007
1
28 mai 2007 à 23:52
28 mai 2007 à 23:52
Salut,
Bon alors ta fonction recherche est pas trop mal, le debut en tout cas effectivement, tu fais la bonne initialisation, mais il te manque l'etape d'apres
de l'algorithme de Dijkstra.
pour i de '0' a 'a' faire
indice <--- l'indice de la ville non parcourue ayant la plus petite distance parcourue.
pour j de '0' a 'a' faire
si il y a une route entre la ville 'k' et la ville 'indice' alors si la ville 'j' n'est pas dans la liste.
ta fonction recherche devrait etre comme ca
visite = tableau de n booleens
precedent = tableau de n entiers
distance = tableau de n entiers
initialement
- tous les elements de visite sont a FAUX
- toutes les distances sont a 10000
distance[depart] = 0
pour i de 1 a n faire
ville <-- indice de la ville ayant la plus petite distance telle que visite[ville]==FAUX
pour j de 1 a n faire
si il y a une route entre ville et j alors
si visite[j]==FAUX alors
si distance[ville]+cout(ville, j)<distance[j] alors
distance[j] = distance[ville]+cout(ville, j)
precedent[j] = ville
finsi
finsi
finsi
finpour
visite[ville] = VRAI
finpour
=
Bon alors ta fonction recherche est pas trop mal, le debut en tout cas effectivement, tu fais la bonne initialisation, mais il te manque l'etape d'apres
de l'algorithme de Dijkstra.
pour i de '0' a 'a' faire
indice <--- l'indice de la ville non parcourue ayant la plus petite distance parcourue.
pour j de '0' a 'a' faire
si il y a une route entre la ville 'k' et la ville 'indice' alors si la ville 'j' n'est pas dans la liste.
ta fonction recherche devrait etre comme ca
visite = tableau de n booleens
precedent = tableau de n entiers
distance = tableau de n entiers
initialement
- tous les elements de visite sont a FAUX
- toutes les distances sont a 10000
distance[depart] = 0
pour i de 1 a n faire
ville <-- indice de la ville ayant la plus petite distance telle que visite[ville]==FAUX
pour j de 1 a n faire
si il y a une route entre ville et j alors
si visite[j]==FAUX alors
si distance[ville]+cout(ville, j)<distance[j] alors
distance[j] = distance[ville]+cout(ville, j)
precedent[j] = ville
finsi
finsi
finsi
finpour
visite[ville] = VRAI
finpour
=
developvbdebut
Messages postés
476
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
2 juin 2012
1
29 mai 2007 à 09:25
29 mai 2007 à 09:25
bonjour tout le monde
J'ai un doute concernant le tableau des villes
Voici comment mon était donnée le villes dans le fichier text avec le TP.
st-quentin 6
cambrai 39
capelle 50
laon 52
noyon 40
peronne 29
roye 48
capelle 5
avesnes 16
cambrai 54
charleville-mezieres 68
st-quentin 50
vervins 17
laon 4
reims 45
soissons 32
st-quentin 52
vervins 32
noyon 3
compiegne 24
roye 20
st-quentin 40
roye 5
amiens 41
compiegne 39
noyon 20
peronne 31
st-quentin 48
peronne 4
amiens 52
bapaume 20
roye 31
st-quentin 29
cambrai 7
arras 37
avesnes 59
bapaume 30
capelle 54
douai 39
st-quentin 39
valenciennes 26
dois je mettre en forme le tableau exactement ainsi, en ajoutant les une colonne pour les kilomêtre et au ajoutant plusieurs fois les villes, l'algo en s'aura t'il modifié.
Merci.
A+
J'ai un doute concernant le tableau des villes
Voici comment mon était donnée le villes dans le fichier text avec le TP.
st-quentin 6
cambrai 39
capelle 50
laon 52
noyon 40
peronne 29
roye 48
capelle 5
avesnes 16
cambrai 54
charleville-mezieres 68
st-quentin 50
vervins 17
laon 4
reims 45
soissons 32
st-quentin 52
vervins 32
noyon 3
compiegne 24
roye 20
st-quentin 40
roye 5
amiens 41
compiegne 39
noyon 20
peronne 31
st-quentin 48
peronne 4
amiens 52
bapaume 20
roye 31
st-quentin 29
cambrai 7
arras 37
avesnes 59
bapaume 30
capelle 54
douai 39
st-quentin 39
valenciennes 26
dois je mettre en forme le tableau exactement ainsi, en ajoutant les une colonne pour les kilomêtre et au ajoutant plusieurs fois les villes, l'algo en s'aura t'il modifié.
Merci.
A+
The_Guardian
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007
1
29 mai 2007 à 11:41
29 mai 2007 à 11:41
RE
l'algo que je t'ai montre est un algo de recherche pour initialiser tes donnees, il te faut un autre algo que je vais te donner maintenant:
deja il te faut un tableau de noms de villes
string nomDesVilles[10];
nomDesVilles[0] = "cambrai" par exemple, etc
ensuite il te faut un tableau a deux dimensions pour les distances
int distances[10][10];tu initialises toutes les cases a INFINI, puis apres tu lis tes distances dans le fichier on voit que st-quentin / cambrai 39, donc tu mets nomDesVilles[1][0] 39 et nomDesVilles[0][1] = 39 (ici j'ai suppose st-quentin est la ville numero 1)
Voila tu fais ca pour toutes les villes de ton fichier texte et apres ca sera bon.
=
l'algo que je t'ai montre est un algo de recherche pour initialiser tes donnees, il te faut un autre algo que je vais te donner maintenant:
deja il te faut un tableau de noms de villes
string nomDesVilles[10];
nomDesVilles[0] = "cambrai" par exemple, etc
ensuite il te faut un tableau a deux dimensions pour les distances
int distances[10][10];tu initialises toutes les cases a INFINI, puis apres tu lis tes distances dans le fichier on voit que st-quentin / cambrai 39, donc tu mets nomDesVilles[1][0] 39 et nomDesVilles[0][1] = 39 (ici j'ai suppose st-quentin est la ville numero 1)
Voila tu fais ca pour toutes les villes de ton fichier texte et apres ca sera bon.
=
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
developvbdebut
Messages postés
476
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
2 juin 2012
1
29 mai 2007 à 23:09
29 mai 2007 à 23:09
Bonsoir tout le monde
graph.h
#ifndef GRAPH_H
#define GRAPH_H
/**/
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#define INFINI INT_MAX
#define a 18
#define b 18
#define c 18
#define d 2
/**/
#define STQUENTIN 0
#define CAMBRAI 1
#define CAPELLE 2
#define LAON 3
#define AVESNES 4
#define CHARLEVILLEMEZIERES 5
#define REIMS 6
#define SOISSONS 7
#define VERVINS 8
#define NOYON 9
#define ROYE 10
#define AMIENS 11
#define COMPIEGNE 12
#define PERONNE 13
#define ARRAS 14
#define BAPAUME 15
#define DOUAI 16
#define VALENCIENNE 17
/**/
const char* tableau [c][d]={
"1","St-quentin",
"2","Cambrai",
"3","Capelle",
"4","Laon",
"5","Noyon",
"6","Peronne",
"7","Roye",
"8","Avesne",
"9","Charleville-Meziere",
"10","Vervins",
"11","Reins",
"12","Soisson",
"13","Amiens",
"14","Compiegne",
"15","Bapaume",
"16","Arras",
"17","Douai",
"18","Valenciennes"};
/**/
/*Ci-dessou la structure*/
struct table{
int km;
char destination;
char source;
char de;
char ar;
};
/*Ci-dessou*/
struct liste{
int villeprecedent;
char pasencoreVue;
};
#endif
graph.c
#include <stdlib.h>
#include <stdio.h>
#include "graph.h"
struct table tab;
struct liste lis;
int distance[18][18]={INFINI};
void result(){
}
int dist(){
int i,j;
/*ici on initialise les distances*/
distance[STQUENTIN][CAMBRAI]=39;
distance[STQUENTIN][CAPELLE]=50;
distance[STQUENTIN][LAON]=52;
distance[STQUENTIN][NOYON]=40;
distance[STQUENTIN][PERONNE]=29;
distance[STQUENTIN][ROYE]=48;
distance[CAPELLE][AVESNES]=16;
distance[CAPELLE][CAMBRAI]=54;
distance[CAPELLE][CHARLEVILLEMEZIERES]=68;
distance[CAPELLE][STQUENTIN]=50;
distance[CAPELLE][VERVINS]=17;
distance[LAON][REIMS]=45;
distance[LAON][SOISSONS]=32;
distance[LAON][STQUENTIN]=52;
distance[LAON][VERVINS]=32;
distance[NOYON][COMPIEGNE]=24;
distance[NOYON][ROYE]=20;
distance[NOYON][STQUENTIN]=40;
distance[ROYE][AMIENS]=41;
distance[ROYE][COMPIEGNE]=39;
distance[ROYE][NOYON]=20;
distance[ROYE][PERONNE]=31;
distance[ROYE][STQUENTIN]=48;
distance[PERONNE][AMIENS]=52;
distance[PERONNE][BAPAUME]=20;
distance[PERONNE][ROYE]=31;
distance[PERONNE][STQUENTIN]=29;
distance[CAMBRAI][ARRAS]=37;
distance[CAMBRAI][AVESNES]=59;
distance[CAMBRAI][BAPAUME]=30;
distance[CAMBRAI][CAPELLE]=54;
distance[CAMBRAI][DOUAI]=39;
distance[CAMBRAI][STQUENTIN]=39;
distance[CAMBRAI][VALENCIENNE]=26;
puts("les chemins\n");
for(i=0;i<a;i++){
for(j=0;j<b;j++){
if(distance[i][j]==INFINI){
printf(" -- ");
}
else { printf("%d ", distance[i][j]); }
}
puts("\n");
}
for(i=0;i<a;i++){
for(j=0;j<b;j++){
distance[i][j] = INFINI;
}
}
}
/*Voici l'algorithme de Dijkstra, pour le plus cours chemin*/
int recherche(char tabl[][b],int cout[][18],char dep,char arriv){
/*là on déclare des des variables pour*/
int i,j;
for(i=1;i<a;i++){
for(j=1;j<b;j++){
cout[i][j]=INFINI;
}
cout[i][j]=0;
}
while(cout!=0){
tab.source=dep;
for(i=1;i<lis.pasencoreVue;i++){
tab.destination= arriv;
}
}
return recherche(tabl,cout,tab.source,tab.destination);
}
/*ici c'est la fonction de départ, c'est là que l'on choisira sont parcourt
audémarage un tableau s'affichera avec les villes.
*/
void saisie()
{
int i,j;
puts("Bienvenue a la SNCF\n");
for(i=0;i<c;i++){
for(j=0;j<d;j++){
printf(" %s", tableau[i][j]);
}
puts("\n");
}
puts("\n");
/*Vous devrez saisir votre ville de départ et la ville d'arrivée*/
puts("Entrer l'indice de la ville du debut de parcours");
scanf("%c",&tab.de);
puts("Entrer l'indice de la ville de fin de parcours");
scanf("%c\n",&tab.ar);
/*ici on appelle la fonction recherche qui aura l'algorithme de Dijkstra
la fonction utilisera cette algorithme pour determiner le chemin le plus court
avec un cout minimum*/
recherche(tableau,distance,tab.de,tab.ar);
/*fin de programme*/
system("PAUSE");
}
******
La il, je suis perdue pour l'algo de la fonction recherche, je veux utiliser la fonction recherche avec la fonction dist qui contien les distances.
Donc, au final je souhait lors que l'on choisi une ville de départ et une ville d'arrivé , je veux que l'algo calcu le plus cours chemin et le cout.
Exemple
On part de Douai pour aller à Capelle, on devra passer par cambrai, le cout sera de 93 km, je souhaite que ca s'affiche.
Est ce que c'est possible.
Merci
A +
graph.h
#ifndef GRAPH_H
#define GRAPH_H
/**/
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#define INFINI INT_MAX
#define a 18
#define b 18
#define c 18
#define d 2
/**/
#define STQUENTIN 0
#define CAMBRAI 1
#define CAPELLE 2
#define LAON 3
#define AVESNES 4
#define CHARLEVILLEMEZIERES 5
#define REIMS 6
#define SOISSONS 7
#define VERVINS 8
#define NOYON 9
#define ROYE 10
#define AMIENS 11
#define COMPIEGNE 12
#define PERONNE 13
#define ARRAS 14
#define BAPAUME 15
#define DOUAI 16
#define VALENCIENNE 17
/**/
const char* tableau [c][d]={
"1","St-quentin",
"2","Cambrai",
"3","Capelle",
"4","Laon",
"5","Noyon",
"6","Peronne",
"7","Roye",
"8","Avesne",
"9","Charleville-Meziere",
"10","Vervins",
"11","Reins",
"12","Soisson",
"13","Amiens",
"14","Compiegne",
"15","Bapaume",
"16","Arras",
"17","Douai",
"18","Valenciennes"};
/**/
/*Ci-dessou la structure*/
struct table{
int km;
char destination;
char source;
char de;
char ar;
};
/*Ci-dessou*/
struct liste{
int villeprecedent;
char pasencoreVue;
};
#endif
graph.c
#include <stdlib.h>
#include <stdio.h>
#include "graph.h"
struct table tab;
struct liste lis;
int distance[18][18]={INFINI};
void result(){
}
int dist(){
int i,j;
/*ici on initialise les distances*/
distance[STQUENTIN][CAMBRAI]=39;
distance[STQUENTIN][CAPELLE]=50;
distance[STQUENTIN][LAON]=52;
distance[STQUENTIN][NOYON]=40;
distance[STQUENTIN][PERONNE]=29;
distance[STQUENTIN][ROYE]=48;
distance[CAPELLE][AVESNES]=16;
distance[CAPELLE][CAMBRAI]=54;
distance[CAPELLE][CHARLEVILLEMEZIERES]=68;
distance[CAPELLE][STQUENTIN]=50;
distance[CAPELLE][VERVINS]=17;
distance[LAON][REIMS]=45;
distance[LAON][SOISSONS]=32;
distance[LAON][STQUENTIN]=52;
distance[LAON][VERVINS]=32;
distance[NOYON][COMPIEGNE]=24;
distance[NOYON][ROYE]=20;
distance[NOYON][STQUENTIN]=40;
distance[ROYE][AMIENS]=41;
distance[ROYE][COMPIEGNE]=39;
distance[ROYE][NOYON]=20;
distance[ROYE][PERONNE]=31;
distance[ROYE][STQUENTIN]=48;
distance[PERONNE][AMIENS]=52;
distance[PERONNE][BAPAUME]=20;
distance[PERONNE][ROYE]=31;
distance[PERONNE][STQUENTIN]=29;
distance[CAMBRAI][ARRAS]=37;
distance[CAMBRAI][AVESNES]=59;
distance[CAMBRAI][BAPAUME]=30;
distance[CAMBRAI][CAPELLE]=54;
distance[CAMBRAI][DOUAI]=39;
distance[CAMBRAI][STQUENTIN]=39;
distance[CAMBRAI][VALENCIENNE]=26;
puts("les chemins\n");
for(i=0;i<a;i++){
for(j=0;j<b;j++){
if(distance[i][j]==INFINI){
printf(" -- ");
}
else { printf("%d ", distance[i][j]); }
}
puts("\n");
}
for(i=0;i<a;i++){
for(j=0;j<b;j++){
distance[i][j] = INFINI;
}
}
}
/*Voici l'algorithme de Dijkstra, pour le plus cours chemin*/
int recherche(char tabl[][b],int cout[][18],char dep,char arriv){
/*là on déclare des des variables pour*/
int i,j;
for(i=1;i<a;i++){
for(j=1;j<b;j++){
cout[i][j]=INFINI;
}
cout[i][j]=0;
}
while(cout!=0){
tab.source=dep;
for(i=1;i<lis.pasencoreVue;i++){
tab.destination= arriv;
}
}
return recherche(tabl,cout,tab.source,tab.destination);
}
/*ici c'est la fonction de départ, c'est là que l'on choisira sont parcourt
audémarage un tableau s'affichera avec les villes.
*/
void saisie()
{
int i,j;
puts("Bienvenue a la SNCF\n");
for(i=0;i<c;i++){
for(j=0;j<d;j++){
printf(" %s", tableau[i][j]);
}
puts("\n");
}
puts("\n");
/*Vous devrez saisir votre ville de départ et la ville d'arrivée*/
puts("Entrer l'indice de la ville du debut de parcours");
scanf("%c",&tab.de);
puts("Entrer l'indice de la ville de fin de parcours");
scanf("%c\n",&tab.ar);
/*ici on appelle la fonction recherche qui aura l'algorithme de Dijkstra
la fonction utilisera cette algorithme pour determiner le chemin le plus court
avec un cout minimum*/
recherche(tableau,distance,tab.de,tab.ar);
/*fin de programme*/
system("PAUSE");
}
******
La il, je suis perdue pour l'algo de la fonction recherche, je veux utiliser la fonction recherche avec la fonction dist qui contien les distances.
Donc, au final je souhait lors que l'on choisi une ville de départ et une ville d'arrivé , je veux que l'algo calcu le plus cours chemin et le cout.
Exemple
On part de Douai pour aller à Capelle, on devra passer par cambrai, le cout sera de 93 km, je souhaite que ca s'affiche.
Est ce que c'est possible.
Merci
A +
The_Guardian
Messages postés
317
Date d'inscription
vendredi 25 mai 2007
Statut
Membre
Dernière intervention
19 octobre 2007
1
31 mai 2007 à 22:20
31 mai 2007 à 22:20
RE
y'a pas mal de trucs a corriger sur ton programme..
Bon donc dans la fonction recherche, tu commences avec l'initialisation du tableau cout, ok
sauf que tu as mis cout[i][j] = 0 et ca doit etre cout[i][i] = 0
ensuite ton while est faux
L'algo est le suivant:
tantque la ville que je recherche est pas visitee faire
Mince c'est quoi ton code là. C'est ni fait, ni a faire en fait!
Bon on reprend depuis début.
Pour l'algo de dijkstra tu as besoin des variables suivantes
un tableau a une dimension cout
un tableau a une dimension visite
donc ton initialisation dans la fonction recherche est fausse
Ensuite l'algo est le suivant:
cout[source] = 0
tantque visite[destination]=faux faire
ville <--- la ville non visitee ayant le plus petit cout
pour toute autre ville v faire
si cout[v]>cout[ville]+distance[v][ville] alors
cout[v] = cout[ville]+distance[v][ville]
finsi
finpour
visite[ville] = vrai
fintantque
Tu risques d'avoir des problemes dans ton test car tu as utilise INT_MAX et c'est pas forcement le mieux, enfin du moment que tu fais les tests qui vont bien ca posera pas de problemes
=
Ps: c'est toi tintin ?
y'a pas mal de trucs a corriger sur ton programme..
Bon donc dans la fonction recherche, tu commences avec l'initialisation du tableau cout, ok
sauf que tu as mis cout[i][j] = 0 et ca doit etre cout[i][i] = 0
ensuite ton while est faux
L'algo est le suivant:
tantque la ville que je recherche est pas visitee faire
Mince c'est quoi ton code là. C'est ni fait, ni a faire en fait!
Bon on reprend depuis début.
Pour l'algo de dijkstra tu as besoin des variables suivantes
un tableau a une dimension cout
un tableau a une dimension visite
donc ton initialisation dans la fonction recherche est fausse
Ensuite l'algo est le suivant:
cout[source] = 0
tantque visite[destination]=faux faire
ville <--- la ville non visitee ayant le plus petit cout
pour toute autre ville v faire
si cout[v]>cout[ville]+distance[v][ville] alors
cout[v] = cout[ville]+distance[v][ville]
finsi
finpour
visite[ville] = vrai
fintantque
Tu risques d'avoir des problemes dans ton test car tu as utilise INT_MAX et c'est pas forcement le mieux, enfin du moment que tu fais les tests qui vont bien ca posera pas de problemes
=
Ps: c'est toi tintin ?
