Количество вариантов расстановки клеток
В зоомагазине нужно расставить в один ряд клетки с кошками и собаками. В ряд помещается N клеток, при этом есть одно ограничение: нельзя ставить подряд три клетки с животными одного вида (иначе они передерутся). Предполагается, что в магазине есть неограниченное количество клеток с кошками и собаками. Определите, сколькими безопасными способами можно расставить N клеток в ряд.
Входные данные Входная строка содержит одно натуральное число – количество клеток в ряду N .
Выходные данные Программа должна вывести количество безопасных способов расстановки N клеток в ряд.
Примеры входные данные 5 выходные данные 16
Ответы (1 шт):
Для двух клеток возможны следующие варианты: СС, СК, КС, КК, придадим им индексы 0..3
Для следующей клетки вариант, оканчиваюшийся на СС, возможен только, если собаку добавить к варианту КС. Вариант, оканчиваюшийся на СК, возможен только, если кошку добавить к варианту СС или КС. Вариант, оканчиваюшийся на КС, возможен только, если собаку добавить к варианту СК или КК. Вариант, оканчиваюшийся на КК, возможен только, если кошку добавить к варианту СК.
Получаем соотношения для i от 3 до N
LL[i][0] = LL[i-1][2]
LL[i][1] = LL[i-1][0]+LL[i-1][2]
LL[i][2] = LL[i-1][1]+LL[i-1][3]
LL[i][3] = LL[i-1][1]
И в конце считаем результат - сумму LL[N] как LL[N][0]+LL[N][1]+LL[N][2]+LL[N][3]
Внимательно всматриваемся в результаты для разных N: 4 6 10 16 26 42 68 110... и видим удвоенные числа Фибоначчи
Result(N) = 2*Fib[N-1]
что позволяет ещё упростить решение и даже решить задачу для довольно больших N
#include <iostream>
using namespace std;
int main() {
int N=5;
long long Old = 0;
long long Fib = 1;
long long Temp;
for (int i = 0; i < N; i++) {
Temp = Fib;
Fib += Old;
Old = Temp;
}
std::cout << 2*Fib;
return 0;
}