Algorithme logique Solution

Version imprimable

15/01/2012, 17h45
Adel13

Algorithme logique Solution

Salut à tous ! Je rencontre un petit problème j'espère pouvoir avoir de l'aide :(

Donc voila soit n, la taille d'une grille d'un sudoku. Donc pour une grille à 5 lignes et 5 colonnes,
n=5 .

Soit également : i,j,k , la triplette qui donne la valeur d'une cause .
Par exemple : 2,1,4 signifie qu'à la ligne 2, 1ère colonne, on a la valeur 4.

Le problème :
Mon objectif est de transformer la suite de triplette en variable unique, allant de 1 à n².

Autrement dit ( toujours pour n = 5) :
1,1,1 => 1
1,1,2 => 2
...
1,2,5 => 5
1,2,1 => 6

Afin d'établir cette relation, j'utilise la fonction suivante :
n²(i-1) + n(j-1) + k

Aucun soucis jusque là.
Le problème que je rencontre est de faire l'inverse, ce qui est apparemment impossible avec une fonction mathématique. Il me faudrait un algo.
L'objectif est donc par exemple :
On me donne l'entier "6", je dois retrouver = > 1,2,1.

C'est casse tête je sais :p , mais si quelqu'un a envie de se casser la tête bin ... merci d'avance !
Car je suis bloqué depuis plus de 2 jours pour trouver une solution ..
15/01/2012, 18h06
Franck Dernoncourt

http://fr.wikipedia.org/wiki/%C3%89q..._ax%2Bby_%3D_c ?

EDIT : désolé, j'avais lu trop rapidement, mon lien est mauvais car k est également une inconnue. Donc plus généralement, ton équation est de type diophantienne du premier degré (mais pas forcément une identité de Bézout, ce qui ne serait le cas que si k est une constante, i.e. ssi tu n'avais que 2 inconnues)
15/01/2012, 18h21
Franck Dernoncourt

Au passage je suppose que tu voulais dire 1,1,5 => 5 ?

Au-delà du caractère général de mon message précédent, ton problème a des contraintes spécifiques qui font que l'équation me semble facile à résoudre à coup de division et modulo.

E.g. pour 6 quelque chose du genre :
k = 6 (mod n) = 1 (si n = 5)
i = ceiling(6 / n) (mod n) = 2 (si n = 5)
j = ceiling(6 / n²) (mod n) = 1 (si n = 5)

Lai,

Oui, je suis arrivé au même genre de résultat :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
uint32_t getIt(uint32_t n, uint32_t i,uint32_t j,uint32_t k)
{
    // n²(i-1) + n(j-1) + k
    uint32_t res = n*n*(i-1) + n*(j-1) + k;
    return res;
}
int main()
{
    const uint32_t n = 5;
    uint32_t i,j,k,r,modK,rModK,modJ,rModJ,modI;
 
    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=n; ++j)
        {
            for (k=1; k<=n; ++k)
            {
                r = getIt(n,i,j,k);
                modK = (r-1) % n; // = k-1 !!!
                rModK = r - (modK+1);
 
                modJ = (rModK / n) % n; // = j-1 !!!
                rModJ = (rModK / n)- modJ;
 
                modI = rModJ / n; // = i-1  !!!
 
                printf("%1u%1u%1u => %3u, modK = %1u, rModK = %3u, modJ = %3u, rModJ = %1u, modI = %1u\n",i,j,k,r,modK,rModK,modJ,rModJ,modI);
            }
        }
    }
 
    return 0;
}

