Рубрики

Бросок костей | DP-30

Для каждого n кубиков с m гранями, пронумерованных от 1 до m, найдите количество способов получить сумму X. X — сумма значений на каждой грани, когда все кости брошены.

Наивный подход состоит в том, чтобы найти все возможные комбинации значений из n кубиков и продолжать считать результаты, которые суммируются с X.

Эта проблема может быть эффективно решена с помощью динамического программирования (DP) .

Let the function to find X from n dice is: Sum(m, n, X)
The function can be represented as:
Sum(m, n, X) = Finding Sum (X - 1) from (n - 1) dice plus 1 from nth dice
               + Finding Sum (X - 2) from (n - 1) dice plus 2 from nth dice
               + Finding Sum (X - 3) from (n - 1) dice plus 3 from nth dice
                  ...................................................
                  ...................................................
                  ...................................................
              + Finding Sum (X - m) from (n - 1) dice plus m from nth dice

So we can recursively write Sum(m, n, x) as following
Sum(m, n, X) = Sum(m, n - 1, X - 1) + 
               Sum(m, n - 1, X - 2) +
               .................... + 
               Sum(m, n - 1, X - m)

Почему DP подход?
Вышеуказанная проблема имеет перекрывающиеся подзадачи. Смотрите схему ниже. Также посмотрите эту рекурсивную реализацию. Пусть будет 3 кубика, каждый с 6 гранями, и нам нужно найти количество способов получить сумму 8:

Sum(6, 3, 8) = Sum(6, 2, 7) + Sum(6, 2, 6) + Sum(6, 2, 5) + 
               Sum(6, 2, 4) + Sum(6, 2, 3) + Sum(6, 2, 2)

To evaluate Sum(6, 3, 8), we need to evaluate Sum(6, 2, 7) which can 
recursively written as following:
Sum(6, 2, 7) = Sum(6, 1, 6) + Sum(6, 1, 5) + Sum(6, 1, 4) + 
               Sum(6, 1, 3) + Sum(6, 1, 2) + Sum(6, 1, 1)

We also need to evaluate Sum(6, 2, 6) which can recursively written
as following:
Sum(6, 2, 6) = Sum(6, 1, 5) + Sum(6, 1, 4) + Sum(6, 1, 3) +
               Sum(6, 1, 2) + Sum(6, 1, 1)
..............................................
..............................................
Sum(6, 2, 2) = Sum(6, 1, 1)

Пожалуйста, внимательно посмотрите на приведенную выше рекурсию. Подзадачи в RED решаются впервые, а подзадачи в BLUE решаются снова (демонстрируют перекрывающиеся подзадачи). Следовательно, сохранение результатов решенных подзадач экономит время.

Ниже приводится реализация подхода динамического программирования.

C ++

// C ++ программа для поиска количества способов получения суммы 'x' с помощью 'n'
// игральная кость, где каждая игральная кость имеет «m» лица
#include <iostream>
#include <string.h>

using namespace std;

  
// Основная функция, которая возвращает количество способов получить сумму 'x'
// с «n» кубиками и «m» с m гранями.

int findWays(int m, int n, int x)

{

    // Создать таблицу для хранения результатов подзадач. Один дополнительный

    // строка и столбец используются для простоты (Количество кубиков

    // непосредственно используется как индекс строки, а сумма напрямую

    // как индекс столбца). Записи в 0-й строке и 0-м столбце

    // никогда не используются.

    int table[n + 1][x + 1];

    memset(table, 0, sizeof(table)); // Инициализируем все записи как 0

  

    // Таблица записей только для одного кубика

    for (int j = 1; j <= m && j <= x; j++)

        table[1][j] = 1;

  

    // Заполняем остальные записи в таблице, используя рекурсивное отношение

    // i: количество кубиков, j: сумма

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

        for (int j = 1; j <= x; j++)

            for (int k = 1; k <= m && k < j; k++)

                table[i][j] += table[i-1][j-k];

  

    / * Раскомментируйте эти строки, чтобы увидеть содержимое таблицы

    для (int i = 0; i <= n; i ++)

    {

      для (int j = 0; j <= x; j ++)

        cout << table [i] [j] << "";

      cout << endl;

    } * /

    return table[n][x];

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    cout << findWays(4, 2, 1) << endl;

    cout << findWays(2, 2, 3) << endl;

    cout << findWays(6, 3, 8) << endl;

    cout << findWays(4, 2, 5) << endl;

    cout << findWays(4, 3, 5) << endl;

  

    return 0;

}

