Școala Româno-Britanică
Modulul 5 Clasa a X-a | C++

Ora 3: Suma cifrelor unui număr - recursiv

Ce vei învăța astăzi: Cum se descompune un număr în cifre și cum se calculează suma cifrelor recursiv, cu % și /

Rezultat practic: Scrii funcția recursivă suma_cifre în C++ și o folosești în probleme pe cifre (Competența 3.5)

Competența 3.5 Săptămâna 26

Înainte de a începe

De ce contează? Suma cifrelor este o problemă frecventă la evaluare și pe platforma PbInfo, fiind primul pas pentru orice prelucrare a cifrelor unui număr.

Ce știi deja?

Din ora 2, știi cazul de bază al factorialului? Cum extragi ultima cifră a unui număr și cum o elimini folosind % și /?

Ideea-cheie: Suma cifrelor se reduce cu n % 10 + suma_cifre(n / 10), până când n devine 0.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei scrie funcția recursivă care calculează suma cifrelor unui număr, folosind operațiile % (modulo) și / (împărțire întreagă).

Descompunerea unui număr în cifre
Definiția recursivă a sumei cifrelor
Operatorii % și /
Program complet în C++

Cum descompunem un număr în cifre?

Ultima cifră a unui număr se obține cu n % 10 (modulo, adică restul împărțirii la 10), iar numărul fără ultima cifră cu n / 10 (împărțire întreagă, adică fără rest). Repetând aceste operații, obținem toate cifrele.

Exemplu pentru n = 1234: cifrele sunt 4, 3, 2, 1, iar suma lor este 10.

Descompunerea lui 1234
1234ultima cifră = 1234 % 10 = 4
123ultima cifră = 123 % 10 = 3
12ultima cifră = 12 % 10 = 2
1ultima cifră = 1 % 10 = 1
0stop: nu mai există cifre

Funcția recursivă pentru suma cifrelor

Definiția recursivă: suma_cifre(n) = n % 10 + suma_cifre(n / 10), cu cazul de bază suma_cifre(0) = 0.

Algoritm suma_cifre(n): dacă n == 0 atunci returnează 0 altfel returnează (n % 10) + suma_cifre(n / 10)
Program C++ - suma cifrelor recursiv
#include <iostream>
using namespace std;

int suma_cifre(int n)
{
    if (n == 0)
        return 0;
    return n % 10 + suma_cifre(n / 10);
}

int main()
{
    int n;
    cout << "n = ";
    cin >> n;
    cout << suma_cifre(n);
    return 0;
}

Exemplu: suma_cifre(1234)

  • suma_cifre(1234) = 4 + suma_cifre(123)
  • suma_cifre(123) = 3 + suma_cifre(12)
  • suma_cifre(12) = 2 + suma_cifre(1)
  • suma_cifre(1) = 1 + suma_cifre(0)
  • suma_cifre(0) = 0 (cazul de bază)
  • Rezultat: 4 + 3 + 2 + 1 + 0 = 10

Ce putem calcula asemănător?

Alte aplicații pe cifre

  • Numărul de cifre: numar_cifre(n) = 1 + numar_cifre(n / 10), caz de bază n < 10
  • Produsul cifrelor: produs_cifre(n) = (n % 10) * produs_cifre(n / 10)
  • Prima cifră: obținută prin apeluri succesive cu n / 10 până la o singură cifră

Observă: toate aceste probleme descompun numărul cu % 10 și / 10, exact ca suma cifrelor.

Exercițiu de completare

Completează enunțul despre suma cifrelor cu cuvintele potrivite:

Ultima cifră a unui număr n se obține cu operația ______ (modulo), iar numărul fără ultima cifră cu ______ (împărțire întreagă). Suma cifrelor se calculează recursiv prin relația suma_cifre(n) = n % 10 + suma_cifre(n / 10), cu cazul de bază suma_cifre(0) = ______. Pentru n = 1234, suma cifrelor este ______.