et en sortie (pas complète, pour éviter trop de lignes)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
111 =>   1, modK = 0, rModK =   0, modJ =   0, rModJ = 0, modI = 0
112 =>   2, modK = 1, rModK =   0, modJ =   0, rModJ = 0, modI = 0
113 =>   3, modK = 2, rModK =   0, modJ =   0, rModJ = 0, modI = 0
114 =>   4, modK = 3, rModK =   0, modJ =   0, rModJ = 0, modI = 0
115 =>   5, modK = 4, rModK =   0, modJ =   0, rModJ = 0, modI = 0
121 =>   6, modK = 0, rModK =   5, modJ =   1, rModJ = 0, modI = 0
122 =>   7, modK = 1, rModK =   5, modJ =   1, rModJ = 0, modI = 0
123 =>   8, modK = 2, rModK =   5, modJ =   1, rModJ = 0, modI = 0
124 =>   9, modK = 3, rModK =   5, modJ =   1, rModJ = 0, modI = 0
125 =>  10, modK = 4, rModK =   5, modJ =   1, rModJ = 0, modI = 0
131 =>  11, modK = 0, rModK =  10, modJ =   2, rModJ = 0, modI = 0
132 =>  12, modK = 1, rModK =  10, modJ =   2, rModJ = 0, modI = 0
133 =>  13, modK = 2, rModK =  10, modJ =   2, rModJ = 0, modI = 0
134 =>  14, modK = 3, rModK =  10, modJ =   2, rModJ = 0, modI = 0
135 =>  15, modK = 4, rModK =  10, modJ =   2, rModJ = 0, modI = 0
141 =>  16, modK = 0, rModK =  15, modJ =   3, rModJ = 0, modI = 0
142 =>  17, modK = 1, rModK =  15, modJ =   3, rModJ = 0, modI = 0
143 =>  18, modK = 2, rModK =  15, modJ =   3, rModJ = 0, modI = 0
144 =>  19, modK = 3, rModK =  15, modJ =   3, rModJ = 0, modI = 0
145 =>  20, modK = 4, rModK =  15, modJ =   3, rModJ = 0, modI = 0
151 =>  21, modK = 0, rModK =  20, modJ =   4, rModJ = 0, modI = 0
...
532 => 112, modK = 1, rModK = 110, modJ =   2, rModJ = 20, modI = 4
533 => 113, modK = 2, rModK = 110, modJ =   2, rModJ = 20, modI = 4
534 => 114, modK = 3, rModK = 110, modJ =   2, rModJ = 20, modI = 4
535 => 115, modK = 4, rModK = 110, modJ =   2, rModJ = 20, modI = 4
541 => 116, modK = 0, rModK = 115, modJ =   3, rModJ = 20, modI = 4
542 => 117, modK = 1, rModK = 115, modJ =   3, rModJ = 20, modI = 4
543 => 118, modK = 2, rModK = 115, modJ =   3, rModJ = 20, modI = 4
544 => 119, modK = 3, rModK = 115, modJ =   3, rModJ = 20, modI = 4
545 => 120, modK = 4, rModK = 115, modJ =   3, rModJ = 20, modI = 4
551 => 121, modK = 0, rModK = 120, modJ =   4, rModJ = 20, modI = 4
552 => 122, modK = 1, rModK = 120, modJ =   4, rModJ = 20, modI = 4
553 => 123, modK = 2, rModK = 120, modJ =   4, rModJ = 20, modI = 4
554 => 124, modK = 3, rModK = 120, modJ =   4, rModJ = 20, modI = 4
555 => 125, modK = 4, rModK = 120, modJ =   4, rModJ = 20, modI = 4

15/01/2012, 21h11
Adel13

Franck Dernoncourt, j'ai l'impression que cela ne marche pas.
Par exemple pour 37

Pour n = 5
On a k = 37 % 5 = 1 ( ok )
on a i = (37/5)% 5 = 2 ( ok )
Mais on a :
j = (37/5²) % 5 = 1 alors qu'il devrait être égale à 3 :/
15/01/2012, 21h20
Franck Dernoncourt

Ah peut-être, je n'ai lu que très rapidement ton message et n'ai pas regardé les détails, je voulais simplement te donner une idée d'algorithme pour trouver les variables i,j et k. Je te laisse faire la fin :)
15/01/2012, 21h21
Adel13

Bin sincérement j'y travail depuis 2 jours j'y arrive pas ..
Pour le i et le k apparemment c'est bon mais le j .. :(
15/01/2012, 21h26
droggo

Xia,

Citation:

Envoyé par Adel13

Bin sincérement j'y travail depuis 2 jours j'y arrive pas ..
Pour le i et le k apparemment c'est bon mais le j .. :(

Il se pourrait que lire mon message précédent t'aide !
15/01/2012, 21h28
Adel13

Oui dsl merci de ta réponse, j'ai vraiment eu du mal à la comprendre pourrais-tu me l'expliquer un peu ?
Quel sont toutes ces variables ?
Vraiment désolé ..
16/01/2012, 10h12
droggo

Vie,

J'ose espérer que tu plaisantes !!

n,i,j,k sont les mêmes que les tiens, les autres sont des calculs intermédiaires et/ou définitifs, et dans le code, il y a de petits commentaires pour dire leur finalité (enfin, les 3 qui comptent, celles qui contiennent ce que tu cherches).

Regarde la liste de sortie pour t'en convaincre.
16/01/2012, 11h00
souviron34

Citation:

Envoyé par droggo

J'ose espérer que tu plaisantes !!

Optimiste !! :D:aie: