Grille de nombres-croises

On 15 nov, 01:09, candide <cand...@free.invalid> wrote:

Ci-dessous le code modifié :

Quelques simplifications légères.

#include <stdio.h>
#include <assert.h>

#define NB_CHIFFRES 4

static void afficher (int (*t)[NB_CHIFFRES])
{
int lig;

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

}

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

for (i = 0; i < NB_CHIFFRES; i++)
{
int q = x / 10;

assert (NB_CHIFFRES - i - 1 >= 0);
t[NB_CHIFFRES - i - 1] = x - 10 * q;
x = q;
}
}

static int solve (void)
{
#define N 97
#define BORNE 10000

int t[NB_CHIFFRES][NB_CHIFFRES];
int a;
for (a = 0; a < BORNE; a += N)
{
int b;
chiffres (&t[0][0], a);
if (t[0][0] != 0)
{
break;
}
for (b = 0; b < BORNE; b += N)
{
int c;
chiffres (&t[1][0], b);
if (t[1][2] != 0)
{
continue;
}
for (c = 0; c < BORNE; c += N)
{
int d;
chiffres (&t[2][0], c);
for (d = 0; d < BORNE; d += N)
{
int col = 0;

chiffres (&t[3][0], d);

while (col < 4
&& (t[3][col] + t[2][col] * 10 + t[1][col] * 100
+
t[0][col] * 1000) % N == 0)
{
col++;
}
if (col == 4)
{
afficher (t);
}
}
}
}
}
return 0;
}

#ifdef TEST
static int test (void)
{
int tt[NB_CHIFFRES];
int i;

chiffres (tt, 2009);

for (i = 0; i < NB_CHIFFRES; i++)
{
printf ("%d", tt[i]);
}
printf ("n");

return 0;

}
#endif

int main (void)
{
#ifdef TEST
test ();
#endif

solve ();

return 0;
}

On 15 nov, 01:09, candide <cand...@free.invalid> wrote:

*) je trouve que la multiplicité des assert nuisent à la lisibilité
(normal je n'ai pas l'habitude de les utiliser)

Les assert() sont juste là pour vérifier qu'on ne fait pas d'âneries
(débordement de tableau, par exemple). Avec un peu d'entrainement, on
ne les voit plus et la lisibilité reste bonne...

Marc Espie a écrit :

Si tu connais un peu Tolkien, Aragorn est appele Grand Pas, ce qui est la
traduction a peu pres fidele de Strider dans la VO.

Ah, je ne regarderai plus jamais le seigneurs des anneaux comme avant ;)

-ed- a écrit :

On 15 nov, 01:09, candide <cand...@free.invalid> wrote:

Jean-Marc Bourguet a écrit :

#define BORNE 10*10*10

BORNE devrait etre 10000

Oui, mon intention était de remplacer 10000 par 10*10*10*10 pour voir si
ça ralentissait l'exécution.

Alors c'est

#define BORNE (10*10*10)

sinon le comportement dépend de l'utilisation.

Exact, petite négligence de ma part.

Mais c'est strictement équivallent à 1000, car une expression
constante est évaluée par le compilateur.

Non, on en a discuté dans un fil précédent, la norme ne garantit rien.

candide <candide@free.invalid> writes:

Jean-Marc Bourguet a écrit :

candide <candide@free.invalid> writes:

au moins deux problemes ici:
* %N doit se faire sur tout le calcul

Pas compris, de quel calcul tu parles ?

Dans

while (!(t[3][col] + t[2][col] * 10 + t[1][col] * 100 + t[0][col] * 1000 % N))

Le % N ne s'applique pas à la même chose que dans ta version corrigée:

while (col < 4
&& (t[3][col] + t[2][col] * 10 + t[1][col] * 100 +
t[0][col] * 1000) % N == 0)

Je suis certainement bouché mais je ne vois pas le problème : d'après le
tableau des priorités des opérateurs, il me semblaient bien que les
expressions étaient équivalentes : % est prioritaire sur [] et + et de
priorité égale avec * et l'associativité est de gauche à droite.

Dans la seconde expression, le % s'applique sur la somme, dans la première
sur son dernier terme.

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org

En news:491f4f99$0$14922$426a74cc@news.free.fr, candide va escriure:

-ed- a écrit :

#define BORNE (10*10*10)
Mais c'est strictement équivallent à 1000, car une expression
constante est évaluée par le compilateur.

