นับวิธีไปถึงบันไดที่ n

มีบันได n ขั้น คนหนึ่งจะไปที่บันไดที่ 1 กำหนดจำนวนบันไดสูงสุดที่เขา/เธอสามารถข้ามได้ในขั้นตอนเดียว จากข้อมูลนี้ เราต้องหาวิธีที่เป็นไปได้ในการขึ้นบันไดที่ n'

ให้เราพิจารณาว่าแต่ละขั้นสามารถข้ามบันไดได้สูงสุดสองขั้น ดังนั้นเราจึงสามารถหาความสัมพันธ์แบบเรียกซ้ำเพื่อแก้ปัญหานี้ได้ หนึ่งสามารถย้ายไปที่บันไดที่ n ไม่ว่าจะจากบันไดที่ (n-1) หรือจากบันไดที่ (n-2) ดังนั้น วิธี(n) =วิธี(n-1) + วิธี(n-2)

อินพุตและเอาต์พุต

Input:จำนวนบันได พูด 10 จำนวนขั้นสูงสุดของขั้นที่สามารถกระโดดได้ 2 ขั้น พูดว่า 2Output:ป้อนจำนวนบันได:10ป้อนบันไดสูงสุดที่บุคคลสามารถปีนได้:2จำนวนวิธีที่จะไปถึง:89 
อัลกอริทึม
 
stairClimpWays(บันได สูงสุด)
 

 อินพุต -  จำนวนบันได กระโดดบันไดสูงสุดในขั้นตอนเดียว
 

 ผลลัพธ์ − จำนวนช่องทางที่เป็นไปได้
 
เริ่มกำหนดจำนวนอาร์เรย์ที่มีขนาดเท่ากับจำนวนขั้นบันได count[0] :=1 count[0] :=1 for i :=2 to stair -1, do count[i] :=0 for j =1 to ผมและเจ <=สูงสุด; นับ[i] :=นับ[i] + นับ[i - j] เสร็จแล้ว นับกลับแล้ว[บันได - 1]สิ้นสุด
 
ตัวอย่าง
 
#includeใช้เนมสเปซ std;int stairClimbWays (int stair, int max) { จำนวน int [บันได]; //เติมบันไดผลลัพธ์โดยใช้การนับลักษณะจากล่างขึ้นบน[0] =1; //เมื่อมีบันได 0 หรือ 1 ขั้น ให้ปีน 1 ทาง นับ[1] =1; สำหรับ (int i=2; i> บันได; cout <<"ใส่บันไดสูงสุดที่บุคคลสามารถปีนได้:"; ซิน>> สูงสุด; cout <<"จำนวนวิธีที่จะไปถึง:" < 
ผลลัพธ์
 
ป้อนจำนวนบันได:10ใส่บันไดสูงสุดที่บุคคลสามารถปีนได้:2จำนวนวิธีที่จะไปถึง:89