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

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

Последовательность чисел задается рекуррентным соотношением:

$F (1) = 1$

$F (2) = 1$

$F (3) = 1$

$F (n) = F(n − 3) +F (n− 1)$ , при $n > 3 » class=»math» src=»/images/inform/quest/quest-4143-5.svg» width=»auto»>, где <img decoding=$ – натуральное число.

Чему равно $F(12)$ ?

В ответе запишите только натуральное число.

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

def f(n):
    if n == 1 or n == 2 or n == 3:
        return 1
    else:
        return f(n-3) + f(n-1)
print(f(12))

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

Последовательно находим:

$F (4) = F(1)+ F(3) = 2$ ,

$F (5) = F(2)+ F(4) = 3$ ,

$F (6) = F(3)+ F(5) = 4$ ,

$F (7) = F(4)+ F(6) = 6$ ,

$F (8) = F(5)+ F(7) = 9$ ,

$F (9) = F(6)+ F(8) = 13$ ,

$F (10) = F(7)+ F(9) = 19$ ,

$F (11) = F(8)+ F(10) = 28$ ,

$F (12) = F(9)+ F(11) = 41$ .

Ответ: 41