Вам нужно выложить плиткой А * 2 коридора.
Существует 2 вида плитки:
1) 1*1,
2) Г-образный
Напишите код c++ который посчитает сколько существует различных способов вымостить коридор. К примеру если А=2 тогда ответ должен быть 5.
Ответы
Відповідь:
#include <iostream>
using namespace std;
int main() {
int n, f1 = 1, f2 = 2, f3; // начальные значения
cin >> n;
if (n == 1) cout << f1; // отдельный случай для n=1
else if (n == 2) cout << f2; // отдельный случай для n=2
else {
for (int i = 3; i <= n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
cout << f3; // результат
}
return 0;
}
Пояснення:
Ответ:
Для решения данной задачи можно использовать динамическое программирование. Создадим массив dp размера A+1, где dp[i] будет хранить количество способов вымостить коридор длины i. Изначально все элементы dp установим в 0.
Для i=1 dp[i] равно 1, так как существует только один способ вымостить коридор длины 1.
Для i=2 dp[i] равно 3, так как существует три способа вымостить коридор длины 2: двумя плитками 1*1, одной плиткой Г-образной или двумя плитками Г-образными.
Для i>2 мы можем выложить первую плитку либо 11, либо Г-образную. Если мы выложили плитку 11, то оставшуюся часть коридора нужно вымостить способом, который соответствует длине i-1, то есть dp[i-1]. Если мы выложили Г-образную плитку, то оставшуюся часть коридора нужно вымостить способом, который соответствует длине i-2, то есть dp[i-2]. Таким образом, мы можем записать рекуррентную формулу:
dp[i] = dp[i-1] + dp[i-2]
Наша цель - посчитать dp[A]. Для этого нам необходимо заполнить массив dp начиная с dp[3] по формуле выше.
Вот код на C++:
#include <iostream>
using namespace std;
int main() {
int A;
cin >> A;
int dp[A+1];
dp[1] = 1;
dp[2] = 3;
for (int i = 3; i <= A; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
cout << dp[A] << endl;
return 0;
}
Объяснение:
Пример работы программы:
Input:
2
Output:
5
Input:
4
Output:
11