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ę:

$$cyfra = n\ mod\ 10$$

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

$$n = n\ div\ 10$$

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.

$$ 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}}}$$

$$=3+2+1+0=6$$

#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;
}