Je m'exerce actuellement sur la piscine de l'école 42, et je suis a l'exercice des dix dames.
J'ai vu que c'était un problème fréquemment posé en informatique.
Du coup, j'en suis seulement au début, mon but pour le moment est d'arriver à afficher seulement une solution. Je verrais pour toutes les afficher après.
J'ai un début de programme qui me paraissait pas trop mal, j'ai compilé et la, surprise, segmentation faut.
J'ai cherché un moment mais je ne trouve pas. Quelqu'un aurait des pistes?
Voila le code :
#include <stdio.h>
#include <unistd.h>
void ft_putchar(char c)
{
write(1, &c, 1);
}
void ft_check_diagonales(int tab[10][10],int x, int y,int *wrong)
{
int i;
int j;
int tmp;
if(x >= y)
{
i = x - y;
j = 0;
tmp = (10 + y) - x;
while(x <= tmp)
{
if(tab[j][i] == 1)
*wrong += 1;
i++;
j++;
tmp++;
}
}
else if (x < y)
{
i = 0;
j = y - x;
tmp = (10 + x) - y;
while(y <= tmp)
{
if(tab[j][i] == 1)
*wrong += 1;
i++;
j++;
tmp++;
}
}
}
int ft_check_line_and_column(int tab[10][10], int x, int y)
{
int i;
int j;
int wrong;
wrong = 0;
i = 0;
j = 0;
while(i <= 9)
{
if (tab[x][i] == 1)
wrong++;
i++;
}
while(j <= 9)
{
if (tab[j][y] == 1)
wrong++;
j++;
}
ft_check_diagonales(tab, x, y, &wrong);
if (wrong == 0)
return(0);
return(1);
}
void ft_recursive_placement(int tab[10][10], int x, int y)
{
if(x == 9 || y == 9)
return;
if(ft_check_line_and_column(tab, x, y) == 0)
{
tab[y][x] = 1;
ft_putchar(x + '0');
x = 0;
y++;
}
else
{
x++;
ft_recursive_placement(tab, x, y);
}
}
int ft_ten_queens_puzzle(void)
{
int x;
int y;
x = 0;
y = 0;
int tab[10][10] = {{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0}};
ft_recursive_placement(tab, x, y);
printf("%d,",tab [0][0]);
return(0);
}
int main()
{
ft_ten_queens_puzzle();
return(0);
}
- Edité par ThéoArchimbaud 6 octobre 2021 à 22:09:57
Ce n'est pas la piscine de l'école 42 qui va t'apprendre à coder efficacement. Savent-ils ce qu'est la récursivité? On met dans une liste les positions possibles et on les essaie. - #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <time.h> #define NB_DAMES 10 int compteur = 0; bool display(int echiquier[]) { // On peut jouer avec cette fonction pour tout afficher, ou s'arrêter après la première solution trouvée (ou la Nième) compteur++; return false; // true si on arrête après la première } bool placer(int echiquier[], int curr) { if(curr >= NB_DAMES) { return display(echiquier); } int liste[NB_DAMES]; int l = 0; for(int n=0; n < NB_DAMES; n++) { int i; for(i=0; i < curr; i++) if(echiquier[i]==n || abs(echiquier[i]-n)==curr-i) break; if(i == curr) liste[l++] = n; } for(int n=0; n < l; n++) { echiquier[curr] = liste[n]; if(placer(echiquier, curr+1)) return true; } return false; } int main() { int tab[NB_DAMES]; clock_t t0 = clock(); placer(tab, 0); printf("Temps consommé: %5.3f\n",(double)(clock()-t0)/CLOCKS_PER_SEC); printf("%d\n", compteur); }
Le Tout est souvent plus grand que la somme de ses parties.
si tu veux entrer dans un monde de développement alors il va falloir non seulement apprendre à coder mais aussi à débuguer. Nous ne sommes pas des super héros qui trouvent tous les problèmes d'un coup d'un seul en lisant simplement un code, nous utilisons des outils.
La première chose à faire est de compiler en mode débug (option -g avec gcc) et en demandant au compilateur d'afficher des warnings (options courantes : -Wall -Wextra) :
$ gcc -g -Wall -Wextra -o ft ft.c
$
Ici rien à signaler … tu peux aussi essayer l'option -fanalyzer avec un gcc récent (≥9 je crois), mais ici ça ne change rien.
Ensuite si tu as un segfault alors il est toujours utile d'utiliser un memory profiler (comme valgrind) qui va tracker tes erreurs de manipulation de mémoire dans ton code :
$ valgrind --leak-check=full --show-reachable=yes --track-origins=yes ./ft
==73713== Memcheck, a memory error detector
==73713== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==73713== Using Valgrind-3.17.0 and LibVEX; rerun with -h for copyright info
==73713== Command: ./ft
==73713==
==73713== Conditional jump or move depends on uninitialised value(s)
==73713== at 0x1091E0: ft_check_diagonales (ft.c:22)
==73713== by 0x109349: ft_check_line_and_column (ft.c:66)
==73713== by 0x1093A4: ft_recursive_placement (ft.c:76)
==73713== by 0x10946E: ft_ten_queens_puzzle (ft.c:106)
==73713== by 0x1094AE: main (ft.c:113)
==73713== Uninitialised value was created by a stack allocation
==73713== at 0x4898A50: (below main) (in /usr/lib/libc-2.33.so)
==73713==
==73713== Invalid read of size 4
==73713== at 0x1091DA: ft_check_diagonales (ft.c:22)
==73713== by 0x109349: ft_check_line_and_column (ft.c:66)
==73713== by 0x1093A4: ft_recursive_placement (ft.c:76)
==73713== by 0x10946E: ft_ten_queens_puzzle (ft.c:106)
==73713== by 0x1094AE: main (ft.c:113)
==73713== Address 0x1fff001028 is not stack'd, malloc'd or (recently) free'd
==73713==
==73713==
==73713== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==73713== Access not within mapped region at address 0x1FFF001028
==73713== at 0x1091DA: ft_check_diagonales (ft.c:22)
==73713== by 0x109349: ft_check_line_and_column (ft.c:66)
==73713== by 0x1093A4: ft_recursive_placement (ft.c:76)
==73713== by 0x10946E: ft_ten_queens_puzzle (ft.c:106)
==73713== by 0x1094AE: main (ft.c:113)
==73713== If you believe this happened as a result of a stack
==73713== overflow in your program's main thread (unlikely but
==73713== possible), you can try to increase the size of the
==73713== main thread stack using the --main-stacksize= flag.
==73713== The main thread stack size used in this run was 8388608.
==73713==
==73713== HEAP SUMMARY:
==73713== in use at exit: 0 bytes in 0 blocks
==73713== total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==73713==
==73713== All heap blocks were freed -- no leaks are possible
==73713==
==73713== For lists of detected and suppressed errors, rerun with: -s
==73713== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)
Le second message (invalid read of size 4) indique que tu essayes de lire en dehors du tableau en ligne 22 … ensuite avec un débugger (gdb par exemple) et avec un pas à pas après avoir mis break sur la ligne 22 tu en arriveras aux même conclusions que edgarjacobs …
$ gdb ./ft
GNU gdb (GDB) 11.1
Copyright (C) 2021 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./ft...
(gdb) b 22
Breakpoint 1 at 0x11b7: file ft.c, line 22.
(gdb) run
Starting program: /home/fred/Desktop/ft
Breakpoint 1, ft_check_diagonales (tab=0x7fffffffe450, x=0, y=0, wrong=0x7fffffffe3fc) at ft.c:22
22 if(tab[j][i] == 1)
(gdb) display i
1: i = 0
$ gdb ./ft
GNU gdb (GDB) 11.1
Copyright (C) 2021 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./ft...
(gdb) b 22
Breakpoint 1 at 0x11b7: file ft.c, line 22.
(gdb) run
Starting program: /home/fred/Desktop/ft
Breakpoint 1, ft_check_diagonales (tab=0x7fffffffe450, x=0, y=0, wrong=0x7fffffffe3fc) at ft.c:22
22 if(tab[j][i] == 1)
(gdb) display i
1: i = 0
$ gdb ./ft
GNU gdb (GDB) 11.1
Copyright (C) 2021 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-pc-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./ft...
(gdb) b 22
Breakpoint 1 at 0x11b7: file ft.c, line 22.
(gdb) run
Starting program: /home/fred/Desktop/ft
Breakpoint 1, ft_check_diagonales (tab=0x7fffffffe450, x=0, y=0, wrong=0x7fffffffe3fc) at ft.c:22
22 if(tab[j][i] == 1)
(gdb) display i
1: i = 0
(gdb) display j
1: j = 0
gdb) n
24 i++;
1: i = 0
2: j = 0
(gdb) n
25 j++;
1: i = 1
2: j = 0
(gdb) n
26 tmp++;
1: i = 1
2: j = 1
(gdb) n
20 while(x <= tmp)
1: i = 1
2: j = 1
(gdb) n
Breakpoint 1, ft_check_diagonales (tab=0x7fffffffe450, x=0, y=0, wrong=0x7fffffffe3fc) at ft.c:22
22 if(tab[j][i] == 1)
1: i = 1
2: j = 1
....
Acquérir ces compétences te permettras de ne plus avoir recours à nous et à aller plus vite dans ton développement, C'est évidemment un atout considérable si tu entres en piscine, car si tu savais le nombre de messages quand les jeunes plongent …
Sinon, un peu HS, oui le problème des 8 reines ou sa généralisation, le problème des N reines est un grand classique dès que l'on aborde le backtracking. Il y a beaucoup de littérature sur le sujet et il y a quelques optimisations à découvrir, pas tant dans la manière d'implémenter un backtracking mais plus dans la manière d'aborder un sujet avant de commencer à pisser du code.
C'est vrai que toi dès le début tu savais déjà tout. Parler correctement c'est bien aussi. Personne te force à répondre, même si c'est la 400e personne à poster sur le même sujet et que la réponse se trouve surement parmi ceux-là.
Regardes la date de ton inscription, la mienne et celle de White Crow. Crois-tu que j'ai "pissé" mon code en 30 secondes sans y réfléchir?
C'est bien là le problème, c'est que vous croyez qu'un débutant, (parce que les gens qui sont à 42 sont des débutants au cas ou vous ne le sauriez pas), vont vous pondre un code de pro ? Quoi que ? moi qui suis aussi débutant, des codes fort semblable au tien, j'en ai trouvé sur le net. Mais ce n'est pas en le postant que ça fait de moi un pro.
@noceer: Regardes la date de ton inscription, la mienne et celle de White Crow. Crois-tu que j'ai "pissé" mon code en 30 secondes sans y réfléchir?
Tu te méprend, c'est pas ce que j'ai voulu dire.. et je ne m'adressais pas à toi.
EDIT: quoi qu'il en soit, oublions ça.
- Edité par noceer il y a environ 1 heure
«pisser du code» est une expression qui n'est en rien offensante. Elle signifie simplement que l'on se met à taper du code à la volée sans trop réfléchir en dehors de la boîte, sans prendre aucun recul ; malheureusement c'est souvent ce que provoque la piscine …
Je ne préfère pas oublier … c'est normal de ne pas comprendre le jargon qui, parfois, je le reconnais volontiers, est un peu ancien.
Je te prierai de remarquer le détail de ma réponse qui, je l'espère, est très informative non seulement pour le PO mais également pour d'autres lecteurs … surtout les futurs participants à la piscine …
Ne penses-tu pas Noceer, maintenant que je t'ai peut-être mieux expliqué le fond de ma démarche, que ta réaction a été un peu exagérée ?
Eh bien eh bien, je ne m'attendais pas a autant de réaction!
Alors en effet, a la base je cherchais seulement une piste de réflexion, pas une réponse toute faite...!
Mais du coup je me rends compte que je peux très largement améliorer mon code, merci a toi PierrotleFou. Pour ce qui est de l'école 42, je laisse chacun avoir son propre avis, je me suis déjà fait le mien.
Quand à toi WhiteCrow, je demandais un coup de main justement parce que je ne trouvais pas la réponse, et que j'avais déjà cherché avant (Ce qui vous paraitra peut être évident comme erreur dans mon code ne l'est pas encore pour moi!). Mais merci pour tes infos. Pour ce qui est de la piscine, je la connais je l'ai déjà faite.
Et enfin, en effet en survolant je n'ai pas trouvé le topic que je cherchais par rapport à ma réponse, mais j'aurais surement trouvé mieux en creusant un peu plus..!
Bref merci pour vos réponses j'ai pu avancer un peu.
Quand à toi WhiteCrow, je demandais un coup de main justement parce que je ne trouvais pas la réponse, et que j'avais déjà cherché avant (Ce qui vous paraitra peut être évident comme erreur dans mon code ne l'est pas encore pour moi!). Mais merci pour tes infos. Pour ce qui est de la piscine, je la connais je l'ai déjà faite.
[...] PS: Détendez vous un peu quand meme 👌👌👌
Cela est tout autant «pas évident» pour nous que pour toi, nous n'avons aucun super pouvoir, juste de super outils. C'est bien pour cela que j'ai essayé de te montrer que le débugage est une compétence qui s'acquiert, non pas en demandant de l'aide sur un forum mais en utilisant des outils adaptés (debuger, memory profiler, compiler avec les bonnes options …).
Le gros souci de 42 est que la piscine produit de nombreux étudiants qui se focalisent uniquement sur le code et pas sur l’écosystème qui permet de produire du code fonctionnel et correct (pas tous, évidemment, certains savent utiliser ces outils dont on leurs parle peu ou pas). Et là je n'aborde pas tout ce qui concerne l'approche algorithmique, les techniques de conception et de développement, les tests …
Mon but n'était que de te donner une gaule pas un poisson. Et je t'assure autant que je peux asurer à Noceer que je n'ai jamais voulu être offensant. Ce n'est pas de ta faute si on t'apprend à pisser du code.
D'après ce que je constate sur la piscine 42 de Québec et les contacts que j'ai eu avec eux, ils ne veulent pas êttre remis en qquestion. Ils n'enseignent rien sur aucun langage de programmation, même chose sur l'algorithmique. La programmation modulaire, la gestion de projets, le debugging, ils ne connaissent pas. ils ne parlent pas non plus des façons de faire des recherche sur Internet. Ça ressemble plus à un club social qu'à autre chose ...
Le Tout est souvent plus grand que la somme de ses parties.
se renseigner sur les outils de debugage c’est bien
relire le code c’est bien
erreur de depart trouve.
Et un debutant n’est pas forcement au courant de tout ce qu’il y a autour outil de debugage ... c’est bien pour cela qu’il est toujours debutant. 🤣
[...]
«se renseigner» est bien ? noooon …
apprendre à débuguer est indispensable, et débuguer n'est pas qu'utiliser un debuger …
Ne pas apprendre à utiliser ces outils quand on donne une formation est juste la preuve qu'il s'agit d'une formation ou complètement foirée ou hyper élitiste où ceux qui ne peuvent apprendre par eux-mêmes sont largués sans parachute.
Ce n'est pas pour rien que de nombreux intervenants insistent parfois lourdement sur cet aspect … apprendre à programmer n'est pas que pisser du code.
Je ne dis pas le contraire justement je fais un résumé foireux de tout ce debat. Je ne pense pas que ce soit de sa faute qu'on ne lui en ai pas parlé. Les remarques dites ici devraient etre directement adressé aux concernés. En tous cas de ma vision des choses c'est un debutant qui n'a pas connaissance de tous les outils indispensables et si on ne lui en pas parlé ce n'est pas de sa faute c'est ce de quoi je parlais. Les partis pris n'ont pas lieu d'etre normalement ou il faut directement aller voir l' ecole en question, de ma vision des choses.
Peut etre que pour toi ce que tu disais etait réellement dans le but d'aider mais aussi de lui faire prendre conscience je dis pas le contraire mais en lisant les messages j'avais plus l'impression que a travers lui tu faisais comprendre ton partis sur l'ecole en question.
Ah ? Je me demande bien quelle partie de ma réponse au PO dénigrait 42 ? Je pense que montrer non seulement les outils mais donner un aperçu de leur utilisation et buts rentre bel et bien dans la catégorie «aider».
Je ne tiens pas cette formation en haute estime, c'est clair … mais après chacun fait ce qu'il veut ou peut. X. Niel a ce côté businessman qui aime mettre le «1337» en avant … ce n'est que du marketing mais qui peut faire des dégâts parmi les jeunes qui entrent en piscine comme on entre dans les ordres …
On dirait que il y en a qui croit que la Piscine ce sont des cours. Non, c'est une épreuve de sélection de quelque semaine ou les inscrits doivent ce débrouiller par eux même. Il faut donc savoir de quoi on parle.
@Zero.c: Mais ça on ne le dis pas sur leurs sites. On n'a pas besoin de cours, on va tout trouver ensemble ...
Le Tout est souvent plus grand que la somme de ses parties.
Les dix dames
× 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.
On écrit "j'ai tort", pas "tord" qui est le verbe "tordre" à la 3ème personne de l'indicatif présent
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
On écrit "j'ai tort", pas "tord" qui est le verbe "tordre" à la 3ème personne de l'indicatif présent
yasakani no magatama
yasakani no magatama
Le Tout est souvent plus grand que la somme de ses parties.