किसी गेम में दिए गए स्कोर तक पहुंचने के तरीकों की संख्या गिनें

आइए एक ऐसे खेल पर विचार करें, जिसमें एक खिलाड़ी प्रत्येक चाल में 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