Lectia 13

Algoritmi care prelucrează cifrele unui număr natural

Există nenumărate aplicaţii în practică, când ni se solicită informaţii despre cifrele din care este construi un număr, despre natura sau numărul lor. În acest caz cifrele numărului vor fi separate, una câte una, de la ultima cifră(cifra unităţilor) spre prima cifră. După fiecare prelucrare din numărul iniţial vom elimina ultima cifră, algoritmul conţinuând în acelaşi mod, în funcţie de numărul de cifre din numărul dat.

Şablonul de rezolvare al problemelor care prelucrează cifrele unui număr natural are următoarea formă:

citeşte numărul de prelucrat

iniţializarea variabilelor de manevră

┌cât timp numărul dat mai are cifre neprelucrate execută

│ - extrage ultima cifră din număr

│ - prelucrază această cifră conform enunţului din problemă

│ - elimină din numărul de prelucrat ultima lui cifră

└■

afişează rezultatul

Aplicaţii rezolvate

1. Se dă un număr natural n. Se cere să se scrie un algoritm care calculează suma cifrelor numărului dat.

Rezolvarea acestei probleme va urmări şablonul de rezolvare prezentat mai sus, tinând cont de faptul că atunci când avem de calculat o sumă de termeni, variabila care va conţine rezultatul se va iniţializa cu valoarea zero.

Algoritmul este:

citeşte n număr natural şi reprezintă numărul de prelucrat

s=0 va conţine, la final, suma cifrelor numărului n, iniţial va avea

valoarea zero

┌cât timp n>0 execută

│ c = n%10 extrag ultima cifră din numarul n

│ s = s+c adun cifra separată la suma cifrelor numărului n

│ n = n/10 elimin din numărul n ultima lui cifră

└■

scrie “suma cifrelor este ”, s

2. Se dă un număr natural n. Să se precizeze din câte cifre este alcătuit.

Algoritmul de rezolvare urmăreşte şablonul prezentat, doar că în acestă situaţie problema se simplifică. Nu mai avem nevoie de cifra să o păstrăm în variabila c, doar vom număra de câte ori putem împărţi numărul la 10, obţinând astfel numărul de cifre

Algoritmul este:

citeşte n număr natural şi reprezintă numărul de prelucrat

nr=0 va conţine numărul cifrelor numărului n, iniţial va avea

valoarea zero

┌cât timp n>0 execută

│ nr = nr+1 număr că am separat o cifră din numărului n

│ n = n/10 elimin din numarul n ultima lui cifra

└■

scrie “suma cifrelor este ”, s

3. Se dă un număr natural n. Se cere să se calculeze suma cifrelor pare din numărul dat.

Algoritmul este:

citeşte n număr natural şi reprezintă numărul de prelucrat

s=0 va conţine, la final, suma cifrelor pare din numărului n, iniţial

va avea valoarea zero

┌cât timp n>0 execută

│ c = n%10 // extrag ultima cifră din numărul n

│ ┌dacă c%2 == 0 atunci // dacă ultima cifră este pară

│ │ s = s+c // adun cifra separată la sumă

│ └■

│ n = n/10 //elimin din numarul n ultima lui cifră

└■

scrie “suma cifrelor este ”, s

4. Se dă un număr natural n. Se cere să se determine cifra maximă din numărul dat.

Atunci când avem de determinat valoarea maximă dintre un şir de numere, vom iniţializa variabila care va conţine maximul cu cea mai mică valoare posibilă. În cazul nostru trebuie să determinăm cifra maximă dintre cifrele unui număr dat, şi vom iniţializa cifra maximă cu valoarea zero, apoi vom extrage câte o cifră din număr şi o vom compara cu valoarea cifrei maxime. În situaţia în care am găsit o valoare mai mare vom actualiza informaţia din cifra maximă, cu ultima cifră extrasă din număr. Algoritmul continuă în acelaşi mod până când au fost prelucrate toate cifrele numărului dat.

Algoritmul este:

citeşte n număr natural şi reprezintă numărul de prelucrat

cif_max=0 va conţine, la final, cifra maximă din numărului n, iniţial

va avea valoarea zero

┌cât timp n>0 execută

│ c = n%10 // extrag ultima cifră din numărul n

│ ┌dacă c >= cif_max atunci // dacă ultima cifră este mai mare decât

