Grille de nombres-croises

Le
candide
Tous les prétextes sont bons pour faire du C : compléter la grille 4x4
ci-dessous par des chiffres décimaux (deux zéros sont déjà placés) en
sorte que tous les nombres de 4 chiffres (lus de la gauche vers la
droite ou de haut en bas) qui apparaissent soient des multiples de 97 :

0XXX
XX0X
XXXX
XXXX


Il n'y a pas que la solution triviale. Bon amusement.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 5
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Sylvain Togni
Le #17839381
candide a écrit :

Tous les prétextes sont bons pour faire du C : compléter la grille 4x4
ci-dessous par des chiffres décimaux (deux zéros sont déjà placés) en
sorte que tous les nombres de 4 chiffres (lus de la gauche vers la
droite ou de haut en bas) qui apparaissent soient des multiples de 97 :

0XXX
XX0X
XXXX
XXXX


Il n'y a pas que la solution triviale. Bon amusement.



0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

0 3 8 8
6 4 0 2
7 9 5 4
9 2 1 5

0 6 7 9
6 4 0 2
7 0 8 1
9 2 1 5

Mais quel rapport avec le C ?

--
Sylvain Togni
candide
Le #17840411
Sylvain Togni a écrit :

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0




OK, la solution triviale

0 3 8 8
6 4 0 2
7 9 5 4
9 2 1 5

0 6 7 9
6 4 0 2
7 0 8 1
9 2 1 5




La dernière solution est amusante, on obtient une matrice symétrique.

Mais quel rapport avec le C ?





Il s'agit de proposer du code C résolvant la question et de discuter de
ce code : respect de la norme, portabilité, variations possibles sur le
code, optimisations diverses, avantage à écrire ce code en C plutôt que
dans un autre langage, etc.

Bon, je vais donner l'exemple :



/* 97.c */

#include
#define NB_CHIFFRES 4
#define BASE 10

void afficher(int t[NB_CHIFFRES][NB_CHIFFRES])
{
int lig, col;

for (lig = 0; lig < NB_CHIFFRES; lig++)
{
for (col = 0; col < NB_CHIFFRES; col++)
printf("%d", t[lig][col]);
printf("n");
}
printf("nn");
}

void chiffres(int *t, int x)
{
int i;
int q;

for (i = 0; i < NB_CHIFFRES; i++)
{
q = x / BASE;
t[NB_CHIFFRES - i - 1] = x - BASE * q;
x = q;
}
}

int solve(void)
{
#define N 97
#define BORNE 10*10*10
int a, b, c, d;
int t[NB_CHIFFRES][NB_CHIFFRES];

for (a = 0; a < BORNE; a += N)
for (b = 0; b < BORNE; b += N)
for (c = 0; c < BORNE; c += N)
for (d = 0; d < BORNE; d += N)
{
int col = 0;

chiffres(&t[0][0], a);
if (t[0][0])
goto fin;
chiffres(&t[1][0], b);
if (t[1][2])
continue;
chiffres(&t[2][0], c);
chiffres(&t[3][0], d);

while (!(t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000 % N))
col++;
if (col == NB_CHIFFRES)
afficher(t);
}
fin:
return 0;
}

int main(void)
{
solve();

return 0;
}
/* Fin de 97.c */





$time ./x
0000
0000
0000
0000


0388
6402
7954
9215


0679
6402
7081
9215



