n সিঁড়ি আছে। একজন ব্যক্তি প্রথম থেকে নবম সিঁড়িতে যাবেন। তিনি এক ধাপে সর্বোচ্চ কতটি সিঁড়ি পার হতে পারবেন তাও দেওয়া আছে। এই তথ্য দিয়ে, আমাদের nম সিঁড়িতে যাওয়ার সম্ভাব্য উপায় খুঁজে বের করতে হবে। আসুন বিবেচনা করা যাক প্রতিটি ধাপে একজন সর্বোচ্চ দুটি সিঁড়ি অতিক্রম করতে পারে। তাই আমরা এই সমস্যা সমাধানের জন্য পুনরাবৃত্তিমূলক সম্পর্ক খুঁজে পেতে পারি। কেউ (n-1)তম সিঁড়ি থেকে বা (n-2)তম সিঁড়ি থেকে nম সিঁড়িতে যেতে পারে। সুতরাং উপায়(n) =উপায়(n-1) + উপায়(n-2)।
ধরুন সিঁড়ির সংখ্যা, বলুন 10, সর্বোচ্চ সংখ্যক সিঁড়ি যা এক ধাপে লাফানো যায়, বলুন 2, তাহলে আউটপুট হবে 89টি সম্ভাব্য উপায়ে।
এটি সমাধান করতে, এই ধাপগুলি অনুসরণ করুন -
- সিঁড়ি সংখ্যার মতো আকারের অ্যারের সংখ্যা নির্ধারণ করুন
- গণনা[0] :=১
- এর জন্য i :=2 থেকে সিঁড়ি -1, কর
- গণনা[i] :=0 j =1 থেকে i এবং j <=সর্বোচ্চ; কর
- গণনা[i] :=গণনা[i] + গণনা[i - j]
আসুন আরও ভালভাবে বোঝার জন্য বাস্তবায়ন দেখি
উদাহরণ (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);
} ইনপুট
Stairs = 10 Max stairs a person can climb: 2
আউটপুট
Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89
