Algo Conversion Décimal -> Binaire

Version imprimable

Bonjour à tous,

Super ce Forum. :D

Voilà, je débute en algo et je bloque sur l'algo de converion décimale -> binaire.

Code:

1
2
3
4
5
6
 
Fonction ConvB(nb:entier):entier
 
  // pour avoir du binaire il faut diviser par 2 autant de fois jusqu'à ce que ça soit plus divisible par 2.
 // le reste de la division (modulo) est lu dans le sens du bas vers le haut. elle sera forcement stocké dans un tableau.
 // mais je n'arrive pas à faire l'algo. Merci de votre aide

23/02/2006, 12h54
benratti

Generalement, quand tu fais une conversion, tu passes d'un format a un autre, d'un type a un autre, d'une representation a une auter. Ce qui me derange, c'est que dans la signature de la fonction que tu essaie de faire, c'est que tu veux convertir un entier en entier.

tu as besoin d'utiliser une notation particuliere pour pouvoir noter les notés les entiers binaires et les entiers decimaux.

A part ca ton algo est bon, je ne vois pas ou tu coinces. Expliques nous ce qui te poses exactement probleme ?
23/02/2006, 14h02
TabrisLeFol

Une representation est seulement une representation. (et oui :lol: )
Ta fonction serait plutot du type int vers String ou tableau/chaine de caractères. Pour l'info, à moins que cela soit un exercice, les données étant codées en binaire, les librairies proposent generalement l'utilisation binaire des nombres...
23/02/2006, 15h32
MisterTee

:D
oui
en entrée : entier
en sortie : binaire.

donc

Foinction Binaire (Nb : entier ) : // il renvoie quoi une chaîne de caractère ???

// code
bin <- résultat du code
retourne bin

voilà où je bloque => je veux le pseudo code. je ne sais pas lui dire divise par 2 jusqu'à ce que ça ne soit plus divisible par 2 et
mettre dans le tableau les valeurs du modulo mais dans le sens inverses

Merci de votre aide

Bonjour,

Pour convertir un nombre décimal en un nombre binaire, on cherche d'abord la puissance de 2 immédiatement inférieure au nombre décimal, ensuite on la soustrait à ce nombre. Ensuite on fait de même avec le résultat de la soustraction et ainsi de suite jusqu'à atteindre 0.

exemple avec 403 en décimal :
Code:

1 2 3 4 5 6 7 8 9 10 403 - 256 = 147 (avec 256 = 2^8) 147 - 128 = 19 (128 = 2^7) 19 - 16 = 3 (16 = 2^4) 3 - 2 = 1 (2 = 2^1) 1 - 1 = 0 (1 = 2^0)
Pour exprimer le nombre binaire, on "met un 1" pour chaque puissance de 2 utilisée (dans le cas contraire, un 0).
Code:

1 2 3 4 Valeure: 256 128 64 32 16 8 4 2 1 Puissance de 2: 2^8 2^7 2^6 2^5 2^4 2^3 2^2 2^1 2^0 Nombre binaire: 1 1 0 0 1 0 0 1 1

23/02/2006, 15h53
Hephaistos007

Citation:

Envoyé par MisterTee

je ne sais pas lui dire divise par 2 jusqu'à ce que ça ne soit plus divisible par 2 et mettre dans le tableau les valeurs du modulo mais dans le sens inverses

Tu remarques toi même que le resultat de ta première division est en fait le dernière à être affiché. C'est en sens inverse comme tu dis. Pour faire cela, tu peux utiliser la récursivité.
Regarde ici : http://membres.lycos.fr/olg2004/?go=_public/_php/list.php&section=5

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
fonction dec2bin(nb)           
 { 
     Si (nb>=2)                             
       Alors
         retourne nb mod 2 
         Sinon 
           dec2bin((nb/2)-1)  
      Finsi                      
}             
 
// heu pas tout compris là.....

ok, je vois pas trop comment ça marche ... à l'aide :oops:

23/02/2006, 16h16
MisterTee

Neitsa, le principe je l'ai compris mais c'est de le traduire en pseudo code. la recursivité m'a l'air d'être la solution mais j'arrive pas à mouliner cela dans ma tête. quelqu'un peut me l'expliquer de façon claire? svp :)

