Lectia 17
Conversii între baze de numeraţie
Toate calculele pe care le efectuăm în ziua de azi sunt efectuate în sistemul de numeraţe zecimal, sau altfel spus în baza 10 de numeraţie. În continuare vom prezenta un algoritm simplu, didactic, care realizează conversii de numere în una din bazele de numeraţie b. În general un număr scris în baza b are următoarea formă generală:
xn-1xn-2 ...x1x0, x-1x-2...x-m= x*bn-1+x*bn-2+ ...x*b1+x*b0+x*b-1+x*b-2+...x*b-m = ,
unde xi[0,b-1].
Exemplu: dacă b=10 atunci numărul 123,45=1*102+2*101+3*100+4*10-1+5*10-2 .
Conversia din baza 10 în baza b
Trecerea unui număr de la o bază la alta presupune aflarea unei secvenţe unice de resturi conform algoritmului următor:
· numărul se împarte la bază şi se reţine restul obţinut. Acesta constituie ultima cifră din reprezentarea în acea bază;
· câtul obţinut în urma acestei prime împărţiri este din nou împărţit la bază şi se reţine iaraşi restul. Acest rest constituie a doua cifră, în ordinea de la dreapta la stânga, a reprezentării în baza aleasă.
· algoritmul continuă până când câtul obţinut este zero. Ultimul rest al împărţirii la bază va reprezenta cea mai semnificativă cifră a numărului în baza în care s-a facut conversia.
Tabelul următor prezinta paşii acestui algoritm pentru trecerea numarului 25 în baza 2:
Pentru ascrie un algoritm care să realizeze această conversie vom proceda astfel:
citim numărul de transformat
citim baza în care dorim să facem conversia
începem să împărţim numărul dat la bază, iar cu resturile obţinute formăm un nou număr(care de fapt va fi scris după regula sistemului zecimal)
Algoritm în pseudocod:
//conversia din baza 10 în baza b din [2,10]
citeşte n,b // numere naturale, n-numărul de transformat, b-baza
m=0 // va conţine rezultatul conversiei
p=1 // puterile lui 10 iniţial 100=1
┌cât timp n≠0 execută
│ r=n%b // calculez restul împărţirii numărului la bază
│ m=m+r*p // formez valoarea noului număr
│ p=p*10 // cresc puterea lui 10
│ n=n/b // calculez câtul împărţirii numărului la bază
└■
scrie m // valoarea numărului în baza b
Această variantă de algoritm este una didactică şi se utilizează pentru conversii de numere naturale relativ mici, valoarea variabilei p creşte exponenţial şi nu poate depăşi 10 cifre. Pentru numere mai mari se vor utiliza alţi algoritmi şi alte tipuri de date pe care îî veţi studia mai târziu.
Conversia din baza 10 în baza b
De exemplu dacă baza de numeraţie este 2 şi valoarea numărului n=(110011)2 atunci transformarea lui în baza 10 se face astfel:
(110011)2=1*20+1*21+0*22+0*23+1*24+1*25=1+2+16+32=(51)10
Operaţia de trecere a unui număr scris în baza b la baza 10 se realizează după următorul algoritm în pseudocod:
//conversia unui număr n scris baza b, în baza 10
citeşte n,b // n – numărul de transformat, b baza în care este scris n
p=1 // b0=1
m=0 // va contine numarul în baza 10
┌cât timp n≠0 execută
│ c=n%10 // extrag cate o cifra din numarul dat
│ m=m+c*p // formez numarul adunând cifrele extrase din n cu puteri ale
│ // bazei
│ p=p*b // cresc puterea bazei
│ n=n/10 // elimin ultima cifra din n
└■
scrie m // valoarea numărului în baza 10
Pentru a realiza conversia unui număr din baza b1 în baza b2 vom proceda astfel:
o transformăm numărul din baza b1 în baza 10;
o transformam numărul obţinut anterior din baza 10 în baza b2.
Aplicaţii rezolvate
1. Se dă un număr natural n, scris în baza 10. Sa se verifice dacă numărul de cifre de zero este egal cu numărul de cifre de 1 în reprezentarea numărului în baza doi.
Exemplu: dacă n=(49)10 =(110001)2 are trei cifre de 1 şi trei cifre de zero, deci pe ecran trebuie afişat „Da, numar egal de cifre de 0 şi 1”;
dacă n=(54)10 =(110110)2 are patru cifre de 1 şi două cifre de zero, deci pe ecran trebuie afişat „Nu, numar diferit de cifre de 0 şi 1”.
Algoritmul în pseudocod este:
citeşte n //număr natural care trebuie transformat în baza 2
m=0 //conţine rezultatul conversiei numărului n în baza 2
nr0=0, nr1=0 //nr0-număr de cifre de 0 şi nr1-număr de cifre de 1 din m
p=1 //100=1
┌cât timp n≠0 execută
│ r = n%2 // determin restul împarţirii lui n la 2, poate fi 0 sau 1
│ ┌dacă r = 0 atunci
│ │ nr0=nr0+1 //număr ca am gasit o cifra de 0
│ │altfel
│ │ nr1=nr1+1 //număr ca am gasit o cifră de 1
│ └■
│ m=m+r*p // formez numărul în baza 2
│ p=p*10 // cresc puterea lui 10
│ n=n/2 // împart n la baza 2
└■
scrie m // afişez valoarea lui n în baza 2
// afişez rezultatul
┌dacă nr0 = nr1 atunci
│ scrie ”Da, are număr egal de cifre de 0 şi 1!”
│altfel
│ scrie ”Nu, numarul de cifre de 0 şi 1 este diferit”
└■
Program C++
#include< iostream.h>
#include<conio.h>
long n,m,nr0,nr1,r,p;
void main()
{ clrscr();
cout<<"n="; cin>>n;
p=1;
while(n!=0)
{r=r%2;
if(r==0)
nr0++;
else
nr1++;
m=m+r*p;
p=p*10;
n=n/2;
}
cout<<"numarul in baza 2 este "<<m;
cout<<endl;
if(nr0==nr1)
cout<<"Da are un numar egal de
cifre de 0 si 1";
else
cout<<"Nu, are numar diferit
de cifre de 0 si 1";
getch();
}
Rezultat afişat pe ecran
sau:
2. Se citeşte un număr natural n scris în baza b1. Secieţi un program care să transforme numărul în baza b2 (b1, b2numere naturale din [2,10]) .
Exemplu: dacă n=2301, b1= 4, iar b2= 9 atunci rezultatul va fi: (216)9 adică:
(2301)4=(177)10=(216)9
Algoritmul în pseudocod este:
citeşte n,b1,b2
// transformăm numărul n din baza b1 în baza 10
p=1
m=0 // contine rezultatul conversiei lui n din baza b1 în baza 10
┌cât timp n≠0 execută
│ r = n%10
│ m = m+r*p
│ p = p*b1
│ n = n/10
└■
// transformăm numărul m din baza 10 în baza b2
p=1
n=0 // contine rezultatul conversiei lui m din baza 10 în baza b2
┌cât timp m≠0 execută
│ r = n%b2
│ m = m+r*p
│ p = p*10
│ n = n/b2
└■
scrie n // afişez rezultatul
Program C++
#include<iostream.h>
#include<conio.h>
long n,m,r,p,b1,b2;
void main()
{ clrscr();
cout<<"Numarul de transformat n=";
cin>>n;
cout<<"Baza in care este scris numarul b1=";
cin>>b1;
cout<<"Baza in care fac conversia b2=";
cin>>b2;
//conversia lui n din b1 in baza 10
p=1;
while(n!=0)
{r=n%10;
m=m+r*p;
p=p*b1;
n=n/10;
}
cout<<"numarul in baza 10 este "<<m<<endl;
//conversia lui m din baza 10 in b2
p=1;
while(n!=0)
{r=m%b2;
n=n+r*p;
p=p*10;
m=m/b2;
}
cout<<"numarul in baza "<<b2<<" este "<<n;
getch();
}
Rezultat afişat pe ecran