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șă ↓
Clasa a IX-aLecția 13 din 14 · mai este 1Urmează: IX.14 · Eficiența algoritmilor și recapitularea clasei a IX-aVezi toate lecțiile
Cuprins
- Ce înseamnă o bază de numerație
- Din baza 10 în baza b: împărțiri repetate
- Din baza b în baza 10
- Conversii rapide între bazele 2, 8, 16
- Biții unui număr (bonus)
- Greșeli frecvente
- La BAC
- Exersează pe hârtie
- Mai departe (pentru cine vrea mai mult)
- Rezumat
- Fișa de lucru
- Probleme de lucru
- Temă
- Pentru cei care vor mai mult
- Citește și exersează în plus
- Răspunsuri
Fișiere PDF și de lucru
- Lecția în PDF
versiunea de printat
- Fișa de lucru: Șiruri recurente, secvențe și baze de numerație
6 pagini · 100 min
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
| 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 : 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₍₁₆₎.
| 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șin / 2sunt „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.
- ușoară
- ușoară
- ușoară
bazab#426
https://www.pbinfo.ro/probleme/426/bazab
Temă
Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.
- ușoară
- ușoară
- ușoară
bazaminima#427
https://www.pbinfo.ro/probleme/427/bazaminima
- ușoară
cifrebinare#122
https://www.pbinfo.ro/probleme/122/cifrebinare
- ușoară
easypow#2872
https://www.pbinfo.ro/probleme/2872/easypow
Pentru cei care vor mai mult
- medie
sumaputeri2#3348
https://www.pbinfo.ro/probleme/3348/sumaputeri2
- dificilă
douabaze#946
https://www.pbinfo.ro/probleme/946/douabaze
Citește și exersează în plus
- Baze de numerație · pbinfo.ro
https://www.pbinfo.ro/articole/5562/baze-de-numeratie
- Operații pe biți · pbinfo.ro
https://www.pbinfo.ro/articole/62/operatii-pe-biti
- Binary Game — învață să numeri în binar · catonmat.net
joc scurt pentru a citi rapid numere binare (engleză)
https://catonmat.net/ftp/binary-game.html
- cppreference — operatori pe biți · en.cppreference.com
tabelul complet &, |, ^, <<, >> (secțiunea Bitwise logic operators)
https://en.cppreference.com/w/cpp/language/operator_arithmetic
- Python Tutor pentru C++ · pythontutor.com
urmărește cum se construiește rezultatul la conversia în altă bază
https://pythontutor.com/cpp.html
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.