nটি সিডি রয়েছে। একজন ব্যক্তি ১ নম্বর থেকে n-তম সিডি পর্যন্ত যাবে। এক ধাপে সর্বোচ্চ কতটি সিডি পার করা যাবে সেটিও দেওয়া আছে। এই তথ্য দিয়ে n-তম সিডিতে পৌঁছানোর সম্ভাব্য পথের সংখ্যা বের করতে হবে। ধরি এক ধাপে সর্বোচ্চ দুটি সিডি পার করা যায়। তখন আমরা রিকার্সিভ রিলেশন দিয়ে সমাধান করতে পারি। কেউ n-তম সিডিতে যেতে পারে (n-1)-তম সিডি থেকে বা (n-2)-তম সিডি থেকে। তাই ways(n) = ways(n-1) + ways(n-2)।
সিডির সংখ্যা যদি ১০ হয়, এক ধাপে সর্বোচ্চ ২টি সিডি পার করা যায়, তবে আউটপুট হবে ৮৯টি সম্ভাব্য পথ।
এটি সমাধানের জন্য নিচের ধাপগুলো অনুসরণ করুন −
- সিডির সংখ্যা সমান আকারের count অ্যারে ডিফাইন করুন
- count[0] := 1
- for i := 2 to stair -1, do
- count[i] := 0
- for j = 1 to i and j <= max; do
- count[i] := count[i] + count[i - j]
- return count[stair - 1]
নিচের ইমপ্লিমেন্টেশন দেখে ভালোভাবে বুঝতে পারবেন
উদাহরণ (C++)
#include<iostream> using namespace std; int stairClimbWays(int stair, int max){ int count[stair]; //নিচ থেকে উপরে ফলাফল সিডি দিয়ে পূরণ count[0] = 1; //যখন ০ বা ১টি সিডি থাকে, চড়ার ১টি পথ count[1] = 1; for (int i=2; i<stair; i++){ //সিডি ২ থেকে উপরের জন্য 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){ //ব্যক্তি ১,২,...max সিডি একসাথে চড়তে পারে 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
