จำนวนวิธีทาสีบันได 2 สี ให้ขั้นติดกันไม่เป็นสีเหลืองใน C++

เราได้รับบันได n ขั้น และ 2 สี (แดงและเหลือง) ที่จะใช้ทาบันไดเหล่านี้ งานของเราคือนับจำนวนวิธีที่เราสามารถทาสีบันไดได้ โดยที่ไม่มีสองขั้นติดกันที่เป็นสีเหลือง

ตัวอย่าง

อินพุต

3

เอาต์พุต

5

คำอธิบาย

วิธีที่บันไดสามารถทาสีได้คือ YRY, RYR, YRR, RRY, RRR
ที่นี่ R แทนสีแดง, Y แทนสีเหลือง

เพื่อแก้ปัญหานี้ ลองดูจำนวนวิธีที่บันไดสามารถทาสีได้:

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

จากกรณีเหล่านี้ เราสามารถสรุปได้ว่า นี่คือ ลำดับฟีบอนัชชี (Fibonacci Series) เริ่มต้นด้วย 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