Відповідь:

#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