Задача к ЕГЭ по информатике на тему «одна функция» №1

Просмотров 8 Комментарии 0

Алгоритм вычисления значения функции $F (n)$ , где $n$ — целое неотрицательное число, задан следующими соотношениями:

$F(n ) = n$ , при $n < 3$ ;
$F (n) = F (n − 1) ⋅ F (n − 2) − F (n − 3)$ , при n > 2 » class=»math» width=»auto»>.<br class=

Чему равно значение функции $F (4)$ ?

Решение руками:

Данная в условии формула $F(n ) = F (n − 1) ⋅ F (n − 2) − F (n − 3)$ называется рекурретной. Это означает, что значение функции от некоторого аргумента зависит от значения функций от других аргументов. Так, чтобы найти значение $F (n)$ при $n > 2 » class=»math» src=»/images/inform/reshen/reshen-564-3.svg» width=»auto»>, нужно найти значение <img decoding=$ , $F (n − 2)$ и $F (n − 3)$ , а чтобы найти найти значение $F (n − 1)$ , нужно найти значение $F (n − 1 − 1 )$ , $F (n − 2 − 1)$ и $F (n − 3 − 1)$ (аналогично с поиском значения $F (n − 2)$ и $F (n − 3)$ ) и так далее (до момента, пока аргумент функции не станет меньше или равен 2, так как для таких аргументов значение функции известно из формулы из условия).

Найдем значение функции $F (4)$ :

$F(4) = F (3) ⋅ F(2) − F (1)$ ;

Нам известны значения $F (2 )$ , $F (1)$ и $F (0)$ (2, 1, 0), но неизвестно значение $F (3)$ . Найдем его:

$F(3) = F (2) ⋅ F(1) − F (0) = 2 ⋅ 1 − 0 = 2$ ;

Подставим найденные значения в $F (4)$ :

$F(4) = 2 ⋅ 2 − 1 = 3$ .

Решение программой:

def f(n):
    if n < 3:
        return n
    if n > 2:
        return f(n - 1) * f(n - 2) - f(n - 3)

print(f(4))

Получаем ответ: $3.$

Ответ: 3