30 ! мистер фокс хочет замостить дорожку от своего дома до дома мистера форда. дорожка имеет вид прямоугольника 2×11, а у мистера фокса есть 11 одинаковых плиток 1×2, которые можно поворачивать. осталось только выбрать, как положить плитки. из скольки замощения можно выбирать мистеру фоксу? например, дорожку 2x3 можно замостить тремя выведите в ответе одно натуральное число.

Пусть F(n) - число замостить дорожку 2xn. Тогда F(1) = 1, F(2) = 2.
Если n > 2, то можно либо положить с краю одну плитку вертикально, и заполнять осташуюся часть форожки 2x(n - 1), или положить две горизонтально и заполнять 2x(n - 2). Первое можно выполнить второе Поэтому F(n) = F(n - 1) + F(n - 2).
Получилось определение чисел Фибоначчи, F(n) - n- ое число Фибоначчи, F(n) = Fib(n).

ответ. F(11) = Fib(11) = 144.