समस्या
A Markov chain moves between states at random, and the next state depends only on the current one. transition[i][j] is the probability of moving from state i to state j, so every row sums to 1.
If p is the probability of being in each state now, the distribution one step later is:
p_next[j] = Σ over i of p[i] × transition[i][j]
Implement markov_distribution(transition, start, steps) and apply this update steps times.
Input
transition: An n × n matrix whose rows sum to 1.
start: The starting distribution (n values summing to 1).
steps: How many steps to take.
Output
Return the distribution after steps steps.
सीमाएँ
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1,000
0 ≤ each probability ≤ 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};व्याख्या
Think of sunny (0) and rainy (1) days, starting sunny. After one step: [0.9, 0.1]. After two: sunny = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 and rainy = 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};व्याख्या
This chain always switches state, so each step swaps the two probabilities. After 3 swaps: [0.75, 0.25].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
The next distribution is found by sending probability mass through every transition from the current distribution.
संकेत 2
Think of it as repeated matrix-vector multiplication, one step at a time.
संकेत 3
When steps is zero, the starting distribution should be returned unchanged.
अपेक्षित जटिलता
O(steps * n^2) time, O(n) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।