java - que - Calcula el número de formas de tirar un cierto número

maskformatter java ejemplos

Question

Soy un estudiante de ciencias de la computación de la escuela secundaria, y hoy me dieron un problema para:

Descripción del programa: Hay una creencia entre los jugadores de dados de que al lanzar tres dados es más fácil conseguir un diez que un nueve. ¿Puedes escribir un programa que pruebe o refuta esta creencia?

Haga que la computadora calcule todas las formas posibles de lanzar tres dados: 1 + 1 + 1, 1 + 1 + 2, 1 + 1 + 3, etc. Sume cada una de estas posibilidades y vea cuántas dan nueve como resultado y cuantos dan diez Si más dan diez, entonces la creencia está probada.

Rápidamente encontré una solución de fuerza bruta, como tal

int sum,tens,nines;
    tens=nines=0;

    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            for(int k=1;k<=6;k++){
                sum=i+j+k;
                //Ternary operators are fun!
                tens+=((sum==10)?1:0);
                nines+=((sum==9)?1:0);
            }
        }

    }
    System.out.println("There are "+tens+" ways to roll a 10");
    System.out.println("There are "+nines+" ways to roll a 9");

Lo que funciona bien, y una solución de fuerza bruta es lo que el profesor quería que hiciéramos. Sin embargo, no se escala, y estoy tratando de encontrar una manera de hacer un algoritmo que pueda calcular la cantidad de maneras de tirar n dados para obtener un número específico. Por lo tanto, comencé a generar el número de formas de obtener cada suma con n dados. Con 1 dado, obviamente hay 1 solución para cada uno. Luego calculé, a través de la fuerza bruta, las combinaciones con 2 y 3 dados. Estos son para dos:

Hay 1 formas de rodar un 2.
Hay 2 formas de tirar un 3.
Hay 3 formas de rodar un 4
Hay 4 formas de rodar un 5.
Hay 5 formas de rodar un 6.
Hay 6 formas de rodar un 7
Hay 5 formas de tirar un 8
Hay 4 formas de tirar un 9
Hay 3 formas de tirar un 10
Hay 2 formas de rodar un 11
Hay 1 maneras de rodar un 12

Lo que parece bastante sencillo; Se puede calcular con una simple función de valor absoluto lineal. Pero entonces las cosas empiezan a complicarse. Con 3:

Hay 1 formas de rodar un 3.
Hay 3 formas de rodar un 4
Hay 6 formas de rodar un 5
Hay 10 formas de rodar un 6.
Hay 15 formas de rodar un 7
Hay 21 formas de tirar un 8
Hay 25 formas de tirar un 9
Hay 27 formas de tirar un 10
Hay 27 formas de rodar un 11
Hay 25 formas de rodar un 12
Hay 21 formas de tirar un 13
Hay 15 formas de rodar un 14
Hay 10 formas de rodar un 15
Hay 6 formas de rodar un 16
Hay 3 formas de rodar un 17
Hay 1 maneras de rodar un 18

Así que miro eso, y pienso: ¡Genial, números triangulares! Sin embargo, luego me doy cuenta de esos molestos 25s y 27s. Así que obviamente no son números triangulares, sino una expansión polinomial, ya que es simétrica.
Así que me dirijo a Google y me encuentro con esta página que explica algunos detalles sobre cómo hacer esto con las matemáticas. Es bastante fácil (aunque largo) encontrar esto utilizando derivados repetidos o expansión, pero sería mucho más difícil programarlo para mí. No entendí bien la segunda y tercera respuesta, ya que nunca había encontrado esa notación o esos conceptos en mis estudios de matemáticas. ¿Podría alguien explicar cómo podría escribir un programa para hacer esto, o explicar las soluciones dadas en esa página, para mi propia comprensión de la combinatoria?

EDITAR: Estoy buscando una forma matemática para resolver esto, que da un número teórico exacto, no simulando dados

Answer 1

Echa un vistazo a los métodos de Monte Carlo que generalmente se escalan linealmente con el tamaño de entrada. En este caso, el ejemplo es fácil, asumimos que ya que una vez que el lanzamiento de los dados no afecta al otro en lugar de contar las combinaciones, podemos simplemente contar la suma de las caras de los dados lanzados al azar (muchas veces).

   public class MonteCarloDice {

    private Map<Integer, Integer> histogram;
    private Random rnd;
    private int nDice;
    private int n;

    public MonteCarloDice(int nDice, int simulations) {
        this.nDice = nDice;
        this.n = simulations;
        this.rnd = new Random();
        this.histogram = new HashMap<>(1000);
        start();
    }

    private void start() {
        for (int simulation = 0; simulation < n; simulation++) {
            int sum = 0;
            for (int i = 0; i < nDice; i++) {
                sum += rnd.nextInt(6) + 1;
            }
            if (histogram.get(sum) == null)
                histogram.put(sum, 0);
            histogram.put(sum, histogram.get(sum) + 1);
        }
        System.out.println(histogram);
    }


    public static void main(String[] args) {
        new MonteCarloDice(3, 100000);
        new MonteCarloDice(10, 1000000);
    }

}

El error disminuye con el número de simulaciones pero a costa del tiempo de ejecución, pero los valores anteriores fueron bastante rápidos.

3 dados

{3=498, 4=1392, 5=2702, 6=4549, 7=7041, 8=9844, 9=11583, 10=12310, 11=12469, 12=11594, 13=9697, 14=6999, 15=4677, 17=1395, 16=2790, 18=460}

10 dados

{13=3, 14=13, 15=40, 17=192, 16=81, 19=769, 18=396, 21=2453, 20=1426, 23=6331, 22=4068, 25=13673, 24=9564, 27=25136, 26=19044, 29=40683, 28=32686, 31=56406, 30=48458, 34=71215, 35=72174, 32=62624, 33=68027, 38=63230, 39=56008, 36=71738, 37=68577, 42=32636, 43=25318, 40=48676, 41=40362, 46=9627, 47=6329, 44=19086, 45=13701, 51=772, 50=1383, 49=2416, 48=3996, 55=31, 54=86, 53=150, 52=406, 59=1, 57=2, 56=7}

Answer 2

La descripción matemática es solo un "truco" para hacer el mismo conteo. Utiliza el polinomio para expresar dados, 1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x significa que cada valor 1-6 se cuenta una vez , y usa la multiplicación polinomial P_1*P_2 para contar diferentes combinaciones. Esto se hace ya que el coeficiente en algún exponente ( k ) se calcula sumando todo el coeficiente en P_1 y P_2 que suma de exponente a k .

Por ejemplo, para dos dados tenemos:

(1*x^6 + 1*x^5 + 1*x^4 + 1*x^3 + 1*x^2 + 1*x) * (x^6 + x^5 + x^4 + x^3 + x^2 + x) = 
(1*1)*x^12 + (1*1 + 1*1)*x^11 + (1*1 + 1*1 + 1*1)*x^11 + ... + (1*1 + 1*1)*x^3 + (1*1)*x^2

El cálculo por este método tiene la misma complejidad que "contar" uno.

Dado que la función (x^6 + x^5 + x^4 + x^3 + x^2 + x)^n tiene una expresión más simple (x(x-1)^6/(x-1))^n , it Es posible utilizar el método de derivación. (x(x-1)^6/(x-1))^n es un polinomio, y estamos buscando el coeficiente en x^s ( a_s ). El coeficiente libre (en x^0 ) de la derivación s! * a_k es s! * a_k s! * a_k . Entonces, la derivación s''th en 0 es s! * a_k s! * a_k .

Entonces, tenemos que derivar s tiempos de esta función. Se puede hacer usando reglas de derivación, pero creo que tendrá una complejidad aún peor que el enfoque de conteo ya que cada derivación produce una función "más compleja". Aquí están las primeras tres derivaciones de Wolfram Alpha: first , segunda y tercera .

En general, prefiero contar la solución, y mellamokb dio un buen enfoque y explicación.

Answer 3

