গেমে নির্দিষ্ট স্কোর পৌঁছানোর উপায় গণনা (Count ways to reach a given score in a game)

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

ডাইনামিক প্রোগ্রামিং পদ্ধতিতে, আমরা ০ থেকে n পর্যন্ত সব স্কোরের একটি টেবিল তৈরি করব, এবং ৩, ৫, ১০ এর প্রতিটি মানের জন্য সিম্পলি টেবিল আপডেট করব।

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

ইনপুট: ৩, ৫ এবং ১০ দিয়ে পৌঁছাতে সর্বোচ্চ স্কোর। ধরি ইনপুট ৫০।
আউটপুট: Number of ways to reach using (3, 5, 10) 50: 14

এলগরিদম

countWays(n)

এখানে শুধু ৩টি সম্ভাব্য স্কোর রয়েছে: ৩, ৫ এবং ১০।

ইনপুট: n হলো পৌঁছাতে হবে সর্বোচ্চ স্কোর।

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

শুরু
  n+1 আকারের একটি টেবিল তৈরি করুন
  সব টেবিল এন্ট্রিকে ০ সেট করুন
  table[0] := 1
  i := 3 থেকে n পর্যন্ত, করুন
    table[i] := table[i] + table[i-3]
  শেষ লুপ
  i := 5 থেকে n পর্যন্ত, করুন
    table[i] := table[i] + table[i-5]
  শেষ লুপ
  i := 10 থেকে n পর্যন্ত, করুন
    table[i] := table[i] + table[i-10]
  শেষ লুপ
  return table[n]
শেষ

উদাহরণ (C++ কোড)

#include <iostream>
using namespace std;

// স্কোর n-এ পৌঁছানোর উপায়ের সংখ্যা ফেরত দেয়
int countWay(int n) {
  int table[n+1], i;
  // প্রতিটি i মানের জন্য কাউন্ট স্টোর করার টেবিল
  for(int i = 0; i <= n; i++) {
    table[i] = 0;  // সব টেবিল ভ্যালু ০ আরম্ভ করুন
  }
  table[0] = 1;  // ইনপুট ০ হলে ১ সেট করুন
  for (i = 3; i <= n; i++)  // ৩ দিয়ে সমাধান করার চেষ্টা
    table[i] += table[i-3];
  for (i = 5; i <= n; i++)  // ৫ দিয়ে সমাধান করার চেষ্টা
    table[i] += table[i-5];
  for (i = 10; i <= n; i++)  // ১০ দিয়ে সমাধান করার চেষ্টা
    table[i] += table[i-10];
  return table[n];
}

int main() {
  int n;
  cout << "Enter max score: "; cin >> n;
  cout << "Number of ways to reach using (3, 5, 10)" << n << ": " << countWay(n);
}

আউটপুট

Enter max score: 50
Number of ways to reach using (3, 5, 10)50: 14