Đếm số cách đạt điểm dùng 1 và 2 không có 2 liên tiếp trong C++

Cho một điểm số. Mục tiêu là đạt được điểm số đó theo cách mà tay côn trộn có thể lấy 1 hoặc 2 điểm trong một quả bóng. Hạn chế là không được lấy 2 điểm liên tiếp. Ví dụ, để đạt điểm 6, có thể lấy điểm như: 1+2+1+2 nhưng không được 2+2+1+1 hoặc bất kỳ cách nào có hai số 2 liên tiếp.

Ví dụ

Đầu vào

score=4

Đầu ra

Số cách đạt điểm dùng 1 và 2 không có 2 liên tiếp là: 4

Giải thích

Các cách đạt điểm 4: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1

Đầu vào

score=5

Đầu ra

Số cách đạt điểm dùng 1 và 2 không có 2 liên tiếp là: 6

Giải thích

Các cách đạt điểm 5: 1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+1+2

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ sử dụng một cờ check để đánh dấu rằng điểm trước đó là 2 hay không, trong trường hợp nó là 2, chúng ta sẽ đạt điểm với điểm tiếp theo là 1, ngược lại là 2.

• Nhận biến nguyên score.
• Lấy biến cờ check = false ban đầu.
• Hàm ways_reach_score(int score, bool check) cho biết số cách đạt điểm dùng 1 và 2 không có 2 liên tiếp.
• Khởi tạo biến đếm ban đầu là 0.
• Nếu điểm là 0 trả về 1 (cách rỗng).
• Nếu check là false nghĩa là điểm trước là 1, nên nếu điểm hiện tại lớn hơn thì số cách sẽ là count = ways_reach_score(score-1, false) + ways_reach_score(score-2, true).
• Ngược lại điểm trước là 2, nên điểm tiếp theo sẽ chỉ là 1 nên số cách sẽ là ways_reach_score(score-1, false).
• Cuối cùng, chúng ta sẽ nhận được tổng số cách trong biến đếm.
• Trả về biến đếm làm kết quả.

Ví dụ mã

#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 << "Số cách đạt điểm dùng 1 và 2 không có 2 liên tiếp là: " << ways_reach_score(score, check);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số cách đạt điểm dùng 1 và 2 không có 2 liên tiếp là: 4