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

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

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

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

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

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

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

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

$F(6) = F (5) ⋅ F(3) + 2 ⋅ F(4)$ ;

$F(5) = F (4) ⋅ F(2) + 2 ⋅ F(3)$ ;

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

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

$F(4) = 2 ⋅ 1 + 2 ⋅ 2 = 2 + 4 = 6$ ;

$F(5) = 6 ⋅ 2 + 2 ⋅ 2 = 12 + 4 = 16$ ;

$F(6) = 16 ⋅ 2 + 2 ⋅ 6 = 32 + 12 = 44$ .

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

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

print(f(6))

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

Ответ: 44