Problem
Eine Markov-Kette wechselt zufällig zwischen Zuständen, und der nächste Zustand hängt nur vom aktuellen ab. transition[i][j] ist die Wahrscheinlichkeit, von Zustand i zu Zustand j zu wechseln, also summiert sich jede Zeile zu 1.
Ist p die Wahrscheinlichkeit, jetzt in jedem Zustand zu sein, dann ist die Verteilung einen Schritt später:
p_next[j] = Σ über i von p[i] × transition[i][j]
Implementiere markov_distribution(transition, start, steps) und wende dieses Update steps-mal an.
Eingabe
transition: Eine n × n-Matrix, deren Zeilen sich zu 1 summieren.
start: Die Startverteilung (n Werte mit Summe 1).
steps: Wie viele Schritte gemacht werden.
Ausgabe
Gib die Verteilung nach steps Schritten zurück.
Einschränkungen
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1.000
0 ≤ jede Wahrscheinlichkeit ≤ 1
Beispiele
Eingabe:
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
Erwartete Ausgabe:
expected = [0.86, 0.14]Eingabe:
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}
};
Erwartete Ausgabe:
std::vector<double> expected = {0.86, 0.14};Eingabe:
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}
};
Erwartete Ausgabe:
double[] expected = new double[] {0.86, 0.14};Erläuterung
Denk an sonnige (0) und regnerische (1) Tage, beginnend mit Sonne. Nach einem Schritt: [0.9, 0.1]. Nach zwei: sonnig = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 und regnerisch = 0.9 × 0.1 + 0.1 × 0.5 = 0.14.
Eingabe:
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
Erwartete Ausgabe:
expected = [0.75, 0.25]Eingabe:
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}
};
Erwartete Ausgabe:
std::vector<double> expected = {0.75, 0.25};Eingabe:
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}
};
Erwartete Ausgabe:
double[] expected = new double[] {0.75, 0.25};Erläuterung
Diese Kette wechselt immer den Zustand, also vertauscht jeder Schritt die beiden Wahrscheinlichkeiten. Nach 3 Vertauschungen: [0.75, 0.25].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Die nächste Verteilung entsteht, indem du die Wahrscheinlichkeitsmasse von der aktuellen Verteilung durch alle Übergänge schickst.
Hinweis 2
Denk daran als wiederholte Matrix-Vektor-Multiplikation, Schritt für Schritt.
Hinweis 3
Wenn steps null ist, sollte die Startverteilung unverändert zurückgegeben werden.
Erwartete Komplexität
Zeit O(steps * n^2), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.