Cách sơn cầu thang với hai màu sao cho hai màu liền nhau không bị ố vàng trong C ++

Chúng tôi được cung cấp n cầu thang và 2 màu (đỏ và vàng) mà những cầu thang này sẽ được sơn. Nhiệm vụ của chúng ta là đếm số cách chúng ta có thể sơn cầu thang sao cho không có hai bậc thang liên tiếp nào có màu vàng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

3

Đầu ra

5

Giải thích

The ways in which stairs can be painted are YRY, RYR, YRR, RRY, RRR. here R denotes red color, Y denotes yellow color.

Để giải quyết vấn đề này, hãy xem số cách có thể sơn cầu thang.

N =1, cách (1) =2:R, Y

N =2, cách (2) =3:RY, YR, RR

N =3, cách (3) =5:RYR, YRY, RRY, YRR, RRR

N =4, cách (4) =8:YRYR, RYRY, RYRR, YRRY, YRRR, RRYR, RRRR, RRRY.

Vì vậy, từ những trường hợp này, chúng ta có thể suy ra rằng đây là Chuỗi Fibonacci bắt đầu với 2 là phần tử đầu tiên và 3 là phần tử thứ hai.

Chương trình minh họa hoạt động của logic của chúng tôi,

Ví dụ

#include <iostream>
using namespace std;
int colorSteps(int n) {
   int first = 2;
   int next = 3;
   for (int i = 3; i <= n; i++) {
      next = first + next;
      first = next - first;
   }
   return next;
}
int main(){
   int n = 6;
   cout<<"Number of ways to color "<<n<<" steps is "<<colorSteps(n);
   return 0;
}

Đầu ra

Number of ways to color 6 steps is 21