Có n cầu thang. Một người sẽ đi từ cầu thang thứ nhất đến thứ n. Tối đa bao nhiêu cầu thang mà anh ấy / cô ấy có thể băng qua trong một bước cũng được đưa ra. Với thông tin này, chúng ta phải tìm cách khả thi để đi đến cầu thang thứ n. Chúng ta hãy xem xét một người có thể băng qua tối đa hai cầu thang trong mỗi bước. Vì vậy, chúng ta có thể tìm quan hệ đệ quy để giải quyết vấn đề này. Người ta có thể di chuyển đến cầu thang thứ n, từ (n-1) cầu thang hoặc từ (n-2) cầu thang. Vì vậy, cách (n) =cách (n-1) + cách (n-2).
Giả sử số cầu thang, chẳng hạn là 10, số cầu thang tối đa có thể nhảy trong một bước, giả sử là 2, thì kết quả sẽ là 89 cách khả thi.
Để giải quyết vấn đề này, hãy làm theo các bước sau -
- xác định số lượng mảng có kích thước giống như số cầu thang
- số lượng [0]:=1
- đối với i:=2 đến bậc thang -1, thực hiện
- count [i]:=0
- for j =1 to i and j <=max; làm
- count [i]:=count [i] + count [i - j]
- số lượt trả về [cầu thang - 1]
Hãy cho chúng tôi xem việc triển khai để hiểu rõ hơn
Ví dụ (C ++)
#include<iostream>
using namespace std;
int stairClimbWays(int stair, int max){
int count[stair]; //fill the result stair using bottom up manner
count[0] = 1; //when there are 0 or 1 stair, 1 way to climb
count[1] = 1;
for (int i=2; i<stair; i++){ //for stair 2 to higher
count[i] = 0;
for(int j=1; j<=max && j<=i; j++)
count[i] += count[i-j];
}
return count[stair-1];
}
int countWays(int stair, int max){ //person can climb 1,2,...max stairs at a time
return stairClimbWays(stair+1, max);
}
int main (){
int stair, max;
cout << "Enter number of stairs: "; cin >> stair;
cout << "Enter max stair a person can climb: "; cin >> max;
cout << "Number of ways to reach: " << countWays(stair, max);
} Đầu vào
Stairs = 10 Max stairs a person can climb: 2
Đầu ra
Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89