Problème
Une chaîne de Markov passe d'un état à l'autre au hasard, et l'état suivant ne dépend que de l'état actuel. transition[i][j] est la probabilité de passer de l'état i à l'état j, donc chaque ligne a une somme de 1.
Si p est la probabilité d'être dans chaque état maintenant, la distribution un pas plus tard est :
p_next[j] = Σ sur i de p[i] × transition[i][j]
Implémentez markov_distribution(transition, start, steps) et appliquez cette mise à jour steps fois.
Entrée
transition : Une matrice n × n dont les lignes ont une somme de 1.
start : La distribution de départ (n valeurs de somme 1).
steps : Le nombre de pas à effectuer.
Sortie
Renvoyez la distribution après steps pas.
Contraintes
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1 000
0 ≤ chaque probabilité ≤ 1
Exemples
Entrée :
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
Sortie attendue :
expected = [0.86, 0.14]Entrée :
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}
};
Sortie attendue :
std::vector<double> expected = {0.86, 0.14};Entrée :
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}
};
Sortie attendue :
double[] expected = new double[] {0.86, 0.14};Explication
Imaginez des jours ensoleillés (0) et pluvieux (1), en partant d'un jour ensoleillé. Après un pas : [0.9, 0.1]. Après deux : ensoleillé = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 et pluvieux = 0.9 × 0.1 + 0.1 × 0.5 = 0.14.
Entrée :
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
Sortie attendue :
expected = [0.75, 0.25]Entrée :
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}
};
Sortie attendue :
std::vector<double> expected = {0.75, 0.25};Entrée :
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}
};
Sortie attendue :
double[] expected = new double[] {0.75, 0.25};Explication
Cette chaîne change toujours d'état, donc chaque pas échange les deux probabilités. Après 3 échanges : [0.75, 0.25].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
La distribution suivante s’obtient en faisant circuler la masse de probabilité à travers chaque transition depuis la distribution actuelle.
Indice 2
Voyez cela comme une multiplication matrice-vecteur répétée, un pas à la fois.
Indice 3
Quand steps vaut zéro, la distribution de départ doit être renvoyée telle quelle.
Complexité attendue
temps O(steps * n^2), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.