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