Джава

// Java программа для поиска количества способов получить сумму 'x' с помощью 'n'
// игральная кость, где каждая игральная кость имеет «m» лица

import java.util.*;

import java.lang.*;

import java.io.*;

  

class GFG {

    / * Основная функция, которая возвращает количество способов получить сумму «x» с «n» кубиками и «m» с m гранями. * /

    public static long findWays(int m, int n, int x){

          

    / * Создать таблицу для хранения результатов подзадач.

    Одна дополнительная строка и столбец используются для простоты

    (Количество кубиков напрямую используется в качестве индекса строки, а сумма напрямую используется в качестве индекса столбца).

    Записи в 0-й строке и 0-м столбце никогда не используются. * /

    long[][] table = new long[n+1][x+1];

          

    / * Записи в таблице только для одного кубика * /

    for(int j = 1; j <= m && j <= x; j++)

                table[1][j] = 1;

              

    / * Заполнить остальные записи в таблице, используя рекурсивное отношение

    i: количество кубиков, j: сумма * /

    for(int i = 2; i <= n;i ++){

                for(int j = 1; j <= x; j++){

                    for(int k = 1; k < j && k <= m; k++)

                        table[i][j] += table[i-1][j-k];

                }

        }

          

        / * Раскомментируйте эти строки, чтобы увидеть содержимое таблицы

        для (int i = 0; i <n + 1; i ++) {

            для (int j = 0; j <x + 1; j ++)

                System.out.print (dt [i] [j] + "");

            System.out.println ();

        } * /

          

        return table[n][x];

    }

      

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

    public static void main (String[] args) {

        System.out.println(findWays(4, 2, 1)); 

        System.out.println(findWays(2, 2, 3)); 

        System.out.println(findWays(6, 3, 8)); 

        System.out.println(findWays(4, 2, 5)); 

        System.out.println(findWays(4, 3, 5)); 

    }

}

  
// Этот код предоставлен MaheshwariPiyush

python3

# Программа Python3, чтобы найти количество способов получить сумму 'x' с помощью кости 'n'
# где каждый кубик имеет «м» лица

  
# Основная функция, которая возвращает количество способов получить сумму «х»
# с «n» кубиками и «m» с m гранями.

def findWays(m,n,x):

    # Создать таблицу для хранения результатов подзадач. Один дополнительный

    # строка и столбец используются для простоты (Количество кубиков

    # непосредственно используется как индекс строки, а сумма напрямую используется

    # как индекс столбца). Записи в 0-й строке и 0-м столбце

    # никогда не используются.

    table=[[0]*(x+1) for i in range(n+1)] # Инициализировать все записи как 0

      

    for j in range(1,min(m+1,x+1)): # Записи в таблице только для одного кубика

        table[1][j]=1

          

    # Заполнить остальные записи в таблице, используя рекурсивное отношение

    # i: количество кубиков, j: сумма

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

        for j in range(1,x+1):

            for k in range(1,min(m+1,j)):

                table[i][j]+=table[i-1][j-k]

      

    #print (дт)

    # Раскомментируйте над строкой, чтобы увидеть содержимое таблицы

      

    return table[-1][-1]

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

print(findWays(4,2,1))

print(findWays(2,2,3))

print(findWays(6,3,8))

print(findWays(4,2,5))

print(findWays(4,3,5))

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

C #

// C # программа для поиска номера
// способов получить сумму 'x'
// с 'n' кубиками, где каждый
// кубик имеет «м» лица

using System;

  

class GFG

{
// Основная функция, которая возвращает
// количество способов получить сумму 'x'
// с «n» кубиками и «m» с m гранями.

static int findWays(int m, 

                    int n, int x)

{

    // Создать таблицу для хранения

    // результаты подзадач.

    // строка и столбец используются

    // для простоты (число

    // кости используются напрямую

    // как индекс строки и сумма

    // непосредственно используется как столбец

    // показатель). Записи в 0-м

    // строка и 0-й столбец

    // никогда не использовался.

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

                           x + 1];

                             

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

