Матч 343, Стойкое число (PersistentNumber)

Дивизион 2, Уровень 1

 

По заданному числу х определим функцию p(x), равную произведению его цифр. Образуем последовательность x, p(x), p(p(x)), … . Стойкостью числа x назовем наименьший индекс однозначного числа в указанной последовательности. Нумерация индексов в последовательности начинается с нуля. Например, для x = 99 имеем: p(99) = 9 * 9 = 81, p(81) = 8 * 1 = 8. Стойкость числа 99 равна 2.

 

Класс: PersistentNumber

Метод: int getPersistence(int n)

Ограничения: 0 £ n £ 2 * 109.

 

Вход. Целое число n.

 

Выход. Стойкость числа n.

 

Пример входа

n

99

268

86898

 

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

2

4

7

 

 

РЕШЕНИЕ

рекурсия

 

Последовательно вычисляем значения x, p(x), p(p(x)), … до тех пор, пока очередное число в последовательности не станет меньше 10. Функция p(x) вычисляет произведение цифр числа x.

 

ПРОГРАММА

 

#include <stdio.h>

 

int p(int x)

{

  return (x < 10) ? x : p(x / 10) * (x % 10);

}

 

class PersistentNumber

{

  public:

  int getPersistence(int n)

  {

    return (n < 10) ? 0 : getPersistence(p(n)) + 1;

  }

};