นับวิธีทำคะแนนด้วย 1 และ 2 ไม่มี 2 ติดกันด้วย C++

ได้รับคะแนน (score) เป้าหมายคือทำคะแนนให้ได้ตามเป้าหมาย โดยนักตีสามารถทำได้ 1 หรือ 2 คะแนนต่อลูกเท่านั้น ข้อจำกัดคือไม่สามารถทำ 2 คะแนนติดกันได้ ตัวอย่างเช่น เพื่อทำคะแนน 6 สามารถทำได้แบบ: 1+2+1+2 แต่ไม่สามารถทำ 2+2+1+1 หรือแบบอื่นที่มี 2 ติดกันได้

ตัวอย่าง

Input

score=4

Output

Count of ways to reach a score using 1 and 2 with no consecutive 2s are: 4

Explanation

The ways in which we can reach the score 4 in following ways: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1

Input

score=5

Output

Count of ways to reach a score using 1 and 2 with no consecutive 2s are: 6

Explanation

The ways in which we can reach the score 6 in following ways: 1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+1+2

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ใช้ตัวแปร flag (check) เพื่อบอกว่าคะแนนก่อนหน้าเป็น 2 หรือไม่ ถ้าเป็น 2 คะแนนถัดไปต้องเป็น 1 มิฉะนั้นเป็น 2 ได้

รับตัวแปรจำนวนเต็ม score
ตัวแปร flag check = false เริ่มต้น
ฟังก์ชัน ways_reach_score(int score, bool check) คืนค่าจำนวนวิธีทำคะแนน
กำหนดจำนวนนับเริ่มต้นเป็น 0
ถ้า score เป็น 0 คืนค่า 0
ถ้า check == false (คะแนนก่อนหน้าเป็น 1) และ score > 1: count = ways_reach_score(score-1, false) + ways_reach_score(score-2, true)
มิฉะนั้น (คะแนนก่อนหน้าเป็น 2) คะแนนต่อไปต้องเป็น 1 เท่านั้น: ways_reach_score(score-1, false)
คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int ways_reach_score(int score, bool check){
    int count = 0;
    if (score == 0){
        return 1;
    }
    if (check == false && score > 1){
        count += ways_reach_score(score - 1, false) + ways_reach_score(score - 2, true);
    } else {
        count += ways_reach_score(score - 1, false);
    }
    return count;
}

int main(){
    int score = 4;
    bool check = false;
    cout << "Count of ways to reach a score using 1 and 2 with no consecutive 2s are: " << ways_reach_score(score, check);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of ways to reach a score using 1 and 2 with no consecutive 2s are: 4