समस्या
मार्कोव चेन अवस्थाओं के बीच यादृच्छिक रूप से चलती है, और अगली अवस्था केवल मौजूदा अवस्था पर निर्भर करती है। 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]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Current distribution से हर transition में probability mass भेजकर next distribution निकलती है.
संकेत 2
इसे repeated matrix-vector multiplication की तरह सोचो, एक-एक step करके.
संकेत 3
जब steps zero हों, तो starting distribution को बिना बदले return करना चाहिए.
अपेक्षित जटिलता
समय O(steps * n^2), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।