Voici un extrait des commentaires d'un de mes sources (en assembleur 8086, ça date d'il y a longtemps), qui explique la chose. Si ça peut servir...

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
;   Voici un algorithme de conversion d'une base vers une base plus
; petite (par exemple de 65536 vers 10000).
;
;   Expliquons l'algorithme en faisant une conversion de la base 10 vers
; la base 3 (d = 3). Convertissons le nombre 837.
;
;        0  0  0  0  0  0  8. 3  7 |        +
;        0  0  0  0  0  2  2  3. 7 |        +
;        0  0  0  0  0  2  7  2  7.|        +
;        0  0  0  0  0  2  7  9  0 | .      -
;        0  0  0  0  0  2. 7  9 |0          +
;        0  0  0  0  0  2  7. 9 |0          +
;        0  0  0  0  0  9  0  9.|0          +
;        0  0  0  0  0  9  3  0 |0.         -
;        0  0  0  0  0  9. 3 |0  0          +
;        0  0  0  0  3  0  3.|0  0          +
;        0  0  0  0  3  1  0 |0. 0          -
;        0  0  0  0  3. 1 |0  0  0          +
;        0  0  0  1  0  1.|0  0  0          +
;        0  0  0  1  0  1 |0. 0  0          -
;        0  0  0  1. 0 |1  0  0  0          +
;        0  0  0  1  0.|1  0  0  0          +
;        0  0  0  3  1 |1. 0  0  0          -
;        0  0  0  3.|1  1  0  0  0          +
;        0  0  1  0 |1. 1  0  0  0          -
;        0  0  1.|0  1  1  0  0  0          +
;        0  0  1 |0. 1  1  0  0  0          -
;        0  0 |1. 0  1  1  0  0  0          -
;
;  Le résultat est 1011000 (c'est un pur hasard, s'il ne contient pas de 2).
;
;  Explications: chaque opération porte sur un groupe de deux chiffres. Ces
; deux chiffres sont suivis par le point dans la simulation ci-dessus. Par
; ailleurs, tout ce qui est a droite de la barre verticale est définitif.
;
;   Il y a un nombre suffisant de 0 a gauche du nombre.
;
;   On commence avec la barre verticale a droite du dernier chiffre
; et le point a droite du chiffre le plus signifiant (première ligne).
:
;   Si la barre est a droite du point (ligne marquées d'un +):
;     - on remplace les deux chiffres a gauche du point par le quotient et
;          le reste dans la division par d.
;     - on déplace le point d'un position vers la droite.
;
;   Si la barre est a gauche du point (lignes marquées d'un -):
;     - on déplace la barre d'une position vers la gauche,
;     - on replace le point a la droite du chiffre le plus signifiant.
;
;   On a fini quand on est amené a faire deux fois de suite l'opération -, ou
; ce qui revient au meme, quand on n'a plus que des 0 a gauche de la barre.
;
;   Remarque: dans les opérations de division de 2 chiffres par d, le chiffre
; de gauche est toujours strictement plus petit que d, car il est soit 0,
; soit le reste de l'opération précédente. Il en résulte que le quotient se
; compose toujours d'un seul chiffre. Or cette caractéristique correspond
; exactement (ce n'est pas par hasard) au mode de fonctionnement du 8086, qui
; refuse de diviser 32 bits par 16 bits si le quotient doit etre de plus de 16
; bits.

23/02/2006, 16h56
MisterTee

:oops: :oops:
désolé, j'ai pas bien compris ton tuto. :cry:
23/02/2006, 18h17
DrTopos
Tu as un nombre n que tu veux écrire en base d. Tu fais une division euclidienne:
Code:

1 2 n = qd + r
avec 0 <= r < d. r est alors le dernier chiffre du résultat cherché, et il suffit de recommencer avec q.

L'algorithme ci-dessus ne fait rien d'autre. Chaque division est faite comme à l'école primaire (en partant du chiifre de gauche du nombre à diviser). Le reste joue le rôle de la retenue. On a donc fait une division complète quand le point traverse la barre.

Par exemple, la première division est effectuée dans les 4 première lignes de la simulation. On a bien 837 = 279x3 + 0.

Cet algorithme est très performant car il est exactement adapté au fonctionnement de l'instruction div des processeurs Intel (et sans doute des autres processeurs aussi bien).

un code du type

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
function DEC_2_bin( i : integer) : string;
var s : string;
   begin
   if i < 0 then s:='?'
   else if i=0 then s:='0'
   else
      begin
      s:='';
      while i <> 0 do
         begin 
         if (i and 1) = 1 then 
            s:='1' + s 
         else 
            s:='0' + s;
         i := i shr 1; // => div 2;
         end;
      end;
    DEC_2_bin:=s
   end;

devrait répondre au problème

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
 
en pseudo ça donne
fonction DEC_2_bin( i :entier) : caractère
s : caractère
 Début
   Si i < 0 Alors
        s<-'?' 
   SinonSi i=0 Alors 
       s<-'0' 
      Sinon 
        s<-'' 
      TanQue i <> 0 Faire
        Si (i ET 1) = 1 Alors 
            s <- s + '1' 
         Sinon
            s<- s + '0'
         i <- i shr 1; // => div 2; 
         FinSi
      FinTanQue
    DEC_2_bin<- s 
   FinSi
Fin
 
// marche pas... :cry:  :cry:  :cry: