============= Conversione da decimale a binario =============

Il problema che dobbiamo risolvere è il seguente: battuti sulla tastiera un numero decimale che leggiamo in una variabile dec vogliamo sia visualizzata sul video una sequenza di 0 o 1 che rappresenta la sua conversione in binario di dec, ad esempio (57)₁₀ = (111001) ₂ .

La prima fase di un, seppur piccolo, progetto consiste nel precisare l’interazione con l’utente, cioè che cosa si chiede in ingresso e cosa si da in uscita col programma che ci accingiamo a scrivere, nel caso dato per esempio decidiamo che 0 < dec < 2¹¹-1 e quindi la sua conversione binaria ha al piú 11 cifre binarie significative, che per comoditá di controllo vogliamo tutte e 11 scritte in uscita. Per facilitare l’uso del programma decidiamo magari di far comparire messaggi che descrivano all’utente cosa deve inserire a tastiera o cosa sta per apparire sul video. Uso la convenzione per cui i dati in uscita sono una sequenza di U_j, in questo caso la sequenza: <U₀,U₁, .....,U₁₀> e riscrivo il risultato che voglio ottenere:

dec = U₀2 ¹⁰ +U₁2 ⁹ + .....+ U₁₀2⁰

var dec, a. i : integer;

begin readln(dec);

..............................

writeln(‘conversione in binario del decimale: ‘, dec);

for i:= 10 downto 0 do write(c[i]);

{AF dec = S ¹⁰ _j=0 U[j] _*2^10-j }

end.

Decidiamo a questo punto che le cifre della conversione in binario saranno tenute in memoria in un vettore c di 11 componenti dove le cifre della conversione possono essere inserite via via che vengono generate, quindi in memoria per c in questo caso avremmo c= [1,0,0,1,1,1,0,0,0,0,0] quindi c[0]= 1, c[1]=0, e cosí via

dec = c[10]_*2 ¹⁰+ c[9]_*2⁹+..+ c[2]_*2²+c[1]_*2¹+c[0]_*2⁰

Pur non avendo ancora pensato a quale algoritmo adottare per risolvere il problema abbiamo giá definite le forme di interazione con chi userá il nostro lavoro e deciso, almeno in parte, la struttura della memoria che useremo. Possiamo formalizzare le decisioni prese come segue:

var c : array[0..10] of integer;

var dec, a. i : integer;

begin readln(dec);

..............................

{dec = S ¹⁰ _j=0 c[10-j] _* 2 ^j }

writeln(‘conversione in binario del decimale: ‘, dec);

for i:= 0 to 10 do write(c[i]);

{AF dec = S ¹⁰ _j=0 U[10-j] _*2^j }

end.

L’asserzione {dec = S ¹⁰ _j=0 c[10-j] _* 2 ^j } afferma che nel vettore c le cifre del numero in binario compaiono nello stesso ordine di quelle in uscita; è la scelta che facciamo per il seguito.

var c : array[0..10] of integer;

var dec, a, i : integer;

begin readln(dec);

..............................

{dec = S ¹⁰ _j=0 c[j] _* 2 ^j }

writeln(‘conversione in binario del decimale: ‘, dec);

for i:= 10 downto 0 do write(c[i]);

{AF dec = S ¹⁰ _j=0 U[j] _*2^10-j }

end.

Le asserzioni {dec = S ¹⁰ _j=0 c[j] _* 2 ^j } e {AF dec = S ¹⁰ _j=0 U[j] _*2^10-j } tengono conto che nel vettore c le cifre del numero in binario compaiono capovolte rispetto a quelle in uscita cioèè indice=potenza di 2.

Quanto all’algoritmo di conversione decidiamo di usare la generazione delle cifre della conversione a partire da quelle meno significative per mezzo di divisioni intere successive, vedere il materiale di Architetture1, e che è illustrato nell’esempio che segue dove convertiamo 57:

passo 1) 57 mod 2 = 1 57 div 2 = 28

passo 2) 28 mod 2 = 0 28 div 2 = 14

passo 3) 14 mod 2 = 0 14 div 2 = 7

passo 4) 7 mod 2 = 1 7 div 2 = 3

passo 5) 3 mod 2 = 1 3 div 2 = 1

passo 6) 1 mod 2 = 1 0 div 2 = 0 (57)₁₀ = (111001)₂

Una specifica formale in Pascal dell’algoritmo è riportata qui di seguito; in essa abbiamo scelto di memorizzare nel vettore c le cifre indice=potenza di 2.

var c : array[0..10] of integer;

var dec, a, i : integer;

begin

for i:= 0 to 10 do c[i]:=0;

readln(dec);

a:= dec;

i:=10;

while (a > 0) and (i >0) do

begin

c[i]:= a mod 2;

a:= a div 2;

{dec = a_*2 ⁱ⁺¹ + S ⁱ _j=0 c[j] _* 2 ^j }

i := i+1

end;

{dec = S ¹⁰ _j=0 c[10-j] _*2 ^j }

writeln(‘conversione in binario del decimale: ‘, dec);

for i:= 10 downto 0 do write(c[i]);

{AF dec = S ¹⁰ _j=0 U[j] _*2^10-j }

end.

In questo programma l’asserzione invariante di ciclo ha funzione di garanzia che dec rimane sempre uguale ad (a_*2 ⁱ⁺¹ + S ⁱ _j=0 c[j] _* 2 ^j) non importa se chi legge, manutentore o altro, non capisca quali trasformazioni il progettista dell’algoritmo abbia richieste sui dati.