Discussion :

[jylac]

Bonjour,

Je me prends la tête depuis quelques jours pour ce problème simple. Y a t'il un algo pour cela :

Pour stocker en un seul chiffres différente catégorie, je cherche à trouver l'algo. de décodage inverse ???

Si on a une catégorie "1" qui correspond à (par ex) "pizzeria",
2 à "gastronomique",
4 à "kebab",
8 à "brasserie",
16 à "hamburger"
etc .... (donc une multi par 2 à chaque fois)

On peut coder que le restaurant qui fait des "kebab" + "hamburger" + "pizza", rentre donc dans la catégorie 21 - 4 + 16 + 1 = 21
Alors comment décomposer ce chiffre pour retrouver les différentes catégories ????

26 == 16 + 8 + 2
11 == 8 + 2 + 1
19 == 16 + 2 + 1
...

Merci d'avance

[droggo]

Luo,

Comme chaque valeur est une puissance de 2, elle est tout simplement représentée par un bit on/off dans l'entier (?) ou tu stockes le total.

S'il y a plus de valeurs que de bits disponibles pour les variables que tu peux gérer, il faudra voir pour plutôt faire un ensemble pouvant contenir les différentes valeurs (qui, à ce moment là, ne devront plus être des puissances de 2, mais une simple suite de 1 à n).

[Jedai]

Dans ce cas on utilise des opérations bit à bit, par exemple en C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
if( resto & 1 ) {
  // pizzeria
}

Généralement, on définit quelques variables :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
#define PIZZA 1
#define GASTRONOMIQUE 2
#define MER 4
// ...

ça rend plus facile la lecture du code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
if( resto & PIZZA ) {
  // pizzeria
}
if( resto & GASTRONOMIQUE ) {
  // gastronomique
}

--
Jedaï

[pseudocode]

pour reprendre la question originale, pour décomposer un nombre N en puissance de 2:

1. chercher la plus grande puissance de 2 inferieure ou egale a N. (appelons la p)
2. Retirer p a N
3. retour etape 1, tant que N n'est pas nul.

exemple: N=21

1. La plus grande puissance de 2 inferieure ou egale a 23 est: p=16
2. N = N-p = 21-16 = 5
3. La plus grande puissance de 2 inferieure ou egale a 5 est: p=4
4. N = N-p = 5-4 = 1
5. La plus grande puissance de 2 inferieure ou egale a 1 est: p=1
6. N = N-p = 1-1 = 0 ... fini

La decomposition est donc 16 + 4 +1

[Nemerle]

Pour savoir si dans X le bit correspondant à 1, 2, 4,... est à 1, tu boucles sur un décalage à droite:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
i=1
tant que X!=0
   si(X!=2*(X>>1)) alors "i est dans X"
   X>>1
   i=i*2
fin tant que

[pseudocode]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
i=1
tant que X!=0
   si (X & 1) alors "i est dans X" 
   X>>1
   i=i*2
fin tant que

C'est plus propre. enfin, moi ce que j'en dis...

[Nemerle]

su^rement... tu sais moi l'informatique... à part la MOA...