En C: structures et tableaux
Utilisateur anonyme
-
kilian Messages postés 8854 Statut Modérateur -
kilian Messages postés 8854 Statut Modérateur -
Salut à tous !
Voila j'ai un ptit problème......
Je dois coder un programme qui résout les sudoku; pour ça, il me faut spécifier les ensembles d'entiers, que j'utiliserai en fait pour stocker les valeurs possibles pour une case du sudoku.
J'ai donc pensé à ça:
typedef struct{
int tab[9];
} Ens;
Mais j'ai un gros doute: pour accéder aux éléments du tableau d'un truc de type Ens, comment faire ?
Et mettons que je fasse:
Ens t;
Comment initialiser et modifier une valeur du tableau ?
Faut-il faire:
t[1]=3;
ou
t.tab[1]=3;
De même, pour tout initialiser, doit-on faire :
t[]={1,2,3,4,5,6,7,8,9};
ou
t.tab[]={1,2,3,4,5,6,7,8,9};
Allez-y profitez-en pour vous moquer de moi, je crois que je suis vraiment à la masse ce soir......
En tout cas merci d'avance pour les âmes charitables qui voudropnt bien me répondre ^^
Et si vous trouvez que ma méthode pour faire des ensembles d'entiers est (très ?) discutable, ne vous genez pas ;-)
Voila j'ai un ptit problème......
Je dois coder un programme qui résout les sudoku; pour ça, il me faut spécifier les ensembles d'entiers, que j'utiliserai en fait pour stocker les valeurs possibles pour une case du sudoku.
J'ai donc pensé à ça:
typedef struct{
int tab[9];
} Ens;
Mais j'ai un gros doute: pour accéder aux éléments du tableau d'un truc de type Ens, comment faire ?
Et mettons que je fasse:
Ens t;
Comment initialiser et modifier une valeur du tableau ?
Faut-il faire:
t[1]=3;
ou
t.tab[1]=3;
De même, pour tout initialiser, doit-on faire :
t[]={1,2,3,4,5,6,7,8,9};
ou
t.tab[]={1,2,3,4,5,6,7,8,9};
Allez-y profitez-en pour vous moquer de moi, je crois que je suis vraiment à la masse ce soir......
En tout cas merci d'avance pour les âmes charitables qui voudropnt bien me répondre ^^
Et si vous trouvez que ma méthode pour faire des ensembles d'entiers est (très ?) discutable, ne vous genez pas ;-)
2 réponses
Salut,
Oui c'est bien t.tab[] ;-)
Tu as plusieurs solutions.
Il y a la tienne, mais dans ce cas quand tu supprimeras les différentes solutions possibles tu vas faire comment?
Par exemple pour une case donnée tu as toutes les solutions possibles:
{1, 2, 3, 4, 5, 6, 7, 8, 9}
La seule solution, ça va être de mettre 0 quand tu voudras supprimer une possibilité.
Par exemple le 5 n'est pas possible:
{1, 2, 3, 4, 0, 6, 7, 8, 9}
Voilà. Ca fonctionne comme ça.
Maintenant faisons une boucle pour trouver la première valeur possible:
Ok, ça fonctionne, mais tu remarqueras que ça ne sert à rien de stocker ainsi chaque nombre, quand le nombre est disponible, t.tab[i] = i + 1
Donc un truc un peu mieux serait de faire mettre 1 quand i + 1 est dispo, sinon on met 0.
Par exemple, tous disponibles sauf le 5:
{1, 1, 1, 1, 0, 1, 1, 1, 1}
Ceci dit pour chaque case tu est en train de consommer un tableau de 9 entiers. Un entier = 4 octets.
Tu as 9 * 9 cases, ce qui donne 4 octets * 9 * 81 = 2916 octets.
En plus parcourir un tableau c'est lent, ça demande pas mal d'accès mémoire.
Pourquoi ne pas utiliser un entier pour chaque case et tester ses 9 premiers bits?
Quand le bit n est à 1, alors le nombre n + 1 est dipo (je prends + 1 car on part de zero).
Prenons une case où tous les nombres sont disponibles, tu peux l'initialiser en mettant les 9 premiers bits à 1, ce qui
fait 2^0 + 2^1 + 2^... + 2^8 = 511
Si tu veux savoir si le nombre 5 est disponible, tu fais un "et" binaire (&) sur le bit numéro 4 (on part de 0).
Ca donne ça:
Si tu veux supprimer le 5 comme possibilité:
Si tu veux ajouter le 5 comme possibilité:
Bon si tu n'as jamais vu tous ces trucs binaires, autant en rester au tableau. Mais comme ça tu sauras pour plus tard, avec cette solution deux avantages:
_ Juste un entier par case: 81 * 4 = 324 octets
_ C'est très rapide, tu ne parcoures pas de tableau (ou juste un pour tous les entiers), et tu fais des calculs binaires dessus. C'est un algo beaucoup plus rapide.
Oui c'est bien t.tab[] ;-)
Tu as plusieurs solutions.
Il y a la tienne, mais dans ce cas quand tu supprimeras les différentes solutions possibles tu vas faire comment?
Par exemple pour une case donnée tu as toutes les solutions possibles:
{1, 2, 3, 4, 5, 6, 7, 8, 9}
La seule solution, ça va être de mettre 0 quand tu voudras supprimer une possibilité.
Par exemple le 5 n'est pas possible:
{1, 2, 3, 4, 0, 6, 7, 8, 9}
Voilà. Ca fonctionne comme ça.
Maintenant faisons une boucle pour trouver la première valeur possible:
for (i = 0; i < 9; i++) {
if (t.ab[i] !=0) {
possible = t.tab[i]
break;
}
}
Ok, ça fonctionne, mais tu remarqueras que ça ne sert à rien de stocker ainsi chaque nombre, quand le nombre est disponible, t.tab[i] = i + 1
Donc un truc un peu mieux serait de faire mettre 1 quand i + 1 est dispo, sinon on met 0.
Par exemple, tous disponibles sauf le 5:
{1, 1, 1, 1, 0, 1, 1, 1, 1}
Ceci dit pour chaque case tu est en train de consommer un tableau de 9 entiers. Un entier = 4 octets.
Tu as 9 * 9 cases, ce qui donne 4 octets * 9 * 81 = 2916 octets.
En plus parcourir un tableau c'est lent, ça demande pas mal d'accès mémoire.
Pourquoi ne pas utiliser un entier pour chaque case et tester ses 9 premiers bits?
Quand le bit n est à 1, alors le nombre n + 1 est dipo (je prends + 1 car on part de zero).
Prenons une case où tous les nombres sont disponibles, tu peux l'initialiser en mettant les 9 premiers bits à 1, ce qui
fait 2^0 + 2^1 + 2^... + 2^8 = 511
int possibles = 511; // ou 0x1ff
Si tu veux savoir si le nombre 5 est disponible, tu fais un "et" binaire (&) sur le bit numéro 4 (on part de 0).
Ca donne ça:
if (possibles & (1 << 4)) {
// 5 est dispo
}
Si tu veux supprimer le 5 comme possibilité:
possibles &= ~(1 << 4)
Si tu veux ajouter le 5 comme possibilité:
possibles |= (1 << 4)
Bon si tu n'as jamais vu tous ces trucs binaires, autant en rester au tableau. Mais comme ça tu sauras pour plus tard, avec cette solution deux avantages:
_ Juste un entier par case: 81 * 4 = 324 octets
_ C'est très rapide, tu ne parcoures pas de tableau (ou juste un pour tous les entiers), et tu fais des calculs binaires dessus. C'est un algo beaucoup plus rapide.
Ouaaaaaaa je n'en attendais pas autant ^^
merci beaucoup lol
Pour le fait de mettre 0 lorsque la valeur n'est pas possible, j'y avait pensé (quand même ;-)
Par contre, mettre 1 quand i+1 est dispo et 0 sinon, j'y avait pas pensé, c'est pas con du tout ;-p
Hmmm va falloir que j'y refléchisse, t'inquiète mon programme final sera libre de droits pour toi ^^
Bon par contre utiliser des bits, très peu pour moi (n'y voyez pas d'allusions hein), je sais pas encore faire ce genre de choses, on n'a pas encore vu ça en cours donc...
Mais merci beaucoup pour ton aide, je m'attendais pas à ce que tu m'explique aussi bien, maintenant j'ai tout compris ^^
A la prochaine en tout cas ^^ (je vais encore surement avoir d'autres gros doutes existentiels comme celui-la ;-)
merci beaucoup lol
Pour le fait de mettre 0 lorsque la valeur n'est pas possible, j'y avait pensé (quand même ;-)
Par contre, mettre 1 quand i+1 est dispo et 0 sinon, j'y avait pas pensé, c'est pas con du tout ;-p
Hmmm va falloir que j'y refléchisse, t'inquiète mon programme final sera libre de droits pour toi ^^
Bon par contre utiliser des bits, très peu pour moi (n'y voyez pas d'allusions hein), je sais pas encore faire ce genre de choses, on n'a pas encore vu ça en cours donc...
Mais merci beaucoup pour ton aide, je m'attendais pas à ce que tu m'explique aussi bien, maintenant j'ai tout compris ^^
A la prochaine en tout cas ^^ (je vais encore surement avoir d'autres gros doutes existentiels comme celui-la ;-)
