Рубрики

Подсчитайте количество способов достичь заданного результата в игре

Рассмотрим игру, в которой игрок может набрать 3, 5 или 10 очков за ход. По заданному общему количеству баллов n найдите количество способов достижения заданного балла.

Примеры:

Input: n = 20
Output: 4
There are following 4 ways to reach 20
(10, 10)
(5, 5, 10)
(5, 5, 5, 5)
(3, 3, 3, 3, 3, 5)

Input: n = 13
Output: 2
There are following 2 ways to reach 13
(3, 5, 5)
(3, 10)

Эта проблема является вариацией проблемы смены монет и может быть решена за O (n) время и O (n) вспомогательное пространство.

Идея состоит в том, чтобы создать таблицу размером n + 1 для хранения количества всех баллов от 0 до n. Для каждого возможного хода (3, 5 и 10) увеличивайте значения в таблице.

C ++

// Программа на C ++ для подсчета количества
// возможные пути к данной оценке
// может быть достигнуто в игре, где
// ход может заработать 3, 5 или 10
#include <iostream>

using namespace std;

  
// Возвращает количество способов
// чтобы набрать n баллов

int count(int n)

{

    // таблица [i] будет хранить количество

    // решений для значения i.

    int table[n + 1], i;

  

    // Инициализируем всю таблицу

    // значения как 0

    for(int j = 0; j < n + 1; j++)

            table[j] = 0;

  

    // Базовый случай (если задано значение 0)

    table[0] = 1;

  

    // Один за другим рассмотрим 3 хода

    // и обновляем значения таблицы [] после

    // индекс больше или равен

    // значение выбранного хода

    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(void)

{

    int n = 20;

    cout << "Count for " << n 

         << " is " << count(n) << endl;

  

    n = 13;

    cout <<"Count for "<< n<< " is " 

         << count(n) << endl;

    return 0;

}

  
// Этот код добавлен
// от Shivi_Aggarwal

С

// AC программа для подсчета количества возможных путей к заданному баллу
// может быть достигнуто в игре, где ход может заработать 3, 5 или 10
#include <stdio.h>

  
// Возвращает количество способов получить оценку n

int count(int n)

{

    // таблица [i] будет хранить количество решений для

    // значение i.

    int table[n+1], i;

  

    // Инициализируем все значения таблицы как 0

    memset(table, 0, sizeof(table));

  

    // Базовый случай (если задано значение 0)

    table[0] = 1;

  

    // Один за другим рассмотрим 3 хода и обновим таблицу []

    // значения после индекса больше или равны

    // значение выбранного хода

    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(void)

{

    int n = 20;

    printf("Count for %d is %d\n", n, count(n));

  

    n = 13;

    printf("Count for %d is %d", n, count(n));

    return 0;

}

Джава

// Java-программа для подсчета количества
// возможные пути к данной оценке
// может быть достигнуто в игре, где
// ход может заработать 3, 5 или 10

import java.util.Arrays;

  

class GFG

{

    // Возвращает количество способов получить оценку n

    static int count(int n)

    {

        // таблица [i] будет хранить количество решений для

        // значение i.

        int table[] = new int[n + 1], i;

      

        // Инициализируем все значения таблицы как 0

        Arrays.fill(table, 0);

      

        // Базовый случай (если задано значение 0)

        table[0] = 1;

      

        // Один за другим рассмотрим данный 3

        // перемещаем и обновляем таблицу []

        // значения после индекса больше

        // чем или равно значению

        // выбранный ход

        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];

    }

      

    // Код драйвера

    public static void main (String[] args) 

    {

        int n = 20;

        System.out.println("Count for "+n+" is "+count(n));

      

        n = 13;

        System.out.println("Count for "+n+" is "+count(n));

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python программа для подсчета количества возможных путей к заданному
# оценка может быть достигнута в игре, где ход может заработать 3 или
№ 5 или 10.

  
# Возвращает количество способов достичь оценки n.

def count(n):

  

    # table [i] будет хранить количество решений для значения i.

    # Инициализировать все значения таблицы как 0.

    table = [0 for i in range(n+1)]

  

    # Базовый случай (если задано значение 0)

    table[0] = 1

  

    # Один за другим рассмотрите данные 3 хода и обновите

    # table [] значения после индекса больше или равно

    # к значению выбранного хода.

    for i in range(3, n+1):

        table[i] += table[i-3]

    for i in range(5, n+1):

        table[i] += table[i-5]

    for i in range(10, n+1):

        table[i] += table[i-10]

  

    return table[n]

  
# Драйверная программа

n = 20

print('Count for', n, 'is', count(n))

  

n = 13

print('Count for', n, 'is', count(n))

  
# Этот код предоставлен Soumen Ghosh

C #

// C # программа для подсчета количества
// возможные пути к данной оценке
// может быть достигнуто в игре, где
// ход может заработать 3, 5 или 10

using System;

  

class GFG {

      

    // Возвращает количество способов достижения

    // забить n

    static int count(int n)

    {

          

        // таблица [i] будет хранить количество

        // решений для значения i.

        int []table = new int[n + 1];

      

        // Инициализируем все значения таблицы

        // как 0

        for(int j = 0; j < n+1; j++)

            table[j] = 0;

          

        // Базовый случай (если задано значение 0)

        table[0] = 1;

      

        // Один за другим рассмотрим данный 3

        // перемещаем и обновляем таблицу []

        // значения после индекса больше

        // чем или равно значению

        // выбранный ход

        for (int i = 3; i <= n; i++)

            table[i] += table[i - 3];

        for (int i = 5; i <= n; i++)

            table[i] += table[i - 5];

        for (int i = 10; i <= n; i++)

            table[i] += table[i - 10];

      

        return table[n];

    }

      

    // Код драйвера

    public static void Main () 

    {

        int n = 20;

        Console.WriteLine("Count for "

             + n + " is " + count(n));

      

        n = 13;

        Console.Write("Count for "

            + n + " is " + count(n));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для подсчета количества
// возможные пути к данной оценке
// может быть достигнуто в игре, где
// ход может заработать 3, 5 или 10
// Возвращает количество способов достижения
// забить n

function counts($n

    // таблица [i] будет хранить количество

    // решений для значения i.

  

    // Инициализируем всю таблицу

    // значения как 0

    for($j = 0; $j < $n + 1; $j++) 

            $table[$j] = 0; 

  

    // Базовый случай (если задано значение 0)

    $table[0] = 1; 

  

    // Один за другим рассмотрим 3 хода

    // и обновляем значения таблицы [] после

    // индекс больше или равен

    // значение выбранного хода

    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]; 

  
// Код драйвера

$n = 20; 

echo "Count for ";

echo($n);

echo (" is "); 

echo counts($n); 

  

$n = 13;

echo ("\n") ;

echo "Count for ";

echo($n);

echo (" is " ); 

echo counts($n); 

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

Count for 20 is 4
Count for 13 is 2 

Упражнение: Как считать счет, когда (10, 5, 5), (5, 5, 10) и (5, 10, 5) рассматриваются как разные последовательности ходов. Аналогично, (5, 3, 3), (3, 5, 3) и (3, 3, 5) считаются разными.

Эта статья предоставлена Раджив Арора . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчитайте количество способов достичь заданного результата в игре

0.00 (0%) 0 votes