Número máximo de puntos después de lanzar un dado N veces

Dado un dado con caras m. La primera cara del dado contiene un punto, la segunda contiene dos puntos, y así sucesivamente, la m-ésima cara contiene m puntos. Cada cara aparece con una probabilidad  . Nuestra tarea es calcular el número máximo esperado de puntos después de lanzar los dados  varias veces.

Ejemplos:  

Entrada : 2 2 
Salida : 1.750000000000
Aquí el dado incluye {1, 2}. 
Entonces, el espacio muestral de lanzar los dados dos veces = 
{(1, 2), (1, 1), (2, 1), (2, 2)} 
Para (1, 2)–> máximo=2 
Para ( 1, 1)–> máximo=1 
Para (2, 2)–> máximo=2 
Para (2, 1)–> máximo=2 
La probabilidad de cada resultado es 0,25,
es decir, la expectativa es igual a 
(2+1+ 2+2)*(0.25) = 7/4 = 1.750000000000

Entrada : 6 3 
Salida : 4.958333333333  

Enfoque : 
La observación clave en este problema es que no. de veces que un número puede ocurrir un máximo de veces dependiendo de su número anterior. 
Para el i-ésimo número, será  . 
Tome m = 6, n = 2 como ejemplo. 
Los números totales con un máximo = 6 son iguales a  . 
Los números totales con un máximo, 5 son iguales a  . 
Del mismo modo, podemos averiguar para 4,3,2 y 1. 
6 6 6 6 6 6 5 
5 5 5 5 6 
4 4 4 4 5 6 
3 3 3 4 5 6 
2 2 3 4 5 6 1 
2 3 4 5 6 
Enumera el número máximo, la distribución será un supercubo n-dimensional con m-longitud-lado. Cada capa será un cubo grande menos un cubo más pequeño. 
Entonces, nuestra respuesta será la suma de todos los i-ésimos elementos de 1 a m dada por:  

El cálculo  puede causar un desbordamiento, por lo que podríamos mover el divisor a la suma y calcular  en su lugar. 
 

// CPP program for above implementation
#include <bits/stdc++.h>
using namespace std;
 
// Function find the maximum expectation
double expect(double m, double n)
{
    double ans = 0.0, i;
 
     
       for (i = m; i; i--)
        // formula to find the maximum number and
        // sum of maximum numbers
        ans += (pow(i / m, n) - pow((i - 1) / m, n)) * i;
   
    return ans;
}
 
// Driver code
int main()
{
    double m = 6, n = 3;
    cout << expect(m, n);
 
 return 0;
}

// Java program for above implementation
class GFG
{
// Function find the maximum expectation
static double expect(double m, double n)
{
    double ans = 0.0, i;
 
    for (i = m; i > 0; i--)
     
        // formula to find the maximum number
        // and sum of maximum numbers
        ans += (Math.pow(i / m, n) -
                Math.pow((i - 1) / m, n)) * i;
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    double m = 6, n = 3;
    System.out.println(String.format("%.5f",
                             expect(m, n)));
}
}
 
// This code is contributed by mits

# Python3 program for finding maximum
# number of dots after throwing a
# dice N times.
 
# Function to find the maximum
# expectation
def expect(m,n) :
 
    ans = 0.0
    i = m
    while (i):
         
        # formula to find the maximum
        # number and
        # sum of maximum numbers
        ans += (pow(i / m, n) - pow((i-1) / m, n)) * i
        i -= 1
 
    return ans
 
# Driver code
if __name__ == "__main__" :
     
    # multiple assignments
    m,n = 6,3
 
    # function calling
    print(expect(m,n))

// C# program for above implementation
using System;
 
class GFG
{
// Function find the maximum expectation
static double expect(double m, double n)
{
    double ans = 0.0, i;
 
    for (i = m; i > 0; i--)
     
        // formula to find the maximum number
        // and sum of maximum numbers
        ans += (Math.Pow(i / m, n) -
                Math.Pow((i - 1) / m, n)) * i;
 
    return ans;
}
 
// Driver code
public static void Main()
{
    double m = 6, n = 3;
    Console.WriteLine(expect(m, n));
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP program for above implementation
 
// Function find the maximum expectation
function expect($m, $n)
{
    $ans = 0.0;
 
    for ($i = $m; $i; $i--)
     
        // formula to find the maximum number
        // and sum of maximum numbers
        $ans += (pow($i / $m, $n) -
                 pow(($i - 1) / $m, $n)) * $i;
     
    return $ans;
}
 
// Driver code
$m = 6;
$n = 3;
echo expect($m, $n);
 
// This code is contributed by ChitraNayal
?>

<script>
// Javascript program for above implementation
     
    // Function find the maximum expectation
    function expect(m,n)
    {
        let ans = 0.0, i;
   
        for (i = m; i > 0; i--)
       
        // formula to find the maximum number
        // and sum of maximum numbers
            ans += (Math.pow(i / m, n) -
                Math.pow((i - 1) / m, n)) * i;
   
        return ans;
    }
     
    // Driver code
    let m = 6, n = 3;
     
    document.write(expect(m, n).toFixed(5))
 
     
 
// This code is contributed by avanitrachhadiya2155
</script>

4.95833

Complejidad del tiempo: O(m)