│ │ cif_max = c // cifra maximă, atunci păstrez valoarea ei

│ └■

│ n = n/10 //elimin din numarul n ultima lui cifră

└■

scrie “cifra maxima este ”, cif_max

5. Se dă un număr natural n. Se cere să se determine numărul obţinut din n, dar care are cifrele în ordinea inversă.

Algoritmul este:

citeşte n // număr natural şi reprezintă numărul de prelucrat

m=0 // va conţine, la final, cifrelor numărului n în ordine inversă,

iniţial va avea valoarea zero

┌cât timp n>0 execută

│ c = n%10 // extrag ultima cifră din numarul n

│ m = m*10+c // adun cifra separată la numărului m modificând şi

│ semnificaţia cifrelor(cifra unităţilor va deveni cifra

│ zecilor, cifra zecilor va deveni cifra sutelor, etc.)

│ n = n/10 // elimin din numărul n ultima lui cifră

└■

scrie “numărul cu cifrele inversate este ”, m

6. Se dă un număr natural n. Se cere să se verifice dacă are toate cifrele pare.

Atunci când avem de a verifica îndeplinrea unei condiţii de către toate elementele unui şir vom proceda astfel:

· vom presupune că toate elementele şirului îndeplinesc condiţia cerută;

· vom verifica dacă există cel mult un număr din şir care nu verifică condiţia dată.

În situaţia nostră vom presupune iniţial că toate cifrele numărului dat sunt pare şi vom separa apoi câte o cifră din număr şi îi vom verifica paritatea. Dacă în numărul iniţial există cel mult o cifră pară, atunci vom ajunge la concluzia ca nu toate cifrele numărului dat sunt pare.

Algoritmul este:

citeşte n // număr natural şi reprezintă numărul de prelucrat

ok = 1 // presupun că toate cifrele numărului sunt pare, iniţial variabila

ok va avea valoarea unu

┌cât timp n>0 şi ok = 1 execută // numărul mai are cifre şi preupunerea

│ făcută rămâne valabilă

│ c = n%10 // extrag ultima cifră din numărul n

│ ┌dacă c%2 = 1 atunci // dacă ultima cifra extrasă este impară atunci

│ │ ok = 0 // presupunerea făcută nu este adevarată!

│ └■ // rezultă că nu toate cifrele lui n sunt pare

│ n = n/10 // elimin din numărul n ultima lui cifră

└■

┌daca ok = 1 atunci

│ scrie “Toate cifrele numarului dat sunt pare! ”

│altfel

│ scrie “NU toate cifrele numarului dat sunt pare! ”

└■

7. Se dă un număr natural n. Se cere să se verifice dacă numărul dat conţine cel putin o cifră pară.

Atunci când trebuie să verificam îndeplinrea unei condiţii de către cel puţin un element din şir vom proceda astfel:

· vom presupune că niciunul din elementele şirului nu îndeplinesc condiţia cerută;

· vom verifica dacă există cel puţin un număr din şir care verifică condiţia dată.

În situaţia nostră vom presupune iniţial că nici una din cifrele numărului dat nu este pară şi vom separa apoi câte o cifră din număr şi îi vom verifica paritatea. Dacă în numărul iniţial există cel puţin o cifră pară, atunci vom ajunge la concluzia ca în cifrele numărului dat există cel puţin o cifră pară.

Algoritmul este:

citeşte n // număr natural şi reprezintă numărul de prelucrat

ok = 0 // presupun că toate cifrele numărului sunt impare, iniţial

variabila ok va avea valoarea zero, nici o cifră nu îndeplineşte

condiţia cerută

┌cât timp n>0 şi ok = 0 execută // numărul mai are cifre şi preupunerea

│ făcută rămâne valabilă

│ c = n%10 // extrag ultima cifră din numărul n

│ ┌dacă c%2 = 0 atunci // dacă ultima cifra extrasă este pară atunci

│ │ ok = 1 // presupunerea făcută nu este adevarată!

│ └■ // rezultă că nu toate cifrele lui n sunt impare

│ n = n/10 // elimin din numărul n ultima lui cifră

└■

┌dacă ok = 1 atunci

│ scrie “Exista cel putin o cifra pară! ”

│altfel

│ scrie “NU există cifre pare, toate cifrele sunt impare! ”

└■