Version anglaise Version espagnoleVersion françaiseVous n'êtes pas connecté. Inscrivez-vous ! (mot de passe oublié)
- Lundi 7 juillet 2008 - 09:36:20
- inscrits : 863223
- connectés : 21845
- questions/jour : 4839
- Taux de réponse : 81.71%
Algorithme c ompression Algorithme chainage avant Algorithme chiffre livre Algorithme classement math Algorithme coloriage de graphe c Algorithme combinaisons possible Algorithme compression jpeg Algorithme conversion nombre binaire en decimal Algorithme correction bcd addition Algorithme crible d'eratosthene Algorithme cryptage des Algorithme cryptage fichier texte Algorithme cryptage joomla Algorithme cryptage tps Algorithme produit cartesien Algorithme tri d'une liste chaînée double precedent suivant Ascii algorithm code Comment créer un algorithme Cour d'algorithme Cours algorithme cours Cours d'initiation à l'algorithmique Créer des fichiers par lagage algorithm Exercices algorithmique corrigés L'algorithmique cours debutant Les algorithmes combinatoire Recrutement capgémini test algorithmiquePlus
Ils ont besoin de votre aide
- 09:34 probleme de couleur (Vidéo numérique)
- 09:33 oui ou non (Windows)
- 09:33 aide profil skyrock (Internet)
- 09:33 mon ipod (Bureautique)
- 09:32 Voir film sur sa TV a partir du PC (Vidéo numérique)
- 09:31 BlueScreen à répétition .... (Matériel/Hardware)
Les règles à respecter Lire le texte complet de la charte
Salut,
j'aurais besoin d'aide pour ce projet.
Merci d'avance
SYNOPSIS graphes –dkpf [-o] [n] fichier
DESCRIPTION
Une des options au moins doit obligatoirement etre presente.Elles ne sont pas toutes mutuellement exclusives et certaines pourront etre demandées en meme temps.
Les graphes traités sont tous valués par des entiers,et peuvent contenir des aretes (i,i) ou i est un sommet.
Options
-o le resultat doit etre place dans un fichier de meme nom que le fichier d’entrée suffixe par .option
S’il y a plusieurs options,plusieurs fichiers devront etre crées.Ainsi la commende graphes –dp –o fic produira le fichier fic.d et fic.p
En cas d’absence de cette option les résultats seront affichés sur la sortie standart.
-d n plus courts chemins,ayant pour origine le sommet n.Si le graphe comporte des arcs de cout négatif on appliquera l’algo de Bellman-Ford.Si tous les arcs ont un cout positif,on appliquera l’algo de Dijkstra avec une file de priorité.
entrée fichier de type GRAPHE
sortie fichier de type LISTE contenant sur la i ème ligne la plus courte distance entre le sommet n et le sommet i suivie de la suite des sommets intermediaires sur le plus court chemin.S’il n’existe pas de plus court chemin entre n et i,la ligne sera vide.
exemple graphe oriente:
0->1 (poids 4),1->0(2),1->2(2),2->0(5),2->1(3)
graphe non oriente:
0--1(3),1--2(1),2--0(5)
-f plus courts chemins entre chaque couple de sommets,en appliquant l’algo de Warshall-Floyd.
entrée fichier de type GRAPHE
sortie fichier de type GRAPHE séparés par une ligne vide, le graphe des distances suivi du graphe des prédécesseurs sur un plus court chemin.
-p arbre recouvrant minimal par la méthode de Prim
entrée fichier de type GRAPHE
sortie fichier de type ARBRE
-k arbre recouvrant minimal par la méthode de Kruskal
Meme type de fichiers que pour l’option [-p]
FORMAT DES FICHIERS
Tous les entiers indiques sur une meme ligne sont separes par un unique caractère espace.Pas d’espace avant le premier ou après le dernier.
Toutes les lignes se terminent par \n
Les fichiers de format GRAPHE
Ces fichiers contiennent la description d’un graphe sous forme de matrice d’adjacence ou de listes d’adjacence.
première ligne : nombre de sommets
deuxième ligne : une lettre indiquant le type du graphe : o pour graphe orienté, n pour graphe non oriente
troisième ligne : une lettre indiquant le type de représentation du graphe, m pour matrice d’adjacence , l pour listes d’adjacence
lignes suivantes : les lignes de la matrice ou la suite des listes
Pour les graphes données en exemple
-Representation par matrice du graphe orienté
3
o
m
0 4 0
2 0 2
5 3 0
-representation par listes d’adjacence du graphe oriente
les arcs sont donnés sous forme de suites de 2 valeurs : cout sommet atteint
3
o
l
4 1
2 0 2 2
5 0 3 1
Cas d’un graphe non orienté
-Representation par matrice du graphe non orinente
On ne fournit que la matrice triangumaire supérieure
3
n
m
0 3 5
0 1
0
-Representation par listes d’ajacences du graphe non oriente :
un arc n’apparaît qu’une fois,associé à son extrémité de plus petit indice :
3
n
l
3 1 5 2
1 2
Remarques :
-si un sommet n’a pas d’arc sortant,la ligne correspondante dans les fichiers est réduite au caractère passage à la ligne.
-la plupart des algos fonctionnent le plus rapidement avec un type particulier de représentation en mémoire.A vous de convertir
A vous de convertir le sformats pour utiliser la representation en memoire la plus adaptée.
Les fichiers de format ARBRE
Première ligne : nombres d’arcs
Deuxieme ligne : poids de l’arbre
Lignes suivantes : sur chaque ligne ,un arc de l’arbre recouvrant (indique par un couple de sommets en ordre craoissant ),les differents couples etant tries dans l’ordre croissant.
Les fichiers de format LISTE
Sur chaque ligne,une liste de sommets
Pour tous les algos de distances ,lorsque la distance entre 2 sommets est infinie ,on affichera I
S’il existe un chemin non trivial(formé d’au moins un arc) d’un sommet à lui-meme ,le programme devra fournir la longueur du plus court ,et fournir la valeur 0 s’il n’y ap pas de chemin non trivial
En entrée ,l’absence d’arc est symbolisée par 0
Lorsqu’il y a plusieurs réponses possibles ,seule la plus petite dans l’ordre lexicographiqueest demandée.
Un graphe non oriente sera considere comme oriente dans les 2 sens.
Si le fichier en entrée est incorrect ,la sortie sera vide avec message d’erreur sur stderr.
j'aurais besoin d'aide pour ce projet.
Merci d'avance
SYNOPSIS graphes –dkpf [-o] [n] fichier
DESCRIPTION
Une des options au moins doit obligatoirement etre presente.Elles ne sont pas toutes mutuellement exclusives et certaines pourront etre demandées en meme temps.
Les graphes traités sont tous valués par des entiers,et peuvent contenir des aretes (i,i) ou i est un sommet.
Options
-o le resultat doit etre place dans un fichier de meme nom que le fichier d’entrée suffixe par .option
S’il y a plusieurs options,plusieurs fichiers devront etre crées.Ainsi la commende graphes –dp –o fic produira le fichier fic.d et fic.p
En cas d’absence de cette option les résultats seront affichés sur la sortie standart.
-d n plus courts chemins,ayant pour origine le sommet n.Si le graphe comporte des arcs de cout négatif on appliquera l’algo de Bellman-Ford.Si tous les arcs ont un cout positif,on appliquera l’algo de Dijkstra avec une file de priorité.
entrée fichier de type GRAPHE
sortie fichier de type LISTE contenant sur la i ème ligne la plus courte distance entre le sommet n et le sommet i suivie de la suite des sommets intermediaires sur le plus court chemin.S’il n’existe pas de plus court chemin entre n et i,la ligne sera vide.
exemple graphe oriente:
0->1 (poids 4),1->0(2),1->2(2),2->0(5),2->1(3)
graphe non oriente:
0--1(3),1--2(1),2--0(5)
-f plus courts chemins entre chaque couple de sommets,en appliquant l’algo de Warshall-Floyd.
entrée fichier de type GRAPHE
sortie fichier de type GRAPHE séparés par une ligne vide, le graphe des distances suivi du graphe des prédécesseurs sur un plus court chemin.
-p arbre recouvrant minimal par la méthode de Prim
entrée fichier de type GRAPHE
sortie fichier de type ARBRE
-k arbre recouvrant minimal par la méthode de Kruskal
Meme type de fichiers que pour l’option [-p]
FORMAT DES FICHIERS
Tous les entiers indiques sur une meme ligne sont separes par un unique caractère espace.Pas d’espace avant le premier ou après le dernier.
Toutes les lignes se terminent par \n
Les fichiers de format GRAPHE
Ces fichiers contiennent la description d’un graphe sous forme de matrice d’adjacence ou de listes d’adjacence.
première ligne : nombre de sommets
deuxième ligne : une lettre indiquant le type du graphe : o pour graphe orienté, n pour graphe non oriente
troisième ligne : une lettre indiquant le type de représentation du graphe, m pour matrice d’adjacence , l pour listes d’adjacence
lignes suivantes : les lignes de la matrice ou la suite des listes
Pour les graphes données en exemple
-Representation par matrice du graphe orienté
3
o
m
0 4 0
2 0 2
5 3 0
-representation par listes d’adjacence du graphe oriente
les arcs sont donnés sous forme de suites de 2 valeurs : cout sommet atteint
3
o
l
4 1
2 0 2 2
5 0 3 1
Cas d’un graphe non orienté
-Representation par matrice du graphe non orinente
On ne fournit que la matrice triangumaire supérieure
3
n
m
0 3 5
0 1
0
-Representation par listes d’ajacences du graphe non oriente :
un arc n’apparaît qu’une fois,associé à son extrémité de plus petit indice :
3
n
l
3 1 5 2
1 2
Remarques :
-si un sommet n’a pas d’arc sortant,la ligne correspondante dans les fichiers est réduite au caractère passage à la ligne.
-la plupart des algos fonctionnent le plus rapidement avec un type particulier de représentation en mémoire.A vous de convertir
A vous de convertir le sformats pour utiliser la representation en memoire la plus adaptée.
Les fichiers de format ARBRE
Première ligne : nombres d’arcs
Deuxieme ligne : poids de l’arbre
Lignes suivantes : sur chaque ligne ,un arc de l’arbre recouvrant (indique par un couple de sommets en ordre craoissant ),les differents couples etant tries dans l’ordre croissant.
Les fichiers de format LISTE
Sur chaque ligne,une liste de sommets
Pour tous les algos de distances ,lorsque la distance entre 2 sommets est infinie ,on affichera I
S’il existe un chemin non trivial(formé d’au moins un arc) d’un sommet à lui-meme ,le programme devra fournir la longueur du plus court ,et fournir la valeur 0 s’il n’y ap pas de chemin non trivial
En entrée ,l’absence d’arc est symbolisée par 0
Lorsqu’il y a plusieurs réponses possibles ,seule la plus petite dans l’ordre lexicographiqueest demandée.
Un graphe non oriente sera considere comme oriente dans les 2 sens.
Si le fichier en entrée est incorrect ,la sortie sera vide avec message d’erreur sur stderr.
Oui alors l'idée c'est qu'on n'est pas là pour faire ton projet. Donc il faut cibler un peu le problème et nous dire sur quoi tu bloques, et là on se fera un plaisir de t'aider :-) |
Je sais bien mais est ce que tu pourrais m'indiquer,les champs que tu mettrais pour la sructure matrice et liste. |
Une matrice se caractérise par les données qu'elle contient. Sauf qu'un tableau en C, on ne connait a priori pas sa taille sauf si on la passe en paramètre, donc il faut stocker le nombre de ligne et de colonne. Les cases de données seront allouées avec une fonction pour créer la matrice (l'équivalent du constructeur en C++), et détruite par une autre (par exemple dès que ut n'auras plus besoin de la matrice) (on parle en C++ de destructeur).
Ainsi, en C ça donne : #include <stdio.h>
struct matrix{
unsigned int nb_rows;
unsigned int nb_columns;
double **data;
};
struct matrix new_matrix(unsigned int nrows,unsigned int ncolumns){
unsigned int i;
struct matrix m;
m.nb_rows=nrows;
m.nb_columns=ncolumns;
m.data=(double **) malloc(sizeof(double *)*nrows);
for(i=0;i<nrows;++i){
m.data[i]=(double *) calloc(sizeof(double),ncolumns);
}
return m;
}
void del_matrix(struct matrix m){
unsigned int i;
for(i=0;i<m.nb_rows;++i){
free(m.data[i]);
}
free(m.data);
}
S'il y a des lignes que tu ne comprends pas n'hésite pas à demander. Pour les listes c'est plus simple. On manipule des maillons qui stockent des données, et un maillon suivant (en supposant qu'ils stockent des doubles, mais ça peut être une adresse sur un type générique, ie un pointeur de type void *) : struct maillon{
double data;
struct maillon * next;
};
typedef maillon * list;
Bonne chance |
bonsoir a tt j'arrive pas a programmer un graphe TAD
(" l'utilisateur doit entrez les ville et les distance+calcule largeur +pranfondeur +dijskraaaaaa") tt ça en orienter objet
|
Trucs & astuces pertinents trouvés dans la base de connaissances Plus d'astuces sur « Algorithmes en C »
Discussions pertinentes trouvées dans le forum
Plus de discussions sur « Algorithmes en C » Discussion en cours Discussion fermée Problème résolu
| 03/04 18h02 | algorithme construction diagramme Voronoi | Programmation | 03/04 18h02 | 0 |
| 29/12 19h05 | algorithme convertir nbre binaire à decimal | Programmation | 08/02 19h58 | 5 |
| 27/12 22h54 | Algorithme convertion nbre binaire en décimal | Programmation | 27/12 23h23 | 4 |
| 11/12 11h13 | algorithme cryptage | Linux/Unix | 24/06 19h46 | 9 |
| 20/11 20h59 | [algorithme]Calcul somme 1/n | Programmation | 16/05 10h15 | 14 |
Logiciels pertinents trouvés dans les téléchargements
Plus de logiciels gratuits sur « Algorithmes en C »
 | Caméléon - Tel le mimétisme du Caméléon, la stéganographie (qui vient du grec steganos, couvert et graphein, écriture et que l’on peut... | Catégorie: Chiffrement Licence: Freeware/gratuit |
 | CCleaner - CCleaner (Crap Cleaner) est un utilitaire de nettoyage gratuit permettant de garantir un respect de la vie privée en... | Catégorie: Anonymat/Confidentialité Licence: Freeware/gratuit |
 | Free Mp3 Wma Converter - Free Mp3 Wma Converter permet de convertir tout vos fichiers Mp3 , Wma , Ogg , AAC , m4a , mp4 , Ape , flac, Wav : ... | Catégorie: Conversion Licence: Freeware/gratuit |
 | PDF Creator - PDF Creator est un outil gratuit permettant de créer des PDF à partir de presque n'importe quelle application capable... | Catégorie: PDF Licence: Open Source |
Produits relatifs Plus de produits sur « Algorithmes en C »
