30 БАЛЛОВ!!!!! Мистер Фокс хочет замостить дорожку от своего дома до дома Мистера Форда. Дорожка имеет вид прямоугольника 2×11, а у Мистера Фокса есть 11 одинаковых плиток 1×2, которые можно поворачивать. Осталось только выбрат...

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 - 1) способами, второе F(n - 2) способами. Поэтому F(n) = F(n - 1) + F(n - 2). Получилось определение чисел Фибоначчи, F(n) - n- ое число Фибоначчи, F(n) = Fib(n). Ответ. F(11) = Fib(11) = 144.
Не нашли ответ?
Ответить на вопрос
Похожие вопросы