นับวิธีไปถึงบันไดที่ n โดยใช้ขั้นตอนที่ 1, 2 หรือ 3 ใน C++

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

เราจะใช้วิธีเรียกซ้ำโดยจำไว้ว่าการจะไปถึงขั้น i'th ใด ๆ บุคคลต้องกระโดดจากขั้นที่ i-1 (ข้ามไป 1 ขั้นตอน) , ขั้นตอนที่ i-2 (ข้าม 2 ขั้นตอน ) หรือขั้นตอนที่ i-3 ( ข้าม 3 ขั้นตอน )

มาทำความเข้าใจกับตัวอย่างกัน

ป้อนข้อมูล

N=3 steps

ผลผลิต

Count of ways to reach the nth stair using step 1, 2 or 3 are: 4

คำอธิบาย

There are total 3 steps
Jump from start ( skip 3 ) : 3 step
Jump from 1’st step (skip 2): 1+2
Jump from 2nd step (skip 1): 2+1
No skip 1+1+1

ป้อนข้อมูล

N=6 steps

ผลผลิต

Count of ways to reach the nth stair using step 1, 2 or 3 are: 24

คำอธิบาย

There are total 6 steps
Ways: 1+1+1+1+1+1, 2+1+1+1+1, 3+1+1+1, 3+1+2, 3+2+1, 3+3 and so on.

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

• เรากำลังดำเนินการขั้นตอนจำนวนเต็มเป็นจำนวนขั้นตอนทั้งหมด

• ฟังก์ชันบันได_step(int step) ใช้ทุกขั้นตอนเป็นอินพุต และส่งคืนหลายวิธีในการไปถึงชั้นถัดไปด้วยการกระโดดหรือไม่..

• ใช้ตัวแปรเริ่มต้นนับเป็น 0 สำหรับวิธีดังกล่าว

• หากตัวเลขเป็น 0 ให้คืนค่า 1

• หากนับก้าว 1 ทางเท่านั้น

• หากนับก้าวเป็น 2 วิธีเท่านั้น ( 1+1 หรือ 2 )

• วิธีอื่น =บันได_step (ขั้นตอนที่ 3)+บันได_ขั้นตอน(ขั้นตอนที่-2)+บันได_ขั้นตอน(ขั้นตอนที่-1)

(วิธีเรียกซ้ำ)

ตัวอย่าง

#include <iostream>
using namespace std;
int stairs_step(int steps){
   if(steps == 0){
      return 1;
   }
   else if(steps == 1){
      return 1;
   }
   else if (steps == 2){
      return 2;
   }
   else{
      return stairs_step(steps - 3) + stairs_step(steps - 2) + stairs_step(steps - 1);
   }
}
int main(){
   int steps = 5;
   cout<<"Count of ways to reach the nth stair using step 1, 2 or 3 are: "<<stairs_step(steps);
   return 0;
}

ผลลัพธ์

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

Count of ways to reach the nth stair using step 1, 2 or 3 are: 13