Rezolvare A.1

Cuprins

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 = {\overset{―}{a_{k} \dots a_{2} a_{1} a_{0}}}_{(b)}$ reprezentarea lui x în baza b , adică $x = a_{0} \cdot b^{0} + a_{1} \cdot b^{1} + a_{2} \cdot b^{2} + \dots + a_{k} \cdot b^{k}$ . Rezultă:

adunăm și scădem $a_{1}$ , $a_{2}$ , …, $a_{k}$ : $x = a_{0} \cdot b^{0} + a_{1} \cdot b^{1} - a_{1} + a_{1} + a_{2} \cdot b^{2} - a_{2} + a_{2} + \dots + a_{k} \cdot b^{k} - a_{k} + a_{k}$
regrupăm termenii: $x = a_{1} \cdot b^{1} - a_{1} + a_{2} \cdot b^{2} - a_{2} + \dots + a_{k} \cdot b^{k} - a_{k} + a_{0} + a_{1} + a_{2} + \dots + a_{k}$
dăm factor comun pe $a_{1}$ , $a_{2}$ , …, $a_{k}$ : $x = a_{1} \cdot (b - 1) + a_{2} \cdot (b^{2} - 1) + \dots + a_{k} \cdot (b^{k} - 1) + a_{0} + a_{1} + a_{2} + \dots + a_{k}$

Aplicăm formula $a^{n} - 1 = (a - 1) (a^{k - 1} + a^{k - 2} + \dots + a^{1} + 1)$ :

$x = a_{1} \cdot (b - 1) + a_{2} \cdot (b - 1) \cdot (b + 1) + \dots + a_{k} \cdot (b - 1) \cdot (b^{k - 1} + \dots + b + 1) + a_{0} + a_{1} + a_{2} + \dots + a_{k}$
dăm factor comun pe $b - 1$ : $x = (b - 1) \cdot (a_{1} + a_{2} \cdot (b + 1) + \dots + a_{k} \cdot (b^{k - 1} + \dots + b + 1)) + a_{0} + a_{1} + a_{2} + \dots + a_{k}$

Deoarece $(b - 1) \cdot (a_{1} + a_{2} \cdot (b + 1) + \dots + a_{k} \cdot (b^{k - 1} + \dots + b + 1)) = (b - 1) \cdot M$ este multiplu al lui $b - 1$ , deducem că restul împărțirii lui x la $b - 1$ este egal cu restul împărțirii lui $S = a_{0} + a_{1} + a_{2} + \dots + a_{k}$ la $b - 1$ – ceea ce trebuia demonstrat.

Consecințe:

Restul împărțirii unui număr la 9 este egal cu restul împărțirii sumei cifrelor sale la 9.
Un număr natural este divizibil cu 9 dacă și numai dacă suma cifrelor sale este divizibilă cu 9.
Suma de control a unui număr natural $x$ este: ${\begin{cases} 0 & , daca x = 0 \\ 9 & , daca x este multiplu neul al lui 9 \\ x % 9 & , altfel \end{cases}$

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).