Тип 16 № 64901 
Рекурсивные алгоритмы. Алгоритмы, опирающиеся на несколько предыдущих значений
i
Обозначим через a%b остаток от деления натурального числа a на натуральное число b, а через a//b — целую часть от деления a на b.
Функция F(n), где n — неотрицательное целое число, задана следующими соотношениями:
F(n) = 1, если n = 0;
F(n) = (n%10) · F(n//100), если n нечётно;
F(n) = F(n//100), если n > 0 и n чётно.
Определите количество таких целых k, что 107 ≤ k ≤ 8 · 107 и F(k) = 35.
Решение. Для примера найдем значение F(12345):
Рассмотрим значение F(1234):
То есть алгоритм считает произведение цифр стоящих на четных местах числа, если цифра нечетная. При этом нас интересуют только числа, произведение нечетных цифр которого, стоящих на четных местах, дают ответ 35. Число 35 можно получить произведением цифр 5 и 7 (и 1, и это учтем в дальнейших вычислениях).
Всего число у нас состоит из 8 цифр. На одном из двух четных мест должны стоять или 5, или 7 (таких позиций для одной цифры 4, тогда для другой останется 3).
На остальных четных местах могут стоять числа 0, 1, 2, 4, 6, 8 (цифра 1, так как она не увеличивает произведение чисел. Таких позиций остается 2).
На первом месте в числе могут стоять цифры 1, 2, 3, 4, 5, 6, 7 (0 не может стоять на первом месте, 8 и 9 превысят отведенный диапазон).
На остальных нечетных местах могут стоять любые цифры (таких позиций в числе 3).
Посчитаем количество чисел из диапазона k, что 107 ≤ k ≤ 8 · 107 и F(k) = 35:
Ответ: 3 024 000.
Приведём решение на языке Python.
def f(n):
if n == 0:
return 1
if n%2!=0:
return (n%10)*f(n//100)
if n%2==0:
return f(n//100)
count = 0
for x in range(10**7,8*10**7+1):
if f(x)==35:
count += 1
print(count)
Ответ: 3024000
