เราได้รับจำนวนขั้นทั้งหมดในบันไดคือ n บุคคลสามารถไปถึงชั้นถัดไปโดยข้าม 1, 2 หรือ 3 ขั้นในคราวเดียว เป้าหมายคือหาจำนวนวิธีที่ชั้นถัดไปสามารถไปถึงได้โดยการทำเช่นนั้น
เราจะใช้วิธีแบบเรียกซ้ำโดยคำนึงถึงว่าเพื่อไปถึงขั้นที่ i บุคคลต้องกระโดดจากขั้น 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
คำอธิบาย
มีทั้งหมด 3 ขั้น กระโดดจากจุดเริ่มต้น (ข้าม 3): 3 ขั้น กระโดดจากขั้นที่ 1 (ข้าม 2): 1+2 กระโดดจากขั้นที่ 2 (ข้าม 1): 2+1 ไม่ข้าม 1+1+1
อินพุต
N=6 steps
เอาต์พุต
Count of ways to reach the nth stair using step 1, 2 or 3 are: 24
คำอธิบาย
มีทั้งหมด 6 ขั้น วิธี: 1+1+1+1+1+1, 2+1+1+1+1, 3+1+1+1, 3+1+2, 3+2+1, 3+3 และอื่นๆ
วิธีการที่ใช้ในโปรแกรมด้านล่าง
เราใช้ตัวแปรจำนวนเต็ม steps เป็นจำนวนขั้นทั้งหมด
ฟังก์ชัน stairs_step(int steps) รับทุกขั้นเป็นอินพุตและคืนค่าจำนวนวิธีไปถึงชั้นถัดไปโดยการกระโดดหรือไม่
ใช้ตัวแปรชั่วคราว count เป็น 0 สำหรับวิธีการดังกล่าว
ถ้าตัวเลขเป็น 0 คืนค่า 1
ถ้าจำนวนขั้นเป็น 1 มีเพียง 1 วิธี
ถ้าจำนวนขั้นเป็น 2 มีเพียง 2 วิธี (1+1 หรือ 2)
มิฉะนั้น วิธี = stairs_step(step-3) + stair_step(step-2) + stair_step(step-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
