Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Grille de nombres-croises

48 réponses
Avatar
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.

10 réponses

1 2 3 4 5
Avatar
Sylvain Togni
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
Avatar
candide
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 <stdio.h>

#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
Avatar
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 <stdio.h>

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
Avatar
candide
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
:~$
Avatar
Sylvain Togni
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
Avatar
candide
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)
Avatar
candide
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.
Avatar
Sylvain Togni
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
Avatar
Sylvain Togni
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 <stdio.h>

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
Avatar
Jean-Marc Bourguet
Sylvain Togni <"sylvain.togni at visionobjects.com"> writes:

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 <stdio.h>

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
1 2 3 4 5