Finding the number of ways to reach a given score in a game
Select Articles
Finding the number of ways to reach a given score in a game
Program to find the number of ways to reach a given score in a game is discussed here. Consider a game where a player can score 1 or 2 or 5 points in a move. Given a total score n, find the total number of ways to reach the given score.
Example 1:
cost = 19
Points per move = 2, 7, 10
Number of ways = 2
(2, 7, 10)
(2, 2, 2, 2, 2, 2 , 7)
Example 2:
cost = 15
Points per move =5, 10
Number of ways = 2
(5, 5, 5)
(5, 10)
Algorithm to find the number of ways to reach a given score in a game
Input the total score.
Input the points per move in an array.
The idea is to create an array of size n+1 and store counts of all scores from 0 to n.
For every possible move, increment values in the array.
Program to find the number of ways to reach a given score in a game
C
/* C program to find the number of ways to reach a given score in a game */
#include
int count_number_of_ways(int n, int points[], int tot)
{
int arr[n + 1], i, j;
for(j = 0; j < n>
arr[j] = 0;
arr[0] = 1;
while(tot--)
{
for (i = points[tot]; i <= n; i++)
arr[i] += arr[i - points[tot]];
}
return arr[n];
}
int main()
{
int n, tot;
printf("Enter the score : ");
scanf("%d", &n);
printf("Enter the total number of points : ");
scanf("%d", &tot);
int points[tot];
printf("Enter the points per move : ");
int i;
for(i = 0; i < tot>
{
scanf("%d", &points[i]);
}
printf("Number of ways to get the score %d is %d",n, count_number_of_ways(n, points, tot));
return 0;
}
C++
/* C++ program to find the number of ways to reach a given score in a game */
#include
using namespace std;
int count_number_of_ways(int n, int points[], int tot)
{
int arr[n + 1], i, j;
for(j = 0; j < n>
arr[j] = 0;
arr[0] = 1;
while(tot–)
{
for (i = points[tot]; i <= n; i++)
arr[i] += arr[i – points[tot]];
}
return arr[n];
}
int main()
{
int n, tot;
cout << “nEnter the score : “;
cin >> n;
cout << “nEnter the total number of points : “;
cin >> tot;
int points[tot];
cout << “nEnter the points per move : “;
int i;
for(i = 0; i < tot>
{
cin >> points[i];
}
cout << “nNumber of ways to get the score ” << n>
return 0;
}
JAVA 8
/* Java program to find the number of ways to reach a given score in a game */
import java.util.*;
public class Main
{
static int count_number_of_ways(int n, int points[], int tot)
{
int[] arr = new int[n + 1];
int i, j;
for(j = 0; j < n>
arr[j] = 0;
arr[0] = 1;
while(tot– > 0)
{
for (i = points[tot]; i <= n; i++)
arr[i] += arr[i – points[tot]];
}
return arr[n];
}
public static void main(String[] args)
{
int n, tot;
Scanner sc = new Scanner(System.in);
System.out.print(“nEnter the score : “);
n = sc.nextInt();
System.out.print(“nEnter the total number of points available : “);
tot = sc.nextInt();
int[] points = new int [tot];
System.out.print(“nEnter the points per move : “);
int i;
for(i = 0; i < tot>
{
points[i] = sc.nextInt();
}
System.out.print(“nNumber of ways to get the score ” + n + ” is ” + count_number_of_ways(n, points, tot));
}
}
PYTHON 3
# Python program to find the number of ways to reach a given score in a game
def count_number_of_ways(n):
arr = [0 for i in range(n+1)]
arr[0] = 1
for i in range(3, n+1):
arr[i] += arr[i-3]
for i in range(5, n+1):
arr[i] += arr[i-5]
for i in range(10, n+1):
arr[i] += arr[i-10]
return arr[n]
n = 30
print(‘Number of ways to score’, n, ‘is’, count_number_of_ways(n))
OUTPUT
Enter the score : 19
Enter the total number of points : 3
Enter the points per move : 2 5 7
Number of ways to get the score 19 is 5
Write a public review