เราได้บันได n ขั้นและ 2 สี (สีแดงและสีเหลือง) ที่จะทาสีบันไดเหล่านี้ งานของเราคือการนับจำนวนวิธีที่เราสามารถทาสีบันไดได้ เพื่อไม่ให้บันไดสองขั้นติดต่อกันเป็นสีเหลือง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
3
ผลลัพธ์
5
คำอธิบาย
The ways in which stairs can be painted are YRY, RYR, YRR, RRY, RRR. here R denotes red color, Y denotes yellow color.
ในการแก้ปัญหานี้ เรามาดูวิธีทาสีบันไดกัน
N =1 วิธี(1) =2 :R, Y
N =2 วิธี(2) =3 :RY, YR, RR
N =3 วิธี (3) =5 :RYR, YRY, RRY, YRR, RRR
N =4 วิธี (4) =8 :YRYR, RYRY, RYRR, YRRY, YRRR, RRYR, RRRR, RRRY
จากกรณีเหล่านี้ เราสามารถสรุปได้ว่านี่คืออนุกรมฟีโบนักชีที่เริ่มต้นด้วย 2 เป็นองค์ประกอบแรกและ 3 เป็นองค์ประกอบที่สอง
โปรแกรมแสดงการทำงานของตรรกะของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
Number of ways to color 6 steps is 21
