Цепь Маркова случайно переходит между состояниями, и следующее состояние зависит только от текущего. transition[i][j] — вероятность перейти из состояния i в состояние j, поэтому сумма каждой строки равна 1.
Если p — вероятности находиться в каждом состоянии сейчас, то распределение через один шаг:
p_next[j] = Σ по i от p[i] × transition[i][j]
Реализуйте markov_distribution(transition, start, steps) и примените это обновление steps раз.
Входные данные
transition: Матрица n × n, сумма каждой строки которой равна 1.
start: Начальное распределение (n значений с суммой 1).
steps: Сколько шагов сделать.
Выходные данные
Верните распределение после steps шагов.
Ограничения
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1 000
0 ≤ каждая вероятность ≤ 1
Примеры
Ввод:
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
Ожидаемый вывод:
expected = [0.86, 0.14]Ввод:
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}
};
Ожидаемый вывод:
std::vector<double> expected = {0.86, 0.14};Ввод:
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}
};
Ожидаемый вывод:
double[] expected = new double[] {0.86, 0.14};Пояснение
Представьте солнечные (0) и дождливые (1) дни, начиная с солнечного. После одного шага: [0.9, 0.1]. После двух: солнечно = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 и дождливо = 0.9 × 0.1 + 0.1 × 0.5 = 0.14.
Ввод:
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
Ожидаемый вывод:
expected = [0.75, 0.25]Ввод:
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}
};
Ожидаемый вывод:
std::vector<double> expected = {0.75, 0.25};Ввод:
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}
};
Ожидаемый вывод:
double[] expected = new double[] {0.75, 0.25};Пояснение
Эта цепь всегда меняет состояние, поэтому каждый шаг меняет две вероятности местами. После 3 обменов: [0.75, 0.25].
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.