Programowanie i algorytmy

Suma cyfr rekurencyjnie

Zad. 4. Napisz program, który wyznaczy sumę cyfr liczby naturalnej z zakresu [0...1020]. Rozwiąż zadanie metodą rekurencyjną.

 

Rozwiązanie

Aby wyłuskać cyfrę jedności danej liczby należy wykonać operację:

{tex}cyfra = n\ mod\ 10{/tex}

gdzie mod oznacza resztę z dzielenia. Następnym krokiem jest skrócenie liczby o jedną cyfrę wykonując operację

{tex}n = n\ div\ 10{/tex}

gdzie div oznacza dzielenie całkowite. Powtarzamy te operacje do momentu otrzymania liczby 0.

Rekurencyjnie wygląda to następująco. Przeanalizujmy przykład dla liczby 123.

{tex} sumacyfr(123)=\overbrace{123\ mod\ 10}^3+\underbrace{sumacyfr(\overbrace{123\ div\ 10}^{12})}_{\overbrace{12\ mod\ 10}^2+\underbrace{sumacyfr(\overbrace{12\ div\ 10}^{1})}_{\overbrace{1\ mod\ 10}^1 + \underbrace{sumacyfr(\overbrace{1\ div\ 10}^0)}_{0}}}{/tex}

{tex}=3+2+1+0=6{/tex}

#include<iostream>
#include<cstdlib>
using namespace std;
 
int suma_cyfr(long long n)
{
  if(n>0)
    return n%10 + suma_cyfr(n/10);
 
  return 0;
}
 
int main()
{
  long long n;
 
  cout<<"Podaj liczbę: ";
  cin>>n;
  cout<<"Suma cyfr liczby "<<n<<" wynosi "<<suma_cyfr(n)<<endl;
 
  system("pause");
  return 0;
}
 

 

powrót