Dado un tablero lineal de longitud N numerado del 1 al N , la tarea es encontrar el número esperado de movimientos requeridos para llegar a la celda N del tablero , si comenzamos en la celda numerada 1 y en cada paso lanzamos un dado cúbico para decidir el próximo movimiento. Además, no podemos salirnos de los límites del tablero. Tenga en cuenta que el número esperado de movimientos puede ser fraccionario.
Ejemplos:
Entrada: N = 8
Salida: 7
p1 = (1 / 6) | 1-paso -> 6 movimientos esperados para llegar al final
p2 = (1/6) | 2-pasos -> 6 movimientos esperados para llegar al final
p3 = (1/6) | 3-pasos -> 6 movimientos esperados para llegar al final
p4 = (1/6) | 4-pasos -> 6 movimientos esperados para llegar al final
p5 = (1/6) | 5-pasos -> 6 movimientos esperados para llegar al final
p6 = (1/6) | 6 pasos -> 6 movimientos esperados para llegar al final
Si estamos a 7 pasos, entonces podemos terminar en 1, 2, 3, 4, 5, 6 pasos
con la misma probabilidad, es decir, (1/6).
Mire la simulación anterior para entender mejor.
dp[N – 1] = dp[7]
= 1 + (dp[1] + dp[2] + dp[3] + dp[4] + dp[5] + dp[6]) / 6
= 1 + 6 = 7Entrada: N = 10
Salida: 7.36111
Enfoque: Ya se ha discutido un enfoque basado en la programación dinámica en una publicación anterior. En este artículo, se discutirá un método más optimizado para resolver este problema. La idea es usar una técnica llamada Matrix-Exponentiation .
Definamos A n como el número esperado de movimientos para llegar al final de un tablero de longitud N + 1 .
La relación de recurrencia será:
UN n = 1 + (UN n-1 + UN n-2 + UN n-3 + UN n-4 + UN n-5 + UN n-6 ) / 6
Ahora, la relación de recurrencia debe convertirse en un formato adecuado.
A n = 1 + (A n-1 + A n-2 + A n-3 + A n-4 + A n-5 + A n-6 ) / 6 (ecuación 1)
A n-1 = 1 + ( A n-2 + A n-3 + A n-4 + A n-5 + A n-6 + A n-7 ) / 6 (ecuación 2)
Restando 1 con 2, obtenemos A n = 7 * (A n-1 ) / 6 – (A n-7 ) / 6
La técnica de exponenciación matricial se puede aplicar aquí en la relación de recurrencia anterior.
La base será {6, 6, 6, 6, 6, 6, 0} correspondiente a {A6, A5, A4…, A0} El
multiplicador será
{
{7/6, 1, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0} ,
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 1},
{ -1/6, 0, 0, 0, 0, 0, 0}
}
Para encontrar el valor:
- Encuentra mul (N – 7)
- Encuentra base * mul (N – 7) .
- El primer valor de la array 1 * 7 será la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define maxSize 50
using namespace std;
// Function to multiply two 7 * 7 matrix
vector<vector<double> > matrix_product(
vector<vector<double> > a,
vector<vector<double> > b)
{
vector<vector<double> > c(7);
for (int i = 0; i < 7; i++)
c[i].resize(7, 0);
for (int i = 0; i < 7; i++)
for (int j = 0; j < 7; j++)
for (int k = 0; k < 7; k++)
c[i][j] += a[i][k] * b[k][j];
return c;
}
// Function to perform matrix exponentiation
vector<vector<double> > mul_expo(vector<vector<double> > mul, int p)
{
// 7 * 7 identity matrix
vector<vector<double> > s = { { 1, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1 } };
// Loop to find the power
while (p != 1) {
if (p % 2 == 1)
s = matrix_product(s, mul);
mul = matrix_product(mul, mul);
p /= 2;
}
return matrix_product(mul, s);
}
// Function to return the required count
double expectedSteps(int x)
{
// Base cases
if (x == 0)
return 0;
if (x <= 6)
return 6;
// Multiplier matrix
vector<vector<double> > mul = { { (double)7 / 6, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1 },
{ (double)-1 / 6, 0, 0, 0, 0, 0, 0 } };
// Finding the required multiplier
// i.e mul^(X-6)
mul = mul_expo(mul, x - 6);
// Final answer
return (mul[0][0]
+ mul[1][0]
+ mul[2][0]
+ mul[3][0]
+ mul[4][0]
+ mul[5][0])
* 6;
}
// Driver code
int main()
{
int n = 10;
cout << expectedSteps(n - 1);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static final int maxSize = 50;
// Function to multiply two 7 * 7 matrix
static double [][] matrix_product(double [][] a,
double [][] b)
{
double [][] c = new double[7][7];
for (int i = 0; i < 7; i++)
for (int j = 0; j < 7; j++)
for (int k = 0; k < 7; k++)
c[i][j] += a[i][k] * b[k][j];
return c;
}
// Function to perform matrix exponentiation
static double [][] mul_expo(double [][] mul, int p)
{
// 7 * 7 identity matrix
double [][] s = {{ 1, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1 }};
// Loop to find the power
while (p != 1)
{
if (p % 2 == 1)
s = matrix_product(s, mul);
mul = matrix_product(mul, mul);
p /= 2;
}
return matrix_product(mul, s);
}
// Function to return the required count
static double expectedSteps(int x)
{
// Base cases
if (x == 0)
return 0;
if (x <= 6)
return 6;
// Multiplier matrix
double [][]mul = { { (double)7 / 6, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1 },
{(double) - 1 / 6, 0, 0,
0, 0, 0, 0 }};
// Finding the required multiplier
// i.e mul^(X-6)
mul = mul_expo(mul, x - 6);
// Final answer
return (mul[0][0] + mul[1][0] + mul[2][0] +
mul[3][0] + mul[4][0] + mul[5][0]) * 6;
}
// Driver code
public static void main(String[] args)
{
int n = 10;
System.out.printf("%.5f",expectedSteps(n - 1));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach import numpy as np maxSize = 50 # Function to multiply two 7 * 7 matrix def matrix_product(a, b) : c = np.zeros((7, 7)); for i in range(7) : for j in range(7) : for k in range(7) : c[i][j] += a[i][k] * b[k][j]; return c # Function to perform matrix exponentiation def mul_expo(mul, p) : # 7 * 7 identity matrix s = [ [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 1 ] ]; # Loop to find the power while (p != 1) : if (p % 2 == 1) : s = matrix_product(s, mul); mul = matrix_product(mul, mul); p //= 2; return matrix_product(mul, s); # Function to return the required count def expectedSteps(x) : # Base cases if (x == 0) : return 0; if (x <= 6) : return 6; # Multiplier matrix mul = [ [ 7 / 6, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 1 ], [ -1 / 6, 0, 0, 0, 0, 0, 0 ] ]; # Finding the required multiplier # i.e mul^(X-6) mul = mul_expo(mul, x - 6); # Final answer return (mul[0][0] + mul[1][0] + mul[2][0] + mul[3][0] + mul[4][0] + mul[5][0]) * 6; # Driver code if __name__ == "__main__" : n = 10; print(expectedSteps(n - 1)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static readonly int maxSize = 50;
// Function to multiply two 7 * 7 matrix
static double [,] matrix_product(double [,] a,
double [,] b)
{
double [,] c = new double[7, 7];
for (int i = 0; i < 7; i++)
for (int j = 0; j < 7; j++)
for (int k = 0; k < 7; k++)
c[i, j] += a[i, k] * b[k, j];
return c;
}
// Function to perform matrix exponentiation
static double [,] mul_expo(double [,] mul, int p)
{
// 7 * 7 identity matrix
double [,] s = {{ 1, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1 }};
// Loop to find the power
while (p != 1)
{
if (p % 2 == 1)
s = matrix_product(s, mul);
mul = matrix_product(mul, mul);
p /= 2;
}
return matrix_product(mul, s);
}
// Function to return the required count
static double expectedSteps(int x)
{
// Base cases
if (x == 0)
return 0;
if (x <= 6)
return 6;
// Multiplier matrix
double [,]mul = {{(double)7 / 6, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0 },
{ 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 1 },
{(double) - 1 / 6, 0, 0,
0, 0, 0, 0 }};
// Finding the required multiplier
// i.e mul^(X-6)
mul = mul_expo(mul, x - 6);
// Final answer
return (mul[0, 0] + mul[1, 0] + mul[2, 0] +
mul[3, 0] + mul[4, 0] + mul[5, 0]) * 6;
}
// Driver code
public static void Main(String[] args)
{
int n = 10;
Console.Write("{0:f5}", expectedSteps(n - 1));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
var maxSize = 50;
// Function to multiply two 7 * 7 matrix
function matrix_product(a, b)
{
var c = Array.from(Array(7),
() => Array(7).fill(0));
for(var i = 0; i < 7; i++)
for(var j = 0; j < 7; j++)
for(var k = 0; k < 7; k++)
c[i][j] += a[i][k] * b[k][j];
return c;
}
// Function to perform matrix exponentiation
function mul_expo( mul, p)
{
// 7 * 7 identity matrix
var s = [ [ 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 1, 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 1, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 0, 0, 0, 1 ] ];
// Loop to find the power
while (p != 1)
{
if (p % 2 == 1)
s = matrix_product(s, mul);
mul = matrix_product(mul, mul);
p = parseInt(p / 2);
}
return matrix_product(mul, s);
}
// Function to return the required count
function expectedSteps(x)
{
// Base cases
if (x == 0)
return 0;
if (x <= 6)
return 6;
// Multiplier matrix
var mul = [ [ 7 / 6, 1, 0, 0, 0, 0, 0 ],
[ 0, 0, 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 1, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 0, 0 ],
[ 0, 0, 0, 0, 0, 1, 0 ],
[ 0, 0, 0, 0, 0, 0, 1 ],
[ -1 / 6, 0, 0, 0, 0, 0, 0 ] ];
// Finding the required multiplier
// i.e mul^(X-6)
mul = mul_expo(mul, x - 6);
// Final answer
return (mul[0][0] + mul[1][0] +
mul[2][0] + mul[3][0] +
mul[4][0] + mul[5][0]) * 6;
}
// Driver code
var n = 10;
document.write(expectedSteps(n - 1));
// This code is contributed by rrrtnx
</script>
7.36111
La complejidad temporal del enfoque anterior será O(343 * log(N)) o simplemente O(log(N)) .
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA