16 номер. Рекурсия
Вычисление рекурсивной функции
(PRO100 ЕГЭ) Алгоритм вычисления функций F(n) и G(n), где n – целое число, задан следующими соотношениями:
F(n) = G(n–1)
G(n) = n, если n < 10
G(n) = G(n–2) + 1, если n ≥ 10
Определите количество значений n на отрезке [1, 100], для которых значение функции F(n) будет полным квадратом некоторого натурального числа.
Подсказка
Начните с базового случая и направления изменения аргумента. Для выражения из нескольких значений сначала проверьте, можно ли сократить общую часть.
Решение
def F(n): return G(n-1) def G(n): if n < 10: return n return G(n-2) + 1 count = 0for n in range(1, 100+1): x = F(n) if x > 0: if int(x**0.5)**2 == x: count += 1print(count)