255. Лицензионное ПО

 

Как вы знаете, для удостоверения лицензионности ПО используются серийные номера и регистрационные ключи. Вами, как ведущими разработчиками систем верификации лицензионности ПО была разработана идея надежнейшей в своём роде системы. Основывается она на цифровых корнях чисел. Теперь вам требуется написать программу, определяющую цифровой корень данного числа.

Для произвольного числа цифровой корень определяется следующим образом:

1.     Если сумма цифр числа меньше десяти, то цифровой корень и есть сумма цифр этого числа.

2.     В противным случае цифровой корень числа равен цифровому корню суммы его цифр.

 

Вход. Единственное число n (0 ≤ n ≤ 231 – 1).

 

Выход. Вывести цифровой корень числа n.

 

Пример входа

Пример выхода

123

6

 

 

РЕШЕНИЕ

математика

 

Анализ алгоритма

Обозначим сумму цифр числа n через S(n). Число n делится на 9 тогда и только тогда, когда S(n) делится на 9. В задаче требуется найти значение S(S(…S(n)…)), которое меньше 10. Оно равно n mod 9, так как числа n и S(S(…S(n)…)) дают одинаковый остаток при делении на 9. При этом если входное значение n = 0, то результат равен 0. Если n > 0 и n mod 9 = 0, то результирующее значение равно 9.

Искомую сумму можно также вычислить при помощи выражения (n – 1) % 9 + 1.

 

Реализация алгоритма

Совершим вычисление ответа по выше приведенной формуле.

 

scanf("%d",&n);

res = (n-1) % 9 + 1;

printf("%d\n",res);

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int res = (n - 1) % 9 + 1;

    System.out.println(res);

  }

}

 

Python реализация

 

n = int(input())

if n == 0: res = 0

else: res = (n - 1) % 9 + 1

print(res)