Problema
Una cadena de Markov pasa de un estado a otro al azar, y el siguiente estado depende solo del actual. transition[i][j] es la probabilidad de pasar del estado i al estado j, así que cada fila suma 1.
Si p es la probabilidad de estar en cada estado ahora, la distribución un paso después es:
p_next[j] = Σ sobre i de p[i] × transition[i][j]
Implementa markov_distribution(transition, start, steps) y aplica esta actualización steps veces.
Entrada
transition: Una matriz n × n cuyas filas suman 1.
start: La distribución inicial (n valores que suman 1).
steps: Cuántos pasos dar.
Salida
Devuelve la distribución después de steps pasos.
Restricciones
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1.000
0 ≤ cada probabilidad ≤ 1
Ejemplos
Entrada:
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
Salida esperada:
expected = [0.86, 0.14]Entrada:
std::vector<double> start = {1.0, 0.0};
long long steps = 2;
std::vector<std::vector<double>> transition = {
{0.9, 0.1},
{0.5, 0.5}
};
Salida esperada:
std::vector<double> expected = {0.86, 0.14};Entrada:
double[] start = new double[] {1.0, 0.0};
long steps = 2;
double[][] transition = new double[][] {
new double[] {0.9, 0.1},
new double[] {0.5, 0.5}
};
Salida esperada:
double[] expected = new double[] {0.86, 0.14};Explicación
Piensa en días soleados (0) y lluviosos (1), empezando con sol. Tras un paso: [0.9, 0.1]. Tras dos: soleado = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 y lluvioso = 0.9 × 0.1 + 0.1 × 0.5 = 0.14.
Entrada:
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
Salida esperada:
expected = [0.75, 0.25]Entrada:
std::vector<double> start = {0.25, 0.75};
long long steps = 3;
std::vector<std::vector<double>> transition = {
{0.0, 1.0},
{1.0, 0.0}
};
Salida esperada:
std::vector<double> expected = {0.75, 0.25};Entrada:
double[] start = new double[] {0.25, 0.75};
long steps = 3;
double[][] transition = new double[][] {
new double[] {0.0, 1.0},
new double[] {1.0, 0.0}
};
Salida esperada:
double[] expected = new double[] {0.75, 0.25};Explicación
Esta cadena siempre cambia de estado, así que cada paso intercambia las dos probabilidades. Tras 3 intercambios: [0.75, 0.25].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
La siguiente distribución se obtiene enviando la masa de probabilidad por cada transición desde la distribución actual.
Pista 2
Piensa en ello como una multiplicación repetida matriz-vector, un paso a la vez.
Pista 3
Cuando steps es cero, la distribución inicial debe devolverse sin cambios.
Complejidad esperada
O(steps * n^2) tiempo, O(n) espacio extra
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.