Nu parcurgeți acest articol înainte de rezolvarea problemei!
Enunț:
Se consideră subalgoritmul alg(x, b)
cu parametrii de intrare două numere naturale x
și b
(1 ≤ x ≤ 1000
, 1 < b ≤ 10
).
Subalgoritm alg(x, b): s ← 0 CâtTimp x > 0 execută s ← s + x MOD b x ← x DIV b SfCâtTimp returnează s MOD (b - 1) = 0 SfSubalgoritm
Precizați efectul acestui subalgoritm.
A. calculează suma cifrelor reprezentării în baza b
a numărului natural x
B. verifică dacă suma cifrelor reprezentării în baza b - 1
a numărului x
este divizibilă cu b - 1
C. verifică dacă numărul natural x
este divizibil cu b - 1
D. verifică dacă suma cifrelor reprezentării în baza b
a numărului x
este divizibilă cu b - 1
Soluție
Răspuns corect: C, D
Justificare:
Reprezentarea în baza b
a unui număr natural x
se face prin împărțiri succesive la b
. Resturile (x MOD b
) reprezintă cifrele reprezentării.
Subalgoritmul determină suma acestor cifre și la final returnează rezultatul expresiei s MOD (b-1) = 0
, care este TRUE
sau FALSE
, după cum s
este sau nu divizibil cu b-1
, deci varianta C este corectă.
Să demonstrăm că și varianta D este corectă.
Vom demonstra următoarea
Proprietate:
Fie două numere naturale x
, și b > 1
. Restul împărțirii la b-1
a lui x
este egal cu restul împărțirii la b-1
a sumei cifrelor reprezentării lui x
în baza b
.
Demonstrație:
Fie x
în baza b
, adică
- adunăm și scădem
, , …, : - regrupăm termenii:
- dăm factor comun pe
, , …, :
Aplicăm formula
- dăm factor comun pe
:
Deoarece x
la
Consecințe:
- Restul împărțirii unui număr la
9
este egal cu restul împărțirii sumei cifrelor sale la9
. - Un număr natural este divizibil cu
9
dacă și numai dacă suma cifrelor sale este divizibilă cu9
. - Suma de control a unui număr natural
este:
Cifra de control a unui număr natural se determină calculând suma cifrelor numărului, apoi suma cifrelor sumei și așa
mai departe până când suma obținută reprezintă un număr cu o singură cifră. De exemplu, cifra de control a numărului
182
este 2
(1 + 8 + 2 = 11
, 1 + 1 = 2
).