real 0m6.411s
user 0m5.452s
sys 0m0.048s
Sylvain Togni
Le #17841001
OK, intéressant, nous n'avons pas choisi la même approche.
Voici la mienne (je te bas en nombre de ligne de code et en
vitesse, mais mon code n'est peut-être pas très propre) :

/* test.c */
#include
static void backtracking(int tab[], int i)
{
/* check last row */
if ((i%4) == 0 && i > 0)
{
if (((tab[i - 4]*1000 + tab[i - 3]*100 + tab[i - 2]*10 + tab[i - 1])%97) != 0)
return;
}

/* check columns */
if (i == 16)
{
int j;
for(j = 0; j < 4; ++j)
{
if (((tab[j]*1000 + tab[j + 4]*100 + tab[j + 8]*10 + tab[j + 12])%97) != 0)
return;
}
for(j = 0; j < 16; ++j)
printf("%d%c", tab[j], (j%4) < 3 ? ' ' : 'n');
printf("n");
}

/* next value */
if (tab[i] == -1)
{
int x;
for(x = 0; x < 10; ++x)
{
tab[i] = x;
backtracking(tab, i + 1);
}
tab[i] = -1;
}
else
{
backtracking(tab, i + 1);
}
}

int main(void)
{
static int tab[16] = {
0, -1, -1, -1,
-1, -1, 0, -1,
-1, -1, -1, -1,
-1, -1, -1, -1
};
backtracking(tab, 0);
return 0;
}
/* fin test.c */

$ time ./test.exe
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

0 3 8 8
6 4 0 2
7 9 5 4
9 2 1 5

0 6 7 9
6 4 0 2
7 0 8 1
9 2 1 5


real 0m2.016s
user 0m1.999s
sys 0m0.031s

--
Sylvain Togni
candide
Le #17841531
Sylvain Togni a écrit :
OK, intéressant, nous n'avons pas choisi la même approche.
Voici la mienne (je te bas en nombre de ligne de code et en
vitesse, mais mon code n'est peut-être pas très propre) :



Voici ce que ton code donne chez moi :

:~$ gcc -O2 -o y 97_2.c
:~$ time ./y
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Erreur de segmentation

real 0m0.049s
user 0m0.000s
sys 0m0.000s
:~$
Sylvain Togni
Le #17841711
candide a écrit :

:~$ gcc -O2 -o y 97_2.c
:~$ time ./y
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Erreur de segmentation

real 0m0.049s
user 0m0.000s
sys 0m0.000s
:~$



T'as vu ça, il est rapide :-)

C'est bizarre il fonctionne chez moi avec VC8 et gcc 3.4.4.
Par contre le tiens ne marche avec aucun des deux.
Quel version de gcc et sur quelle architecture ?

--
Sylvain Togni
candide
Le #17842721
Sylvain Togni a écrit :


Par contre le tiens ne marche avec aucun des deux.



Il marche pas : c'est-à-dire ? il compile pas ou t'as une erreur à
l'exécution ?

Quel version de gcc et sur quelle architecture ?




version gcc 4.2.3 (Ubuntu 4.2.3-2ubuntu7)
candide
Le #17842811
Sylvain Togni a écrit :
candide a écrit :

:~$ gcc -O2 -o y 97_2.c
:~$ time ./y
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Erreur de segmentation

real 0m0.049s
user 0m0.000s
sys 0m0.000s
:~$



T'as vu ça, il est rapide :-)

C'est bizarre il fonctionne chez moi avec VC8 et gcc 3.4.4.
Par contre le tiens ne marche avec aucun des deux.
Quel version de gcc et sur quelle architecture ?




Voici ce que me donne gdb :

(gdb) r
Starting program: /home/candide/y
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0


Program received signal SIGSEGV, Segmentation fault.
0x0804856d in backtracking (tab=0x8049800, iQ2) at 97_2.c:28
(gdb)
La ligne 28 étant :

if (tab[i] == -1)


tu as vu que tu as un iQ2.
Sylvain Togni
Le #17842931
candide a écrit :

Il marche pas : c'est-à-dire ? il compile pas ou t'as une erreur à
l'exécution ?



Il ne trouve aucune solution.

Mais en remplaçant
#define BORNE 10*10*10
par
#define BORNE 10*10*10*10
et
while (!(t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000 % N))
par
while (col < 4 && !((t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000) % N))
il fonctionne et ne met que 0.5s.

--
Sylvain Togni
Sylvain Togni
Le #17843071
candide a écrit :

Voici ce que me donne gdb :

(gdb) r
Starting program: /home/candide/y
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0


Program received signal SIGSEGV, Segmentation fault.
0x0804856d in backtracking (tab=0x8049800, iQ2) at 97_2.c:28
(gdb)
La ligne 28 étant :

if (tab[i] == -1)


tu as vu que tu as un iQ2.



Ah oui, il manque un return

/* test.c */
#include
static void backtracking(int tab[], int i)
{
/* check last row */
if ((i%4) == 0 && i > 0)
{
if (((tab[i - 4]*1000 + tab[i - 3]*100 + tab[i - 2]*10 + tab[i - 1])%97) != 0)
return;
}

/* check columns */
if (i == 16)
{
int j;
for(j = 0; j < 4; ++j)
{
if (((tab[j]*1000 + tab[j + 4]*100 + tab[j + 8]*10 + tab[j + 12])%97) != 0)
return;
}
for(j = 0; j < 16; ++j)
printf("%d%c", tab[j], (j%4) < 3 ? ' ' : 'n');
printf("n");


return;
}

/* next value */
if (tab[i] == -1)
{
int x;
for(x = 0; x < 10; ++x)
{
tab[i] = x;
backtracking(tab, i + 1);
}
tab[i] = -1;
}
else
{
backtracking(tab, i + 1);
}
}

int main(void)
{
static int tab[16] = {
0, -1, -1, -1,
-1, -1, 0, -1,
-1, -1, -1, -1,
-1, -1, -1, -1
};
backtracking(tab, 0);
return 0;
}
/* fin test.c */



--
Sylvain Togni
Jean-Marc Bourguet
Le #17843061
Sylvain Togni
OK, intéressant, nous n'avons pas choisi la même approche.
Voici la mienne (je te bas en nombre de ligne de code et en
vitesse, mais mon code n'est peut-être pas très propre) :

/* test.c */
#include
static void backtracking(int tab[], int i)
{
/* check last row */
if ((i%4) == 0 && i > 0)
{
if (((tab[i - 4]*1000 + tab[i - 3]*100 + tab[i - 2]*10 + tab[i - 1])%97) != 0)
return;
}

/* check columns */
if (i == 16)
{
int j;
for(j = 0; j < 4; ++j)
{
if (((tab[j]*1000 + tab[j + 4]*100 + tab[j + 8]*10 + tab[j + 12])%97) != 0)
return;
}
for(j = 0; j < 16; ++j)
printf("%d%c", tab[j], (j%4) < 3 ? ' ' : 'n');
printf("n");



Il manque un return ici.

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Publicité
Poster une réponse
Anonyme