    // записи как 0

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

    for (int j = 0; j <= x; j++)

    table[i, j] = 0;

      

    // Записи таблицы для

    // только одна игральная кость

    for (int j = 1; 

             j <= m && j <= x; j++)

        table[1, j] = 1;

  

    // Заполняем остальные записи

    // в таблице используя рекурсив

    // отношение i: количество

    // кубик, j: сумма

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

        for (int j = 1; j <= x; j++)

            for (int k = 1; 

                     k <= m && k < j; k++)

                table[i, j] += table[i - 1, 

                                     j - k];

  

    / * Раскомментируйте эти строки

    посмотреть содержание таблицы

    для (int i = 0; i <= n; i ++)

    {

    для (int j = 0; j <= x; j ++)

        cout << table [i] [j] << "";

    cout << endl;

    } * /

    return table[n, x];

}

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

public static void Main()

{

    Console.WriteLine(findWays(4, 2, 1));

    Console.WriteLine(findWays(2, 2, 3));

    Console.WriteLine(findWays(6, 3, 8));

    Console.WriteLine(findWays(4, 2, 5));

    Console.WriteLine(findWays(4, 3, 5));

}
}

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

PHP

<?php
// PHP программа для поиска номера
// способов получить сумму 'x' с
// 'n' кости, где каждая игральная кость
// имеет "м" лица

  
// Основная функция, которая возвращает
// количество способов получить сумму 'x'
// с «n» кубиками и «m» с m гранями.

function findWays($m, $n, $x)

{

    // Создать таблицу для хранения результатов

    // подзадач. Один дополнительный ряд

    // и столбец используются для

    // Simpilicity (Количество кубиков

    // используется непосредственно как индекс строки и

    // сумма непосредственно используется в качестве столбца

    // показатель). Записи в 0-й строке

    // и 0-й столбец никогда не используются.

    $table;

      

    // Инициализируем все записи как 0

        for ($i = 1; $i < $n + 1; $i++)

        for ($j = 1; $j < $x + 1; $j++)

        $table[$i][$j] = 0;

  

    // Записи таблицы для

    // только одна игральная кость

    for ($j = 1; $j <= $m && 

                 $j <= $x; $j++)

        $table[1][$j] = 1;

  

    // Заполняем остальные записи

    // в таблице используя рекурсив

    // отношение i: количество кубиков,

    // j: сумма

    for ($i = 2; $i <= $n; $i++)

        for ($j = 1; $j <= $x; $j++)

            for ($k = 1; $k <= $m && 

                         $k < $j; $k++)

                $table[$i][$j] += 

                        $table[$i - 1][$j - $k];

  

    return $table[$n][$x];

}

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

echo findWays(4, 2, 1). "\n";

echo findWays(2, 2, 3). "\n";

echo findWays(6, 3, 8). "\n";

echo findWays(4, 2, 5). "\n";

echo findWays(4, 3, 5). "\n";

  
// Этот код предоставлен mits.
?>


Выход :

0
2
21
4
6

Сложность времени: O (m * n * x), где m — количество граней, n — количество кубиков, а x — сумма.

Мы можем добавить следующие два условия в начале findWays (), чтобы улучшить производительность программы в экстремальных случаях (х слишком высокий или х слишком низкий)

// Когда х настолько велико, что сумма не может выйти за пределы х, даже когда мы
// получить максимальное значение при каждом броске костей.

if (m*n <= x)

    return (m*n == x);

 
// когда х слишком низко

if (n >= x)

    return (n == x);

При добавлении вышеуказанных условий временная сложность становится равной O (1), когда x> = m * n или когда x <= n.

Ниже приводится реализация подхода оптимизированного динамического программирования.

C ++

// C ++ программа
// Основная функция, которая возвращает количество способов получить сумму 'x'
// с «n» кубиками и «m» с m гранями.
#include<bits/stdc++.h>

using namespace std;

  

long findWays(int f, int d, int s)

