นับวิธีเพื่อให้ได้คะแนนโดยใช้ 1 และ 2 โดยไม่มี 2s ติดต่อกันใน C++

ให้คะแนนการวิ่ง เป้าหมายคือการทำคะแนนให้ได้ในลักษณะที่ผู้ตีสามารถวิ่ง 1 หรือ 2 วิ่งในบอลเดียว ข้อจำกัดคือไม่สามารถวิ่ง 2 รอบติดต่อกันได้ ตัวอย่างเช่น หากต้องการได้คะแนน 6 เราสามารถวิ่งได้ เช่น 1+2+1+2 แต่ไม่ใช่ 2+2+1+1 หรือวิธีอื่นใดที่มี 2 แต้มติดต่อกัน 2 ครั้ง

ตัวอย่าง

อินพุต

score=4

ผลลัพธ์

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

คำอธิบาย

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

อินพุต

score=5

ผลลัพธ์

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

คำอธิบาย

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

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราจะใช้แฟล็กเพื่อทำเครื่องหมายว่าคะแนนก่อนหน้านี้เป็น 2 หรือไม่ ในกรณีที่เป็น 2 เราจะครอบคลุมคะแนนด้วยการวิ่งครั้งต่อไปเป็นคะแนนอื่น 2

• ใช้คะแนนตัวแปรจำนวนเต็ม

• ตรวจสอบตัวแปรแฟล็ก =false เริ่มแรก

• ฟังก์ชัน way_reach_score(int score, bool check) บอกจำนวนวิธีที่จะไปถึงคะแนนโดยใช้ 1 และ 2 โดยไม่มี 2 วินาทีติดต่อกัน

• นับเริ่มต้นเป็น 0

• หากคะแนนเป็น 0 ให้คืน 0

• หากการตรวจสอบเป็นเท็จหมายถึงการเรียกใช้ครั้งก่อนเป็น 1 ดังนั้นในกรณีที่คะแนนปัจจุบันมากกว่า วิธีจะถูกนับ =ways_reach_score(คะแนน − 1, เท็จ) +ways_reach_score(คะแนน − 2 จริง)

• มิฉะนั้น การรันครั้งก่อนคือ 2 ดังนั้นการรันที่ตามมาจะเป็น 1 เท่านั้น ดังนั้นวิธีจะเป็น way_reach_score(score − 1, false)

• ในตอนท้ายเราจะได้วิธีนับทั้งหมด

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

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

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

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