Problema
Una catena di Markov si sposta a caso tra gli stati, e lo stato successivo dipende solo da quello attuale. transition[i][j] è la probabilità di passare dallo stato i allo stato j, quindi ogni riga ha somma 1.
Se p è la probabilità di trovarsi ora in ciascuno stato, la distribuzione un passo dopo è:
p_next[j] = Σ su i di p[i] × transition[i][j]
Implementa markov_distribution(transition, start, steps) e applica questo aggiornamento steps volte.
Input
transition: Una matrice n × n le cui righe hanno somma 1.
start: La distribuzione iniziale (n valori con somma 1).
steps: Quanti passi fare.
Output
Restituisci la distribuzione dopo steps passi.
Vincoli
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1.000
0 ≤ ogni probabilità ≤ 1
Esempi
Input:
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
Output atteso:
expected = [0.86, 0.14]Input:
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}
};
Output atteso:
std::vector<double> expected = {0.86, 0.14};Input:
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}
};
Output atteso:
double[] expected = new double[] {0.86, 0.14};Spiegazione
Pensa a giorni di sole (0) e di pioggia (1), partendo dal sole. Dopo un passo: [0.9, 0.1]. Dopo due: sole = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 e pioggia = 0.9 × 0.1 + 0.1 × 0.5 = 0.14.
Input:
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
Output atteso:
expected = [0.75, 0.25]Input:
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}
};
Output atteso:
std::vector<double> expected = {0.75, 0.25};Input:
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}
};
Output atteso:
double[] expected = new double[] {0.75, 0.25};Spiegazione
Questa catena cambia sempre stato, quindi ogni passo scambia le due probabilità. Dopo 3 scambi: [0.75, 0.25].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
La distribuzione successiva si ottiene distribuendo la massa di probabilità attraverso ogni transizione dalla distribuzione corrente.
Suggerimento 2
Pensa a una moltiplicazione matrice-vettore ripetuta, un passo alla volta.
Suggerimento 3
Quando steps è zero, la distribuzione iniziale va restituita invariata.
Complessità attesa
tempo O(steps * n^2), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.