{

    // Создать таблицу для хранения результатов подзадач. Один дополнительный

    // строка и столбец используются для простоты (Количество кубиков

    // непосредственно используется как индекс строки, а сумма напрямую

    // как индекс столбца). Записи в 0-й строке и 0-м столбце

    // никогда не используются.

    long mem[d + 1][s + 1];

    memset(mem,0,sizeof mem);

    // Табличные записи без кубиков

    // Если у вас нет данных, тогда значение должно быть 0, поэтому результат равен 1

    mem[0][0] = 1;

    // Перебираем кубики

    for (int i = 1; i <= d; i++)

    {

        // перебирать сумму

        for (int j = i; j <= s; j++)

        {

            // Результат получается двумя способами: закрепить текущую кость и потратить 1 значение,

            // поэтому у нас есть оставшиеся комбинации mem [i-1] [j-1], чтобы найти оставшиеся комбинации, которые мы

            // придется закрепить значения выше 1, тогда мы используем mem [i] [j-1] для суммирования всех комбинаций

            // это закрепляет оставшиеся j-1. Но есть способ, когда "jf-1> = 0" мы добавим

            // дополнительные комбинации, поэтому мы удаляем комбинации, которые прикрепляют только экстраполированную грань кости и

            // вычитаем экстраполированные комбинации.

            mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1];

            if (j - f - 1 >= 0)

                mem[i][j] -= mem[i - 1][j - f - 1];

        }

    }

    return mem[d][s];

}

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

int main(void)

{

    cout << findWays(4, 2, 1) << endl;

    cout << findWays(2, 2, 3) << endl;

    cout << findWays(6, 3, 8) << endl;

    cout << findWays(4, 2, 5) << endl;

    cout << findWays(4, 3, 5) << endl;

    return 0;

}

  
// Этот код предоставлен ankush_953

Джава

/**

 * The main function that returns number of ways to get sum 'x'

 * with 'n' dice and 'm' with m faces.

 

 * @author Pedro H. Chaves <pedrohcd@hotmail.com> <https://github.com/pedrohcdo>

 */

public class GFG {

      

    / **

     * Подсчет путей

     *

     * @param f

     * @param d

     * @param s

     * @возвращение

     * /

    public static long findWays(int f, int d, int s) {

        // Создать таблицу для хранения результатов подзадач. Один дополнительный

        // строка и столбец используются для простоты (Количество кубиков

        // непосредственно используется как индекс строки, а сумма напрямую

        // как индекс столбца). Записи в 0-й строке и 0-м столбце

        // никогда не используются.

        long mem[][] = new long[d + 1][s + 1];

        // Табличные записи без кубиков

        // Если у вас нет данных, тогда значение должно быть 0, поэтому результат равен 1

        mem[0][0] = 1;

        // Перебираем кубики

        for(int i=1; i<=d; i++) {

            // перебирать сумму

            for(int j=i; j<=s; j++) {

                // Результат получается двумя способами: закрепить текущую кость и потратить 1 значение,

                // поэтому у нас есть оставшиеся комбинации mem [i-1] [j-1], чтобы найти оставшиеся комбинации, которые мы

                // придется закрепить значения выше 1, тогда мы используем mem [i] [j-1] для суммирования всех комбинаций

                // это закрепляет оставшиеся j-1. Но есть способ, когда "jf-1> = 0" мы добавим

                // дополнительные комбинации, поэтому мы удаляем комбинации, которые прикрепляют только экстраполированную грань кости и

                // вычитаем экстраполированные комбинации.

                mem[i][j] = mem[i][j-1] + mem[i-1][j-1];

                if(j-f-1 >= 0)

                    mem[i][j] -= mem[i-1][j-f-1];

            }

        }

        return mem[d][s];

    }

      

      

    / **

     * Основной

     *

     * @param args

     * /

    public static void main(String[] args) {

        System.out.println(findWays(4, 2, 1));

        System.out.println(findWays(2, 2, 3));

        System.out.println(findWays(6, 3, 8));

        System.out.println(findWays(4, 2, 5));

        System.out.println(findWays(4, 3, 5));

    }

}

python3

# Python программа
# Основная функция, которая возвращает количество способов получить сумму «х»
# с «n» кубиками и «m» с m гранями.

  

  