Non, on en a discuté dans un fil précédent, la norme ne garantit rien.

On a pas dû lire le même fil, alors.

La norme ne garantit pas le _moment_ où se fait l'évaluation, et il y a
aussi quelques autres subtilités sur le préprocesseur (genre la valeur de
#BORNE), certes, donc /stricto sensu/ ce n'est pas « strictement
équivalent ».

Mais si on cesse de pinailler, oui, la norme garantit bien que la *valeur*
de BORNE sera 10000.
C'est même tout le principe des expressions constantes, en fait, la valeur
est garantie, peu importe comment le compilateur se débrouille pour
l'obtenir, c'est son problème.

(Et comme c'est inférieur à 32767-N, c'est strictement conforme).



Antoine

Antoine Leca a écrit :

En news:491f4f99$0$14922$426a74cc@news.free.fr, candide va escriure:

-ed- a écrit :

#define BORNE (10*10*10)
Mais c'est strictement équivallent à 1000, car une expression
constante est évaluée par le compilateur.

Non, on en a discuté dans un fil précédent, la norme ne garantit rien.

On a pas dû lire le même fil, alors.

Je te cite :


Antoine Leca a écrit :

En news:49172a5f$0$17384$426a74cc@news.free.fr, candide va escriure:

#include <stdio.h>
#define A 2
#define B 5
int main(void) {
int i;
for (i = 0; i < A * B; i++) printf("toton");
return 0; }

Ai-je une quelconque garantie que l'expression A*B ne sera pas
réévaluée à chaque tour de boucle pendant l'exécution ?

Garantie formelle, non.

Je cite un autre intervenant :

Erwan David a écrit :

Ai-je une quelconque garantie que l'expression A*B ne sera pas réévaluée
à chaque tour de boucle pendant l'exécution ?

Non. Cependant en pratique A*B sera évalué à la compilation.

Ça me semble clair.

La norme ne garantit pas le _moment_ où se fait l'évaluation, et il y a
aussi quelques autres subtilités sur le préprocesseur (genre la valeur de
#BORNE), certes, donc /stricto sensu/ ce n'est pas « strictement
équivalent ».

Mais si on cesse de pinailler, oui, la norme garantit bien que la *valeur*
de BORNE sera 10000.

Je ne dis pas le contraire. Le problème n'est pas la valeur. Le problème
est que je ne souhaite pas que cette valeur soit recalculée à chaque
tour de boucle (cf. la place de BORNE dans mon code, il figure dans des
expressions régissant des boucles for) et apparemment, la norme ne me
donne aucune garantie de cela même si selon toute vraisemblance, tout
compilateur digne de ce nom optimisera.

Pour une question de lisibilité, tu penses bien que je préfèrerais écrire

#define BASE 10
#define BORNE (BASE*BASE*BASE*BASE)



J'en profite pour jeter un coup d'oeil à ce que disent Kernighan & Pike
dans leur chapitre sur l'optimisation. Et quelle n'est pas alors ma
surprise de voir (page 179) qu'ils écrivent :


for (i=0; i< 3*n; i+=3)
{
/*
Déroulement classique de boucle
*/
}


J'avoue que le 3*n dans l'expression de contrôle de la boucle me laisse
plus que perplexe: on n'a aucune garantie que ce produit 3*n n'est pas
recalculé n fois, si ?

On 2008-11-18, candide <candide@free.invalid> wrote:

Je ne dis pas le contraire. Le problème n'est pas la valeur. Le problème
est que je ne souhaite pas que cette valeur soit recalculée à chaque
tour de boucle (cf. la place de BORNE dans mon code, il figure dans des
expressions régissant des boucles for) et apparemment, la norme ne me
donne aucune garantie de cela même si selon toute vraisemblance, tout
compilateur digne de ce nom optimisera.

Mais la norme ne te garantie pas non plus que le compilo ne fera pas
calculer au processeur les statistiques du dernier tierce entre
chaque intruction, ou qu'il utilisera bien l'instruction de multiplication
du processeur et ne calculera pas les multiplications par sommes successives.

Pour une question de lisibilité, tu penses bien que je préfèrerais écrire

#define BASE 10
#define BORNE (BASE*BASE*BASE*BASE)

Pourquoi ne le faits-tu pas ? A ton avis, quel est le risque majeur
de l'informatique des années 2000 ? Avoir un code non maintenable ou
avoir un code qui rame ?

J'avoue que le 3*n dans l'expression de contrôle de la boucle me laisse
plus que perplexe: on n'a aucune garantie que ce produit 3*n n'est pas
recalculé n fois, si ?

Le compilo pourrait même la calculer 3*(3*n) fois, c'est à dire la
calculer 3 fois chaque fois qu'il en a besoin, et vérifier que
les 3 valeurs sont les mêmes, et sinon, choisir par un vote.

Marc Boyer
--
En France, un habitant sur 1000 est en prison.
Aux USA, 7 habitants sur 1000 sont en prison.
Est-ce que les USA sont 7 fois plus sûrs ?

candide <candide@free.invalid> writes:

Je ne dis pas le contraire. Le problème n'est pas la valeur. Le problème
est que je ne souhaite pas que cette valeur soit recalculée à chaque
tour de boucle (cf. la place de BORNE dans mon code, il figure dans des
expressions régissant des boucles for) et apparemment, la norme ne me
donne aucune garantie de cela même si selon toute vraisemblance, tout
compilateur digne de ce nom optimisera.

La norme ne decrit qu'un comportement observable et le temps d'execution
n'en fait pas partie -- donc la norme ne demande rien la dessus.

Dans tous les contextes ou c'est observable, les expressions entieres
constantes doivent se comporter comme si elles etaient evaluees a la
compilation (en particulier, elles peuvent apparaitre comme taille de
tableaux en C90). En pratique, la mecanique pour faire ces calculs a la
compilation doivent donc etre la car ne pas les avoir *compliquerait*
l'implementation. Ne pas l'utiliser tout le temps, en dehors meme de toute
option d'optimisation, serait pour le moins etrange.

Si tu as un compilateur pour lequel c'est un probleme de performance, le
meilleur conseil est d'utiliser un autre compilateur -- celui que tu as est
tellement particulier qu'il doit avoir d'autres surprises pour toi.

A+

--
Jean-Marc
FAQ de fclc: http://www.levenez.com/lang/c/faq
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Marc Boyer a écrit :

Mais la norme ne te garantie pas non plus que le compilo ne fera pas
calculer au processeur les statistiques du dernier tierce entre
chaque intruction, ou qu'il utilisera bien l'instruction de multiplication
du processeur et ne calculera pas les multiplications par sommes successives.

Oui, c'est l'argument qu'a déjà donné Antoine mais qui n'est pas probant
dans la mesure où je n'ai aucun contrôle sur ce type de comportement
fantasque du compilateur. Par contre, en utilisant BORNE dans de
nombreuses boucles imbriquées

#define BORNE (BASE*BASE*BASE*BASE)

je prends le risque de faire faire au processeur de nombreux calculs
inutiles pendant l'exécution.

Pourquoi ne le faits-tu pas ? A ton avis, quel est le risque majeur
de l'informatique des années 2000 ? Avoir un code non maintenable ou
avoir un code qui rame ?

Je ne vois pas le rapport avec notre problème. Tu veux dire que sous
prétexte que les processeurs sont rapides aujourd'hui, on peut se
permettre de faire l'impasse sur certaines optimisations basiques ? Je
ne suis pas compétent pour répondre ayant une vue très étroite de
l'informatique des années 2000 mais j qu'on a besoin dans certaines
circonstances de code qui soit bien optimisé. Par ailleurs, je ne vois
pas pourquoi tu opposes rapidité et maintenabilité.

Le compilo pourrait même la calculer 3*(3*n) fois, c'est à dire la
calculer 3 fois chaque fois qu'il en a besoin, et vérifier que
les 3 valeurs sont les mêmes, et sinon, choisir par un vote.

Mais bien sûr. Et tu vas peut-être me dire qu'il est vain de sortir par
temps de pluie avec un parapluie rouge car Eole pourrait décider de
faire subir un effet de lévitation mortelle aux porteurs de tels parapluies.

Bon, tu m'as déjà avancé cet argument et comme je t'ai déjà dit : le
programmeur qui ne connaît pas les entrailles du compilateur-cible n'a
aucun moyen d'être informé sur ce genre de comportement.

Ce que tu racontes là est assez invraisemblable. Par contre, que le
processeur soit amené à calculer n fois le produit et cela de façon
totalement inutile me le paraît moins.