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

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

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

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

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

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

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

Нам даны значения $F(0)$ , $F (1)$ и $F (2)$ . Найдем значение функции $F (7 )$ :

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

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

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

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

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

$F(7) = 8 + 2 ⋅ 7 = 8 + 14 = 22$ .

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

def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 2
    elif n == 2:
        return 3
    elif n > 2:
        return f(n - 2) + 2 * f(n - 3)

print(f(7))

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

Ответ: 22