Chúng ta được cho n bậc cầu thang và 2 màu (đỏ và vàng) để tô các bậc này. Nhiệm vụ là đếm số cách tô cầu thang sao cho không có hai bậc liên tiếp nào được tô màu vàng.
Hãy xem ví dụ để hiểu bài toán,
Đầu vào
3
Đầu ra
5
Giải thích
Các cách tô cầu thang là YRY, RYR, YRR, RRY, RRR. Ở đây R là màu đỏ, Y là màu vàng.
Để giải bài toán này, hãy xem số cách tô cầu thang.
N = 1, ways(1) = 2 : R, Y
N = 2, ways(2) = 3 : RY, YR, RR
N = 3, ways(3) = 5 : RYR, YRY, RRY, YRR, RRR
N = 4, ways(4) = 8 : YRYR, RYRY, RYRR, YRRY, YRRR, RRYR, RRRR, RRRY.
Vì vậy từ các trường hợp này, chúng ta có thể suy ra đây là dãy Fibonacci bắt đầu với 2 là phần tử đầu và 3 là phần tử thứ hai.
Chương trình minh họa logic của chúng ta,
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<<"Số cách tô màu "<<n<<" bậc là "<<colorSteps(n); return 0; }Đầu ra
Số cách tô màu 6 bậc là 21