Bancă de cuvinte:
% / 0 10

Exercițiu de completare

Completează funcția suma_cifre din codul C++:
______ suma_cifre(int n)
{
    if (______)
        ______ 0;
    return n ______ + suma_cifre(n / 10);
}
Bancă de cuvinte:
int n == 0 return % 10

Test de înțelegere

Test rapid - suma cifrelor:

1. Ultima cifră a numărului 987 se obține cu:

2. suma_cifre(0) are valoarea:

3. Pentru n = 45, suma cifrelor este:

Ai grijă la: cazul n == 0 dă suma 0 - dacă tratezi greșit numărul 0 sau o cifră egală cu 0, rezultatul poate fi greșit pentru numerele care conțin zerouri.

Aprofundare

Ce se întâmplă cu numărul 0? Pentru n = 0, funcția întoarce 0, ceea ce este corect (suma cifrelor lui 0 este 0). Pentru numerele cu o singură cifră, suma_cifre(7) = 7 % 10 + suma_cifre(0) = 7 + 0 = 7, deci algoritmul funcționează fără un caz special suplimentar.

Derivatele algoritmului. Același mecanism de descompunere n % 10 și n / 10 stă la baza altor prelucrări recursive ale cifrelor:

  • Numărul de cifre: numar_cifre(n) = 1 + numar_cifre(n / 10), cu cazul de bază n < 10.
  • Produsul cifrelor: produs_cifre(n) = (n % 10) * produs_cifre(n / 10), cu cazul de bază n == 0.
  • Inversul unui număr: se construiește cifră cu cifră, purtând rezultatul parțial ca parametru suplimentar.
  • Afișarea cifrelor în ordine inversă: cout << n % 10 la coborâre pe stivă, apoi apelul cu n / 10.

Cifra de control (suma cifrelor repetată până la o singură cifră). Aplicând suma cifrelor în mod repetat până se obține o singură cifră, obținem cifra de control (cifra folosită la verificarea unor coduri, de exemplu coduri de bare și numere de cont) a numărului.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Suma cifrelor

Enunț:

Cerință: Se citește un număr natural n. Să se afișeze suma cifrelor lui n, folosind un subprogram recursiv.

Date de intrare:

Programul citește de la tastatură numărul natural n.

Date de ieșire:

Programul va afișa pe ecran suma cifrelor lui n.

Restricții și precizări:

0 ≤ n ≤ 2.000.000.000. Suma cifrelor nu depășește valoarea unui int.

Exemplu:

Intrare:

1234

Ieșire:

10
Cum gândim soluția:
  1. Definim funcția suma_cifre(n)
  2. Cazul de bază: dacă n == 0, întoarcem 0
  3. Altfel întoarcem n % 10 + suma_cifre(n / 10)
  4. În main citim n și afișăm rezultatul
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int suma_cifre(int n)
{
    if (n == 0)
        return 0;
    return n % 10 + suma_cifre(n / 10);
}

int main()
{
    int n;
    cin >> n;
    cout << suma_cifre(n);
    return 0;
}

Ce învățăm: problema se reduce la descompunerea numărului cu % și /, iar cazul de bază n == 0 oprește recurența.

PbInfo - Produsul cifrelor

Enunț:

Cerință: Se citește un număr natural n, cu toate cifrele nenule. Să se afișeze produsul cifrelor lui n, folosind un subprogram recursiv.

Date de intrare:

Programul citește de la tastatură numărul natural n.

Date de ieșire:

Programul va afișa pe ecran produsul cifrelor lui n.

Restricții și precizări:

1 ≤ n ≤ 2.000.000.000 și n nu conține cifra 0.

Exemplu:

Intrare:

234

Ieșire:

