n-তম সিড়ি পৌঁছার উপায় গণনা (Count ways to reach the n-th stair)

n সংখ্যক সিড়ি রয়েছে। একজন ব্যক্তি ১ নম্বর থেকে n-তম সিড়িতে যাবে। এক ধাপে সে সর্বোচ্চ কতগুলো সিড়ি পার করতে পারে সেটিও দেওয়া আছে। এই তথ্য দিয়ে n-তম সিড়িতে পৌঁছার সম্ভাব্য উপায়ের সংখ্যা বের করতে হবে।

ধরি, এক ধাপে সর্বোচ্চ দুটি সিড়ি পার করা সম্ভব। তাহলে n-তম সিড়িতে পৌঁছার উপায়: ways(n) = ways(n-1) + ways(n-2)।

ইনপুট এবং আউটপুট

ইনপুট: সিড়ির সংখ্যা, মনে করুন ১০। এক ধাপে সর্বোচ্চ পার করা সিড়ি, মনে করুন ২।
আউটপুট: Enter number of stairs: 10
Enter max stair a person can climb: 2
Number of ways to reach: 89

এলগরিদম

stairClimbWays(stair, max)

ইনপুট: সিড়ির সংখ্যা, এক ধাপে সর্বোচ্চ সিড়ি পার করার সংখ্যা।

আউটপুট: পৌঁছার সম্ভাব্য উপায়ের সংখ্যা।

শুরু
  stair সংখ্যার সমান আকারের count অ্যারে সংজ্ঞায়িত করুন
  count[0] := 1
  count[1] := 1
  i := 2 থেকে stair-1 পর্যন্ত, করুন
    count[i] := 0
    j = 1 থেকে i এবং j <= max; করুন
      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);
}

আউটপুট

Enter number of stairs: 10
Enter max stair a person can climb: 2
Number of ways to reach: 89