La solución que utiliza el método de la función de generación con N(d, s) es probablemente la más fácil de programar. Puedes usar la recursión para modelar el problema muy bien:

public int numPossibilities(int numDice, int sum) {
    if (numDice == sum)
        return 1;
    else if (numDice == 0 || sum < numDice)
        return 0;
    else
        return numPossibilities(numDice, sum - 1) +
               numPossibilities(numDice - 1, sum - 1) -
               numPossibilities(numDice - 1, sum - 7);
}

A primera vista, esto parece ser una solución bastante sencilla y eficiente. Sin embargo, notará que muchos cálculos de los mismos valores de numDice y sum pueden repetirse y recalcularse una y otra vez, lo que hace que esta solución sea incluso menos eficiente que su método original de fuerza bruta. Por ejemplo, al calcular todos los conteos para 3 dados, mi programa ejecutó la función numPossibilities un total de 15106 veces, a diferencia de su bucle que solo toma 6^3 = 216 ejecuciones.

Para que esta solución sea viable, debe agregar una técnica más: la memorización (almacenamiento en caché) de los resultados calculados previamente. Al usar un objeto HashMap , por ejemplo, puede almacenar combinaciones que ya se han calculado y consultarlas antes de ejecutar la recursión. Cuando implementé un caché, la función numPossibilities solo se ejecuta 151 veces en total para calcular los resultados para 3 dados.

La mejora de la eficiencia aumenta a medida que aumenta el número de dados (los resultados se basan en la simulación con mi propia solución implementada):

# Dice | Brute Force Loop Count | Generating-Function Exec Count
3      | 216 (6^3)              | 151
4      | 1296 (6^4)             | 261
5      | 7776 (6^5)             | 401
6      | 46656 (6^6)            | 571
7      | 279936 (6^7)           | 771
...
20     | 3656158440062976       | 6101

Answer 4

No necesita fuerza bruta, ya que su primer rollo determina qué valores pueden usarse en el segundo rollo, y tanto el primer rollo como el segundo determinan el tercer rollo. Tomemos el ejemplo de las decenas, supongamos que sacas un 6 , entonces 10-6=4 significa que todavía necesitas 4 . Para la segunda tirada necesitas al menos 3 , porque tu tercera tirada debería contar al menos para 1 . Así que la segunda tirada va de 1 a 3 . Supongamos que su segunda tirada es 2 , tiene 10-6-2=2 , lo que significa que su tercera tirada es un 2 , no hay otra manera.

Pseudo código para decenas:

tens = 0

for i = [1..6] // first roll can freely go from 1 to 6
   from_j = max(1, 10 - i - 6) // We have the first roll, best case is we roll a 6 in the third roll
   top_j = min(6, 10 - i - 1) // we need to sum 10, minus i, minus at least 1 for the third roll
   for j = [from_j..to_j]
      tens++

Tenga en cuenta que cada bucle agrega 1, por lo que al final sabe que este código se repite exactamente 27 veces.

Aquí está el código de Ruby para los 18 valores (lo siento, no es Java, pero se puede seguir fácilmente). Tenga en cuenta el mínimo y el máximo, que determinan qué valores pueden tener cada una de las tiradas de dados.

counts = [0] * 18

1.upto(18) do |n|
  from_i = [1, n - 6 - 6].max # best case is we roll 6 in 2nd and 3rd roll
  top_i = [6, n - 1 -1].min # at least 1 for 2nd and 3rd roll
  from_i.upto(top_i) do |i|
    from_j = [1, n - i - 6].max # again we have the 2nd roll defined, best case for 3rd roll is 6
    top_j = [6, n - i -1].min # at least 1 for 3rd roll
    from_j.upto(top_j) do
      # no need to calculate k since it''s already defined being n - first roll - second roll
      counts[n-1] += 1
    end
  end
end

print counts

Para un enfoque matemático, eche un vistazo a https://math.stackexchange.com/questions/4632/how-can-i-algorithmically-count-the-number-of-ways-n-m-sided-dice-can-add-up-t