একটি গেমে প্রদত্ত স্কোরে পৌঁছানোর উপায় গণনা করুন

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

গতিশীল প্রোগ্রামিং পদ্ধতির মাধ্যমে, আমরা 0 থেকে n পর্যন্ত সমস্ত স্কোরের একটি তালিকা তৈরি করব এবং 3, 5, 10 এর প্রতিটি মানের জন্য, আমরা কেবল টেবিলটি আপডেট করব।

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

Input:
The maximum score to reach using 3, 5 and 10. Let the input is 50.
Output:
Number of ways to reach using (3, 5, 10)50: 14

অ্যালগরিদম

countWays(n)

শুধুমাত্র 3টি সম্ভাব্য স্কোর আছে, সেগুলি হল 3, 5 এবং 10

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

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

Begin
   create table of size n+1
   set all table entries to 0
   table[0] := 1

   for i := 3 to n, do
      table[i] := table[i] + table[i-3]
   done

   for i := 5 to n, do
      table[i] := table[i] + table[i-5]
   done

   for i := 10 to n, do
      table[i] := table[i] + table[i-10]
   done

   return table[n]
End

উদাহরণ

#include <iostream>
using namespace std;

// Returns number of ways to reach score n
int countWay(int n) {
   int table[n+1], i;    //table to store count for each value of i

   for(int i = 0; i<=n; i++) {
      table[i] = 0;    // Initialize all table values as 0
   }

   table[0] = 1;       //set for 1 for input as 0
   for (i=3; i<=n; i++)    //try to solve using 3
      table[i] += table[i-3];

   for (i=5; i<=n; i++)    //try to solve using 5
      table[i] += table[i-5];

   for (i=10; i<=n; i++)    //try to solve using 10
      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