SISergiu Ilincameditații informatică
Meniu

clasa a IX-a · Algoritmi elementari · lecția 13

Baze de numerație: baza 2, baza 10, baza b

60 mintoate profilurile

Înainte de lecția asta: IX.9 Cifrele unui număr: sumă, oglindit, palindrom, construire de numere

Ce vei ști după lecție

  • Înțelegi ce înseamnă scrierea unui număr într-o bază b.
  • Transformi un număr din baza 10 în baza b (împărțiri repetate) și invers.
  • Faci conversii rapide 2 ↔ 8 ↔ 16 pe hârtie.
  • Rezolvi probleme cu cifrele binare ale unui număr.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Fișiere PDF și de lucru

1. Ce înseamnă o bază de numerație

În baza 10 avem cifrele 0–9, iar poziția unei cifre îi dă valoarea:

3507 = 3·10³ + 5·10² + 0·10¹ + 7·10⁰

În baza b avem cifrele 0 … b−1, iar pozițiile valorează puteri ale lui b:

1011₍₂₎ = 1·2³ + 0·2² + 1·2¹ + 1·2⁰ = 8 + 0 + 2 + 1 = 11

1011 în baza 2

Baza Cifre Unde apare
2 (binar) 0, 1 memoria calculatorului (biți)
8 (octal) 0–7 permisiuni de fișiere în Linux
10 (zecimal) 0–9 viața de zi cu zi
16 (hexazecimal) 0–9, A–F culori (#FF8800), adrese de memorie

De ce așa?

De ce calculatoarele folosesc baza 2? Un circuit electronic are două stări sigure: curent / fără curent. Zece stări distincte ar fi scumpe și nesigure, două sunt ieftine și robuste. Orice număr, text, imagine sau sunet se reduce la un șir de 0 și 1; baza 16 e doar o scriere scurtă pentru cititorul uman.

2. Din baza 10 în baza b: împărțiri repetate

Împărțim repetat la b; resturile, citite de jos în sus, sunt cifrele.

13 în baza 2

13 în baza 2: 13 : 2 = 6 rest 1 → 6 : 2 = 3 rest 0 → 3 : 2 = 1 rest 1 → 1 : 2 = 0 rest 1 → 13 = 1101₍₂₎

De ce așa?

De ce funcționează? Restul la împărțirea cu b este ultima cifră în baza b (exact cum n % 10 e ultima cifră în baza 10). Împărțirea n / b „taie” ultima cifră. Algoritmul de la cifrele unui număr, aplicat cu b în loc de 10. Resturile ies în ordine inversă: de la ultima cifră la prima, de aceea le citim de jos în sus.

În cod, resturile vin în ordine inversă, așa că folosim metoda cu puterea lui 10 (ca la construirea numerelor din cifre):

#include <iostream>
using namespace std;

int main()
{
    long long n, b, rez = 0, p = 1;
    cin >> n >> b;
    while (n > 0)
    {
        rez += (n % b) * p;
        p *= 10;
        n /= b;
    }
    cout << rez;
    return 0;
}
n n % 2 p rez n după
13 1 1 1 6
6 0 10 1 3
3 1 100 101 1
1 1 1000 1101 0

Atenție — greșeli frecvente

Metoda funcționează doar pentru b ≤ 10 și numere mici (un număr de 10 cifre în baza 2 are ~30 de cifre și nu mai încape într-un long long ca „număr zecimal”). Pentru baze mari sau numere mari, memorează cifrele într-un vector sau afișează-le recursiv.

3. Din baza b în baza 10

Metoda 1 (puteri): parcurgi cifrele de la dreapta și aduni cifra · bᵏ:

#include <iostream>
using namespace std;

int main()
{
    long long x, b, val = 0, p = 1;     // x = cifrele în baza b, scrise „ca un număr zecimal”
    cin >> x >> b;
    while (x > 0)
    {
        val += (x % 10) * p;
        p *= b;
        x /= 10;
    }
    cout << val;
    return 0;
}
x cifra x % 10 p val
1101 1 1 1
110 0 2 1
11 1 4 5
1 1 8 13

Metoda 2 (Horner), când citești cifrele de la stânga la dreapta:

val = 0;
// pentru fiecare cifră c, în ordinea de la stânga:
val = val * b + c;

Exemplu: 1101₍₂₎ → 0 → 1 → 1·2+1 = 3 → 3·2+0 = 6 → 6·2+1 = 13.

De ce așa?

De ce funcționează Horner? Fiecare cifră nouă „împinge” tot ce ai până acum cu o poziție spre stânga (înmulțirea cu b) și intră la unități. La baza 10 faci același lucru când citești un număr cifră cu cifră: din „12” și cifra 3 obții 123 = 12·10 + 3. E exact og = og * 10 + c de la numărul oglindit.

4. Conversii rapide între bazele 2, 8, 16

Fiindcă 8 = 2³ și 16 = 2⁴:

  • o cifră octală ↔ 3 biți: 101 110₍₂₎ = 56₍₈₎;
  • o cifră hexazecimală ↔ 4 biți: 1010 1111₍₂₎ = AF₍₁₆₎.

Grupe de 4 biți

Hex 0 1 … 9 A B C D E F
Zecimal 0 1 … 9 10 11 12 13 14 15
Binar 0000 0001 … 1001 1010 1011 1100 1101 1110 1111

De ce așa?

De ce hexazecimal în loc de zecimal pentru culori? Un canal de culoare are 8 biți = 2 cifre hexazecimale exact (00–FF = 0–255). Culoarea #FF8800 înseamnă roșu 255, verde 136, albastru 0: fiecare pereche de cifre e un octet. În zecimal nu există o împărțire atât de curată.

Sfat

Ca să convertești orice număr zecimal în binar „în cap”, scrie puterile lui 2 (1, 2, 4, 8, 16, 32, 64, 128) și scade-le de la cea mai mare care încape: 100 = 64 + 32 + 4 → 1100100₍₂₎.

5. Biții unui număr (bonus)

  • n % 2 = ultimul bit, n / 2 = taie ultimul bit (exact ca la cifrele zecimale).
  • Puterile lui 2 au un singur bit de 1: 1, 10, 100, 1000…₍₂₎.
  • Operatorii pe biți &, |, ^, <<, >> lucrează direct pe biți: 1 << k = 2ᵏ, n & 1 = ultimul bit.
#include <iostream>
using namespace std;

int main()
{
    int n, uni = 0;
    cin >> n;
    while (n > 0)
    {
        uni += n % 2;      // același lucru cu n & 1
        n /= 2;
    }
    cout << uni;           // câți biți de 1 are n
    return 0;
}

6. Greșeli frecvente

Greșeala Efect Corect
resturile citite de sus în jos numărul oglindit de jos în sus
val = val + c * b la Horner rezultat greșit val = val * b + c
cifră ≥ baza (de exemplu 2 în binar) număr invalid verifică cifrele
scrii 1101 și crezi că e „o mie o sută unu” confuzie între baze notează baza: 1101₍₂₎
p pornit de la 0 rezultat 0 p = 1

7. La BAC

La BAC

Bazele de numerație nu mai apar în grilele actuale de la BAC (mate-info), dar ideea lor e peste tot: algoritmul „împărțiri repetate” e algoritmul cifrelor, iar grilele cu n % 2 și n / 2 sunt, de fapt, grile despre baza 2 (de exemplu „câți biți de 1” sau „n este putere a lui 2”). La concursuri (olimpiade) bazele apar direct.

8. Exersează pe hârtie

Răspunsurile sunt la final: încearcă întâi singur.

1. Transformă în baza 2: 25, 64, 100.

2. Transformă în baza 10: 11111₍₂₎, 777₍₈₎, FF₍₁₆₎.

3. Care este cea mai mică bază în care poate fi scris numărul 4073? (Indiciu: cifra maximă.)

4. Câte numere naturale au exact 5 cifre în baza 2?

5. Scrie 45 în baza 2.

6. Convertește AF₍₁₆₎ în baza 10, trecând prin baza 2.

7. Câte cifre are 1000 în baza 2?

8. Ce afișează secvența?

int n = 13, c = 0;
while (n > 0) { c += n % 2; n /= 2; }
cout << c;

9. Ce valoare au 1 << 5 și 13 & 1?

10. Scrie un program care afișează DA dacă n este putere a lui 2 și NU altfel (indiciu: câți biți de 1 are o putere a lui 2?).

9. Mai departe (pentru cine vrea mai mult)

Numere negative. Calculatorul reprezintă -5 prin „complement față de 2”: se inversează toți biții lui 5 și se adaugă 1. Așa se face că int merge de la −2³¹ la 2³¹ − 1 și că depășirea unui int „se întoarce” la valori negative.

De ce 0.1 + 0.2 != 0.3. Numerele reale se păstrează în binar. Fracția 0,1 nu are o scriere finită în baza 2 (la fel cum 1/3 nu are o scriere finită în baza 10), deci se rotunjește. De aceea comparațiile cu == între double sunt riscante: compară cu o toleranță (fabs(a - b) < 1e-9).

Trucuri cu biți. n & (n - 1) șterge cel mai din dreapta bit de 1: un număr e putere a lui 2 dacă n > 0 && (n & (n - 1)) == 0. n & 1 testează paritatea mai rapid decât % 2. Măști de biți (1 << k) reprezintă submulțimi: o mulțime de 20 de elemente încape într-un int.

Alte baze. Baza 3 echilibrată (cifre −1, 0, 1), baza fibonacci, baza −2: sunt subiecte de concurs. Principiul e același: împărțiri repetate cu atenție la rest.

Rezumat

  • Baza 10 → baza b: împărțiri repetate la b, resturile citite invers.
  • Baza b → baza 10: Σ cifră · bᵖᵒᶻⁱᵗⁱᵉ sau Horner (val = val * b + c).
  • 3 biți = o cifră octală, 4 biți = o cifră hexazecimală.
  • n % 2 și n / 2 sunt „ultimul bit” și „taie ultimul bit”.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 100 min

Șiruri recurente, secvențe și baze de numerație

  • Generezi termenii unui șir recurent cu o fereastră de 2–3 variabile, în ordinea corectă a atribuirilor.
  • Prelucrezi secvențe citite comparând cu elementul anterior: platouri, monotonie, recorduri.
  • Treci un număr dintr-o bază în alta (împărțiri repetate, Horner, grupe de biți) și lucrezi cu cifrele binare.

Fișa acoperă și: IX.12

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • cifbin#429

    Câte cifre de 0 și de 1 are n în baza 2.

    ușoară
  • transfb#428

    Din baza b în baza 10.

    ușoară
  • bazab#426

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • baze#945

    Din baza b în baza c: treci prin baza 10.

    ușoară
  • baza16#947

    Cifrele peste 9 se scriu A–F.

    ușoară
  • bazaminima#427

    ușoară
  • cifrebinare#122

    ușoară
  • easypow#2872

    ușoară

Pentru cei care vor mai mult

  • sumaputeri2#3348

    medie
  • douabaze#946

    dificilă

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. 25 = 11001₍₂₎ (16 + 8 + 1); 64 = 1000000₍₂₎; 100 = 1100100₍₂₎ (64 + 32 + 4).

2. 11111₍₂₎ = 31; 777₍₈₎ = 7·64 + 7·8 + 7 = 511; FF₍₁₆₎ = 15·16 + 15 = 255.

3. Cifra maximă din 4073 este 7, deci baza minimă este 8 (într-o bază b cifrele sunt 0 … b − 1).

4. 16: numerele de la 10000₍₂₎ = 16 până la 11111₍₂₎ = 31.

5. 45 = 32 + 8 + 4 + 1 = 101101₍₂₎.

6. AF = 1010 1111₍₂₎ = 128 + 32 + 8 + 4 + 2 + 1 = 175; direct: 10·16 + 15 = 175.

7. 10 cifre: 2⁹ = 512 ≤ 1000 < 1024 = 2¹⁰.

8. 3. 13 = 1101₍₂₎ are trei cifre de 1. Secvența numără biții de 1.

9. 1 << 5 = 32; 13 & 1 = 1 (ultimul bit al lui 13 = 1101₍₂₎).

10.

#include <iostream>
using namespace std;

int main()
{
    int n, uni = 0;
    cin >> n;
    int m = n;
    while (m > 0)
    {
        uni += m % 2;
        m /= 2;
    }
    cout << (n > 0 && uni == 1 ? "DA" : "NU");
    return 0;
}

O putere a lui 2 are un singur bit de 1 (1, 10, 100…₍₂₎). Cazul n = 0 are zero biți de 1 și nu e putere a lui 2.