9300 afișări Candale Silviu (silviu) 03.02.2019
www.pbinfo.ro
Etichete: nicio etichetă

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=aka2a1a0(b) reprezentarea lui x în baza b , adică x=a0b0+a1b1+a2b2++akbk. Rezultă:

  • adunăm și scădem a1, a2, …, ak: x=a0b0+a1b1a1+a1+a2b2a2+a2++akbkak+ak
  • regrupăm termenii: x=a1b1a1+a2b2a2++akbkak+a0+a1+a2++ak
  • dăm factor comun pe a1, a2, …, ak: x=a1(b1)+a2(b21)++ak(bk1)+a0+a1+a2++ak

Aplicăm formula an1=(a1)(ak1+ak2++a1+1):

  • x=a1(b1)+a2(b1)(b+1)++ak(b1)(bk1++b+1)+a0+a1+a2++ak
  • dăm factor comun pe b1: x=(b1)(a1+a2(b+1)++ak(bk1++b+1))+a0+a1+a2++ak

Deoarece (b1)(a1+a2(b+1)++ak(bk1++b+1))=(b1)M este multiplu al lui b1, deducem că restul împărțirii lui x la b1 este egal cu restul împărțirii lui S=a0+a1+a2++ak la b1 – 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: {0, daca x=09, daca x este multiplu neul al lui 9x%9, altfel

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


9300 afișări Candale Silviu (silviu) 03.02.2019
www.pbinfo.ro
Du-te sus!