J'ai un projet d'info à faire dans lequel on doit recréer un SAT-solveur. Mon programme compile, mais lors de l'exécution ... erreur de segmentation. J'ai donc restreint mon main à une petite fonction et à nouveau erreur de segmentation, je ne sais pas d'où elle vient... je vous mets en dessous ma fonction, ainsi que la définition de mes structures... Merci d'avance !
typedef struct {
long int valeur;
long int nb;
long int indice;
}cases;
typedef struct{
cases max;
cases min;
long int nb_max; //taille du tableau
cases tab_cases[1000000000];
}inventaire;
Il nous manque le main. Allouer un aussi grand tableau sur la pile, ça ne doit pas trop faire plaisir, donc il faudrait peut-être passer par une allocation dynamique pour tab_cases. Ta fonction initialisation_cases revient à cases c = {0}.
et l'erreur je ne sais pas d'où elle vient justement --' ça seg fault direct
int main(){
inventaire i;
initialisation_inventaire(&i);
return 0;
}
yo@n97one a écrit:
Allouer un aussi grand tableau sur la pile, ça ne doit pas trop faire plaisir, donc il faudrait peut-être passer par une allocation dynamique pour tab_cases. Ta fonction initialisation_cases revient à cases c = {0}.
bonjour,
merci ! oui, c'est vrai que le tableau est énorme, il y a moyen que je le change, mais est ce que cela changera quelque chose ? ou l'erreur de segmentation est due à la taille de mon tableau ?
pour initialisation_cases si je mets c = {0} ca marche ?
- Edité par NaeliaChesnot 23 avril 2019 à 16:01:36
Pour déboguer une erreur de segmentation tu peux utiliser un débogueur : en faisant une backtrace tu verras tout de suite où c'est que ça plante, et tu pourras par la suite remonter à "pourquoi ça plante".
Tu peux utiliser gdb pour ça. Si tu utilises un IDE, regarde les fonctionnalités de ton IDE pour lancer ton programme en mode Debug.
Réserver 1 000 000 000 * sizeof(cases) octets sur la pile, ça ne va pas le faire lors de l'exécution.
Je suppose que tu as pris ce nombre pour ne pas risquer un dépassement. Néanmoins, quid si par hasard, il devait y avoir 1 000 000 001 données ? Les valeurs fixes, dans un programme comme le tien, ça n'a rien de bon.
Il va falloir qe tu passes par l'allocation dynamique (malloc, realloc, calloc)
- Edité par edgarjacobs 23 avril 2019 à 16:17:01
On écrit "j'ai tort", pas "tord" qui est le verbe "tordre" à la 3ème personne de l'indicatif présent
je viens d'utiliser gdb et justement il me dit qu'il y a un soucis dans mon initialisation... comment fait-on pour entrer dans la fonction ?
ok pour la taille du tableau je vais faire un tableau à taille variable,
juste par curiosité j'ai baissé le nombre de cases de mon tableau à 10000, si je relance mon main, plus d'erreur de segmentation par contre, si je relance le main principal faisant appel à d'autre fonction, erreur de segmentation à nouveau... j'ai donc utilisé gdb et là, à nouveau l'erreur viendrait de cette fonction... j'y comprends plus rien
ci dessous voici les fonctions, mais comme il y en a beaucoup, je vous ai juste mis le .s ainsi que la fonction qui appelle la fonction d'initialisation plus haut
#ifndef _SAT_SOLVEUR_H
#define _SAT_SOLVEUR_H
typedef enum {VALIDE, INVALIDE, INCONNU}etat;
typedef struct{
long int valeur;
etat em;
}monome;
typedef struct{
etat ec;
long int monome_inval;
long int monome_val;
monome tab_monome[2];
}clause;
typedef struct {
etat ef;
long int nb_clause;
long int nb_variable;
long int nb_clause_val;
long int nb_clause_inval;
clause tab_clause[100000];
}formule;
typedef struct {
long int valeur;
long int nb;
long int indice;
}cases;
typedef struct{
cases max;
cases min;
long int nb_max; //taille du tableau
cases tab_cases[100000];
}inventaire;
/* récupère le nombre de clause d'une formule*/
long int nb_clause(formule f);
/* récupère le nombre de variable d'une formule*/
long int nb_variable(formule f);
/* récupère le nombre de clause valide d'une formule*/
long int nb_clause_val(formule f);
/* récupère le nombre de clause invalide d'une formule*/
long int nb_clause_inval(formule f);
/* récupère l'état d'une formule*/
etat etat_f(formule f);
/* met à jour l'état de la formule en fonction des nombres de clauses valides et invalides*/
etat mise_a_jour_etat_formule(formule f);
/* met à jour l'état de la formule en fonction des nombres de monome valides et invalides*/
etat mise_a_jour_etat_clause(clause c);
/* met à jour l'état de la formule en fonction d'une variable*/
etat mise_a_jour_etat_monome(monome a, long int v);
/*initialise une formule*/
formule initialisation_formule();
/*initialise une clause*/
clause initialisation_clause();
/*initialise un monome*/
monome initialisation_monome();
/*initialise une case*/
cases initialisation_cases();
/*initialise un inventaire*/
void initialisation_inventaire(inventaire* i);
/*lit un fichier DIMACS et le transforme en formule*/
formule lecture_dimacs_ecriture_formule_inventaire(FILE* fich,inventaire* inv);
/* trouve la variable avec le plus d'apparition et celle avec le moins*/
void min_max_inventaire(inventaire* i);
/*à partir d'une clause, met à jour l'inventaire*/
inventaire mise_a_jour_inventaire(inventaire i, clause c);
/*faire la propagation sur une clause de l'assignation d'un monome
i etant l'indice de la clause à traiter dans la formule et a étant l'assignation que l'on a choisit pour la propagation*/
void propagation_clause(clause* c, inventaire* inv, long int a );
/*choix des littéraux sur lesquels brancher*/
monome choix_branchement(inventaire* i);
/* algorythme de david putnam logemann loveland (dppl) permettant de determiné la satisfaisabilité d'une formule
f correspond à la formule cnf à traiter,
a correspond au monome que l'on propage sur la formule
i correpond à l'inventaire de notre formule
tour permet de savoir de tourner en rond en effet si l'on a la formule fausse pour a et pour -a, il faut pouvoir s'arreter, quand tour = 0, et que a rend invalide la formule on appelle dpll avec -a et tour = 1, ainsi si -a rend aussi la formule invalide on sait que l'on a pas besoin de retester avec l'opposé de a
idée générale de l'algo :
on parcourt les clauses tant qu'il n'y a pas de clause rendu invalide à cause du choix de l'assignation du monome a
on met à jour les clauses en fonction de l'assignation du monome choisi
si il y a une clause invalide alors
on rappelle DPLL avec la même formule mais avec l'assignation opposé du même monome et on initialise tour à 1 si tour était à 0, si tour était à 1 alors on renvois invalide (faux)
on récupère la valeur de cet appel et on le renvois.
sinon
on appelle la fonction permettant de choisir une assignation, on récupère le monome
on appelle DPLL avec la même formule et le nouveau monome assigné
on récupère la valeur de cet appel et on le renvois.
*/
void algo_DPLL(formule* f, monome a, inventaire* inv, long int tour);
/*fonction appelant les autres afin de gerer les appels,
création d'une formule vide, et d'un inventaire vide,
puis lecture du fichier dimacs etremplissage de la formule et de l'inventaire
choisi le litteral sur lequel brancher
effectue la propagation et continue.
*/
long int main_formule(FILE* fichier);
#endif
long int main_formule(FILE* fichier){
long int j,i,tour;
monome a;
formule f;
clause c;
inventaire inv;
initialisation_inventaire(&inv);
min_max_inventaire(&inv);
f=lecture_dimacs_ecriture_formule_inventaire(fichier,&inv);
a=choix_branchement(&inv);
tour=0;
algo_DPLL(&f,a,&inv, tour);
if (f.ef==VALIDE){
printf("La formule est satisfaisable\n l'un des modèles est : \n");
for(j=0;j<inv.nb_max;j++){
c=f.tab_clause[inv.tab_cases[j].indice];
i=0;
while (abs(c.tab_monome[i].valeur)!=abs(inv.tab_cases[j].valeur) && i<3){ //i< 3 normalement inutile
i++;
}
a=c.tab_monome[i];
switch (a.em) {
case VALIDE : if (a.valeur<0){
printf(" %ld = faux ;",-a.valeur);
}
else{
printf(" %ld = vrai ;",a.valeur);
}
break;
case INVALIDE : if (a.valeur>0){
printf(" %ld = faux ;",a.valeur);
}
else{
printf(" %ld = vrai ;",-a.valeur);
}
break;
default : if (a.valeur>0){
printf(" %ld = faux ;",a.valeur);
}
else{
printf(" %ld = vrai ;",-a.valeur);
}
break;
}
}
printf("\n");
}
else{
printf("la formule est insatisfaisable, il n'y a donc pas de modèle possible\n");
}
return 1;
}
Si tu fais run, tu obtiens l'erreur de segmentation : à ce moment, tu peux faire "backtrace" afin d'avoir la pile d'appel des fonctions. ça te permettra de savoir à quelle ligne exactement se produit le seg fault.
A noter que tu dois compiler en mode debug, c'est à dire avec l'option -g
Pour aller plus loin, une fois que tu as fais ton backtrace, tu peux printer les variables courantes avec "print var"
Par exemple, pour déboguer le segfault de ce code là :
#include <stdio.h>
#include <stdlib.h>
#define TAILLE 100
void f(int *t, int taille){
int i, j;
for (i = 0; i < taille; i++){
j = i*i;
t[j] = 42;
}
}
int main(void){
int t[TAILLE];
int i;
f(t, TAILLE);
for (i = 0 ; i < 10; i++)
printf("%d ", t[i]);
printf("\n");
}
J'utilise :
(gdb) run
Starting program: /home/sixcy/Documents/truc
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400588 in f (t=0x7fffffffde70, taille=100) at truc.c:11
11 t[j] = 42;
(gdb) bt
#0 0x0000000000400588 in f (t=0x7fffffffde70, taille=100) at truc.c:11
#1 0x00000000004005bb in main () at truc.c:19
(gdb) p j
$1 = 1156
(gdb) p taille
$2 = 100
(gdb)
(bt est un raccourci pour backtrace, p est un raccourci pour print)
Je vois que j est supérieur à la taille du tableau, d'où le seg fault.
Si le seg fault est dans une fonction que tu n'as pas écrite, tu peux printer les arguments de la fonction pour regarder si tu vois quelque chose qui cloche.
Cette page donne une liste des causes courantes de seg fault
A noter que tu peux aussi utiliser valgrind - ce dernier va te faire remonter toutes les lectures et écritures invalides que tu fais dans ton programme.
- Edité par potterman28wxcv 23 avril 2019 à 17:13:56
Ca peut faire que du bien de savoir comment ca marche derriere le code, histoire de coder plus propre et plus opti et d'eviter les gros segfault, abort, overflow ect
erreur de segmentation
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
« Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »
D. Mendeleïev
On écrit "j'ai tort", pas "tord" qui est le verbe "tordre" à la 3ème personne de l'indicatif présent