Приведу пример задачи:
Из условия мы видим, что знаем только то, что при n = 1 функция F возвращает единицу. Кроме того, если n > 1, то функция вернет F(n - 1) * n. То есть функция будет вызывать сама себя до тех пор, пока n не станет равной единице. Мы можем расписать данную задачу на бумаге:
F(5) = F(4) * 5
F(4) = F(3) * 4
F(3) = F(2) * 3
F(2) = F(1) * 2
F(1) = 1
Теперь собираем снизу-вверх:
F(1) = 1
F(2) = F(1) * 2 = 1 * 2 = 2
F(3) = F(2) * 3 = 2 * 3 = 6
F(4) = F(3) * 4 = 6 * 4 = 24
F(5) = F(4) * 5 = 24 * 5 = 120
Ответ: 120
Данную номер ЕГЭ можно также решать и с помощью программирования:
def f(n):
if n == 1:
return 1
return f(n - 1) * n
print(f(5))
Обратите внимание, что перед return f(n - 1) * n не надо ставить условие n > 1, т. к. мы уже учли, что если n == 1, то возвращается 1, поэтому уже только при n > 1 это будет выполняться. Но если вы сделаете, например, так:
def f(n):
if n == 1:
return 1
if n > 1:
return f(n - 1) * n
print(f(5))
То есть если напишете данное условие, то это не будет ошибкой и ответ будет тот же.
Вы можете подумать, что зачем нам писать код если легче расписать все на бумаге. В данной задаче, возможно, вы правы, но бывают функции, где надо возвращать длинную строчку и вы можете ошибиться в расчетах.
Распишем 1 способом:
F(5) = F(4) * 5 + F(3) * 4
F(4) = F(3) * 4 + F(2) * 3
F(3) = F(2) * 3 + F(1) * 2
А теперь обратно:
F(3) = 3 * 3 + 1 * 2 = 11
F(4) = 11 * 4 + 9 = 53
F(5) = 53 * 5 + 11 * 4 = 309
Ответ: 309
Как мы видим, не так уж и трудно все расписать и посчитать, но можно где-то все таки запутаться, ведь мы люди. Поэтому я предпочитаю решать данные задачи кодом.
def f(n):
if n == 1:
return 1
if n == 2:
return 3
return f(n - 1) * n + f(n - 2) * (n - 1)
print(f(5))
Решим что-то посложнее:
Данную задачу я покажу как решать только кодом, но вы можете решать как вам удобнее.
def f(n):
if n == 1:
return 1
return 2 * g(n - 1) + 5 * n
def g(n):
if n == 1:
return 1
return f(n - 1) + 2 * n
print(f(4) + g(4))
Ответ: 89
Тут уже понадобиться ввести 2 функцию g(n), но это не сильно затрудняет задачу.
А вот еще интересная задача:
def f(n):
if n == 1:
return 1
if n % 2 == 0:
return n + f(n - 1)
return 2 * f(n - 2)
print(f(26))
Ответ: 4122
Стоит отметить, что n является четным если его остаток от деления (% в python) равен нулю, иначе он будет равняться единице.
На это все, но я хотел бы, чтобы вы сами порешали задачи, которые я скину ниже.
Задача 1:
Решение:
def f(n):
if n == 0:
return 5
if n > 0:
return 3 * f(n - 4)
return f(n + 3)
print(f(43))
Ответ: 7971615
Задача 2:
Решение:
def f(n):
if n < 5:
return 5 - n
if n % 3 == 0:
return 4 * (n - 5) * f(n - 5)
return 3 * n + 2 * f(n - 1) + f(n - 2)
print(f(20))
Ответ: 1343116
Задача 3 (самая трудная):
Решение:
def f(n):
if n == 0:
return 0
if n % 3 == 0:
return n + f(n - 3)
return n + f(n - (n % 3))
print(f(22))
Ответ: 106