Problema
Uma cadeia de Markov muda de estado aleatoriamente, e o próximo estado depende apenas do atual. transition[i][j] é a probabilidade de ir do estado i para o estado j, então cada linha soma 1.
Se p é a probabilidade de estar em cada estado agora, a distribuição um passo depois é:
p_next[j] = Σ sobre i de p[i] × transition[i][j]
Implemente markov_distribution(transition, start, steps) e aplique essa atualização steps vezes.
Entrada
transition: Uma matriz n × n cujas linhas somam 1.
start: A distribuição inicial (n valores que somam 1).
steps: Quantos passos dar.
Saída
Retorne a distribuição após steps passos.
Restrições
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1.000
0 ≤ cada probabilidade ≤ 1
Exemplos
Entrada:
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
Saída 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}
};
Saída 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}
};
Saída esperada:
double[] expected = new double[] {0.86, 0.14};Explicação
Pense em dias de sol (0) e de chuva (1), começando com sol. Após um passo: [0.9, 0.1]. Após dois: sol = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 e chuva = 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]
]
Saída 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}
};
Saída 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}
};
Saída esperada:
double[] expected = new double[] {0.75, 0.25};Explicação
Esta cadeia sempre troca de estado, então cada passo troca as duas probabilidades. Após 3 trocas: [0.75, 0.25].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
A próxima distribuição é obtida enviando a massa de probabilidade por todas as transições a partir da distribuição atual.
Dica 2
Pense nisso como multiplicação repetida de matriz por vetor, um passo por vez.
Dica 3
Quando steps é zero, a distribuição inicial deve ser retornada sem mudanças.
Complexidade esperada
tempo O(steps * n^2), espaço extra O(n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.