С++: Найти цифровой корень числа

Задача:

Написать рекурсивную и нерекурсивную функцию,
которая принимает положительный целочисленный аргумент
и возвращает цифровой корень этого числа. Цифровой
корень числа вычисляется следующим образом.
Складываются все цифры числа, затем все цифры
найденной суммы и т.д. Процесс повторяется до тех пор,
пока в результате не будет получено однозначное число
(цифра), которое и является цифровым корнем.

Начнем с нерекурсивного варианта.

Весь исходный код такой:

[cpp]
#include <locale.h>
#include <conio.h>

int SumOfDigits(int N)
{
int d=0, sum = 0;
while (N != 0)
{
d = N % 10;
sum  +=  d;
N = N / 10;
}
return sum;
}
int RootOfNumber (int k)
{
while (k>9)
{
k = SumOfDigits(k);
}
return k;
}

int main()
{
setlocale(LC_ALL, «Russian»);

int N;
printf («Введите целое число:\n»);
scanf («%d», &N );
printf («Сумма цифр числа %d = %d\n», N, RootOfNumber (N));

getch();

return 0;
}

[/cpp]

в функции main всё достаточно просто: сначала устанавливается русская локаль ( setlocale(LC_ALL, «Russian»);), затем пользователю выдается приглашение ввести число и это число считывается в переменную n целого типа. После этого печатается результат работы функции int RootOfNumber(int k).

Рассмотрим ее подробнее.

[cpp]

int RootOfNumber (int k)
{
while (k>9)
{
k = SumOfDigits(k);
}
return k;
}

[/cpp]

В нее передается целое число и пока оно содержит больше 1 знака (условие k > 9) выполняется вызов функции для складывания чисел внутри числа. Вызывается она с разными аргументами. У меня это k. На каждом витке цикла это число уменьшается, и рано или поздно оно станет меньше 10. Тогда функция вернет значение.

И последняя функция, которая просто вычисляет сумму цифр внутри числа:

[cpp]

int SumOfDigits(int N)
{
int d=0, sum = 0;
while (N != 0)
{
d = N % 10;
sum  +=  d;
N = N / 10;
}
return sum;
}

[/cpp]

Принимает целое число N. И пока N не станет равным нулю делит это число на 10 (основание системы счисления) и прибавляет остаток от деления к сумме, после чего делит N на 10 еще раз, но в этот раз уже записывает не остаток от деления, а целую часть. Так как происходит округление, то рано или поздно это число станет равным нулю.

Рекурсивный вариант той же функции:

Примечание: опубликован лишь код функции, так как ее вызов идентичен описанному выше.

[cpp]

int RootOfNumber(int N)
{
int d, sum = 0;
while (N != 0)
{
d = N % 10;
sum = sum + d;
N = N / 10;
}

if(sum<10)
{
return sum;
}
else
{
RootOfNumber(sum);
}
}

[/cpp]

Фишка рекурсивных функций в том, что она вызывает сама себя внутри себя. В этом коде нет дополнительной функции, которая считала бы сумму, но код содержится внутри. Т.е сначала на функцию подается число, для которого хорошо бы посчитать корень, далее для этого числа считается сумма его чисел и проверяется условие выхода из рекурсии — является ли число однозначным, т.е меньше 10. Если да, то выходим из рекурсии и возвращаем число, иначе — вызываем еще раз эту же функцию, но уже с новой суммой.

 

5 Responses

Добавить комментарий