def findWays(f, d, s):

    # Создать таблицу для хранения результатов подзадач. Один дополнительный

    # строка и столбец используются для простоты (Количество кубиков

    # непосредственно используется как индекс строки, а сумма напрямую используется

    # как индекс столбца). Записи в 0-й строке и 0-м столбце

    # никогда не используются.

    mem = [[0 for i in range(s+1)] for j in range(d+1)]

    # Таблица записей без кубиков

    # Если у вас нет никаких данных, тогда значение должно быть 0, поэтому результат равен 1

    mem[0][0] = 1

    # Перебирать кубики

    for i in range(1, d+1):

  

        # Итерировать по сумме

        for j in range(1, s+1):

            # Результат получается двумя способами: закрепить текущую кость и потратить 1 значение,

            # поэтому у нас есть оставшиеся комбинации mem [i-1] [j-1], чтобы найти оставшиеся комбинации, которые мы

            # придется закрепить значения выше 1, тогда мы используем mem [i] [j-1] для суммирования всех комбинаций

            #, которые прикрепляют оставшиеся j-1. Но есть способ, когда "jf-1> = 0" мы добавим

            # дополнительные комбинации, поэтому мы удаляем комбинации, которые прикрепляют только к экстраполированной грани кости и

            # вычитаем экстраполированные комбинации.

            mem[i][j] = mem[i][j - 1] + mem[i - 1][j - 1]

            if j - f - 1 >= 0:

                mem[i][j] -= mem[i - 1][j - f - 1]

    return mem[d][s]

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

  

print(findWays(4, 2, 1))

print(findWays(2, 2, 3))

print(findWays(6, 3, 8))

print(findWays(4, 2, 5))

print(findWays(4, 3, 5))

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

C #

// C # программа
// Основная функция, которая возвращает количество способов получить сумму 'x'
// с «n» кубиками и «m» с m гранями.

using System;

  

class GFG 

{

      

    / **

    * Подсчет путей

    *

    * @param f

    * @param d

    * @param s

    * @возвращение

    * /

    public static long findWays(int f, int d, int s) 

    {

        // Создать таблицу для хранения результатов подзадач. Один дополнительный

        // строка и столбец используются для простоты (Количество кубиков

        // непосредственно используется как индекс строки, а сумма напрямую

        // как индекс столбца). Записи в 0-й строке и 0-м столбце

        // никогда не используются.

        long [,]mem = new long[d + 1,s + 1];

          

        // Табличные записи без кубиков

        // Если у вас нет данных, тогда значение должно быть 0, поэтому результат равен 1

        mem[0,0] = 1;

        // Перебираем кубики

        for(int i = 1; i <= d; i++)

        {

            // перебирать сумму

            for(int j = i; j <= s; j++) 

            {

                // Результат получается двумя способами: закрепить текущую кость и потратить 1 значение,

                // поэтому у нас есть оставшиеся комбинации mem [i-1, j-1], чтобы найти оставшиеся комбинации, которые мы

                // придется закрепить значения выше 1, тогда мы используем mem [i, j-1] для суммирования всех комбинаций

                // это закрепляет оставшиеся j-1. Но есть способ, когда "jf-1> = 0" мы добавим

                // дополнительные комбинации, поэтому мы удаляем комбинации, которые прикрепляют только экстраполированную грань кости и

                // вычитаем экстраполированные комбинации.

                mem[i,j] = mem[i,j-1] + mem[i-1,j-1];

                if(j-f-1 >= 0)

                    mem[i,j] -= mem[i-1,j-f-1];

            }

        }

        return mem[d,s];

    }

      

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

    public static void Main(String[] args) 

    {

        Console.WriteLine(findWays(4, 2, 1));

        Console.WriteLine(findWays(2, 2, 3));

        Console.WriteLine(findWays(6, 3, 8));

        Console.WriteLine(findWays(4, 2, 5));

        Console.WriteLine(findWays(4, 3, 5));

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход :

0
2
21
4
6

Сложность времени: O (n * x), где n — количество кубиков, а x — сумма.

Упражнение:
Расширьте приведенный выше алгоритм, чтобы найти вероятность получить Sum> X.

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

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

Бросок костей | DP-30

0.00 (0%) 0 votes