24
Cum gândim soluția:
  1. Definim funcția produs_cifre(n)
  2. Cazul de bază: dacă n == 0, întoarcem 1 (element neutru)
  3. Altfel întoarcem (n % 10) * produs_cifre(n / 10)
  4. În main citim n și afișăm rezultatul
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;

int produs_cifre(int n)
{
    if (n == 0)
        return 1;
    return (n % 10) * produs_cifre(n / 10);
}

int main()
{
    int n;
    cin >> n;
    cout << produs_cifre(n);
    return 0;
}

Ce învățăm: pentru produs, cazul de bază întoarce 1 (elementul neutru al înmulțirii), nu 0.

EXERCIȚII PRACTICE

Exercițiul Practic: Cifrele unui număr

Sarcini de lucru

Rezolvă sarcinile următoare despre cifrele unui număr

Sarcina 1: Numărul de cifre

Cerință: Scrie un program C++ care afișează numărul de cifre ale unui număr natural n, folosind o funcție recursivă. Pentru n = 12345 rezultatul este 5.

Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;

int numar_cifre(int n)
{
    if (n < 10)
        return 1;
    return 1 + numar_cifre(n / 10);
}

int main()
{
    int n;
    cin >> n;
    cout << numar_cifre(n);
    return 0;
}

Verifică: cazul de bază este n < 10 (o singură cifră), iar fiecare apel reduce numărul cu o cifră.

Sarcina 2: Media cifrelor

Cerință: Scrie un program C++ care afișează media aritmetică a cifrelor unui număr n, folosind suma cifrelor și numărul de cifre calculate recursiv. Pentru n = 12 media este 1.5.

Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;

int suma_cifre(int n)
{
    if (n == 0)
        return 0;
    return n % 10 + suma_cifre(n / 10);
}

int numar_cifre(int n)
{
    if (n < 10)
        return 1;
    return 1 + numar_cifre(n / 10);
}

int main()
{
    int n;
    cin >> n;
    cout << (double)suma_cifre(n) / numar_cifre(n);
    return 0;
}

Scrie pe caiet

Titlul lecției

Suma cifrelor unui număr - recursiv. A treia lecție din Modulul 5 îți arată cum se descompune un număr în cifre și se calculează suma lor recursiv.

Definiția lecției

Suma cifrelor unui număr natural se calculează descompunând numărul cu două operații: n % 10, care extrage ultima cifră, și n / 10, care elimină ultima cifră. Definiția recursivă este suma_cifre(n) = n % 10 + suma_cifre(n / 10), cu cazul de bază suma_cifre(0) = 0. Pentru n = 1234, apelurile adună pe rând 4, 3, 2 și 1, iar rezultatul final este 10. Suma parțială se construiește la întoarcerea din apeluri, pe stivă. Același mecanism de descompunere se reutilizează pentru numărul de cifre, produsul cifrelor sau inversul unui număr. Aplicând suma cifrelor repetat până la o singură cifră, obținem cifra de control a numărului.

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritm suma_cifre(n): dacă n == 0 atunci returnează 0 altfel returnează (n % 10) + suma_cifre(n / 10)

Algoritmul cheie - cod C++

Program C++ - suma cifrelor recursiv
#include <iostream>
using namespace std;

int suma_cifre(int n)
{
    if (n == 0)
        return 0;
    return n % 10 + suma_cifre(n / 10);
}

int main()
{
    int n;
    cout << "n = ";
    cin >> n;
    cout << suma_cifre(n);
    return 0;
}

Greșeli comune de evitat

Exemplu practic

Scenariu real: la un magazin, codul unui bilet este 3456 și vrei să verifici rapid suma cifrelor lui: 3 + 4 + 5 + 6 = 18. Funcția recursivă face calculul automat:

Program C++ - suma cifrelor (exemplu practic)
int suma_cifre(int n)
{
    if (n == 0)
        return 0;
    return n % 10 + suma_cifre(n / 10);
}

Apelul suma_cifre(3456) întoarce 18.

Sfaturi practice și trucuri