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

Cho điểm số lần chạy. Mục tiêu là đạt được số điểm đó theo cách mà người đánh bóng chỉ có thể thực hiện 1 hoặc 2 lần chạy trong một đường bóng duy nhất. Hạn chế là không được thực hiện liên tiếp 2 lượt chạy. Ví dụ:để đạt được điểm số 6 đã cho, người ta có thể thực hiện các bước chạy như:1 + 2 + 1 + 2 nhưng không phải là 2 + 2 + 1 + 1 hoặc bất kỳ cách nào khác với hai số 2 liên tiếp.

Ví dụ

Đầu vào

score=4

Đầu ra

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

Giải thích

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

Đầu vào

score=5

Đầu ra

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

Giải thích

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi sẽ sử dụng một lá cờ để đánh dấu rằng điểm trước đó là hai hay không, trong trường hợp là 2, chúng tôi sẽ bao gồm điểm của lần chạy tiếp theo là 1 điểm khác 2.

• Lấy điểm biến số nguyên.

• Ban đầu hãy kiểm tra biến cờ =false.

• Hàm way_reach_score (điểm số int, kiểm tra bool) cho biết số lượng cách để xóa điểm bằng cách sử dụng 1 và 2 mà không có 2s liên tiếp.

• Lấy số lượng ban đầu là 0.

• Nếu điểm là 0, trả về 0.

• Nếu kết quả kiểm tra là sai có nghĩa là lần chạy trước đó là 1, vì vậy trong trường hợp điểm số hiện tại bằng nhau thì số cách sẽ được tính =điểm số - 1, điểm sai) + điểm số - điểm số - 2, điểm số đúng).

• Nếu không, lần chạy trước đó là 2, vì vậy lần chạy kết quả sẽ chỉ là 1, do đó các cách sẽ là cách_trách_sách (điểm - 1, sai).

• Cuối cùng, chúng ta sẽ tính được tổng số cách.

• Kết quả là số lượt trả lại.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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