这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% fold 点击显/隐题目 %}
Consider a system which is described at any time as being in one of a set of $N$ distinct states, $1,2,3,...,N$. We denote the time instants associated with state changes as $t = 1,2,...$, and the actual state at time $t$ as $a\_{ij} = p = [s\_{i}=j\ |\ s\_{i-1}=i], 1\le i,j \le N$.
For the special case of a discrete, first order, Markovchain, the probabilistic description for the current state (at time tt) and the predecessor state is s_ts\_{t}. Furthermore we only consider those processes being independent of time, thereby leading to the set of state transition probability a_ija\_{ij} of the form: with the properties a_ij≥0a\_{ij} \geq 0 and $\sum_{i=1}^{N} A_{ij} = 1 $.
The stochastic process can be called an observable Markovmodel. Now, let us consider the problem of a simple 4-state Markov model of weather. We assume that once a day (e.g., at noon), the weather is observed as being one of the following:
- State 11: snow
- State 22: rain
- State 33: cloudy
- State 44: sunny
The matrix AA of state transition probabilities is:
$A = {a_{ij}}= \begin{Bmatrix} a_{11}& a_{12}& a_{13}&a_{14} \\
a_{21}&a_{22}&a_{23}&a_{24} \\
a_{31}&a_{32}&a_{33}&a_{34} \\
a_{41}&a_{42}&a_{43}&a_{44}
\end{Bmatrix}$
Given the model, several interestingquestions about weather patterns over time can be asked (and answered). We canask the question: what is the probability (according to the given model) thatthe weather for the next kk days willbe? Another interesting question we can ask: given that the model is in a knownstate, what is the expected number of consecutive days to stay in that state?Let us define the observation sequence OO as O = \left \\{ s\_{1}, s\_{2}, s\_{3}, ... , s\_{k} \right \\}, and the probability of the observation sequence OO given the model is defined as p(O∣model)p(O|model).
Also, let the expected number of consecutive days to stayin state ii be E_iE\_{i}. Assume that the initial state probabilities p[s_1=i]=1,1≤i≤Np[s\_{1} = i] = 1, 1 \leq i \leq N. Both p(O∣model)p(O|model) and E_iE\_{i} are real numbers.
Line $1$~$4$ for the state transition probabilities. Line $5$ for the observation sequence $O\_{1}$, and line $6$ for the observation sequence $O\_{2}$. Line $7$ and line $8$ for the states of interest to find the expected number of consecutive days to stay in these states.
Line 11: a_11 a_12 a_13 a_14a\_{11}\ a\_{12}\ a\_{13}\ a\_{14}
Line 22: a_21 a_22 a_23 a_34a\_{21}\ a\_{22}\ a\_{23}\ a\_{34}
Line 33: a_31 a_32 a_33 a_34a\_{31}\ a\_{32}\ a\_{33}\ a\_{34}
Line 44: a_41 a_42 a_43 a_44a\_{41}\ a\_{42}\ a\_{43}\ a\_{44}
Line 55: s_1 s_2 s_3 ... s_ks\_{1}\ s\_{2}\ s\_{3}\ ...\ s\_{k}
Line 66: s_1 s_2 s_3 ... s_ls\_{1}\ s\_{2}\ s\_{3}\ ...\ s\_{l}
Line 77: ii
Line 88: jj
Line $1$ and line $2$ are used to show the probabilities of the observation sequences $O\_{1}$ and $O\_{2}$ respectively. Line $3$ and line $4$ are for the expected number of consecutive days to stay in states $i$ and $j$ respectively. Line $1$: $p[O\_{1} | model]$ Line $2$: $p[O\_{2} | model]$ Line $3$: $E\_{i}$ Line $4$: $E\_{j}$ Please be reminded that the floating number should accurate to $10^{-8}$.
0.4 0.3 0.2 0.1 0.3 0.3 0.3 0.1 0.1 0.1 0.6 0.2 0.1 0.2 0.2 0.5 4 4 3 2 2 1 1 3 3 2 1 1 1 3 3 4 3 4
0.00115200 2.50000000 2.00000000
题解
给你一个状态转移的概率矩阵，有四组询问，前两组询问按照序列顺序出现的概率；后两种询问指定状态连续出现的期望天数
显然前者就是按照顺序求一下概率的乘积
后者可以很容易推出是等比数列求和
难点在于输入和读题
代码
{% fold 点击显/隐代码 %}```cpp Weather Patterns https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
#include
#include
using namespace std;
double p[4][4];
int O[105];
double calc1() {
string s;
getline(cin, s);
stringstream ss(s);
int lst = -1, ths = -1;
double ans = 1.0;
while (ss >> ths) {
if (lst != -1)
ans *= p[lst - 1][ths - 1];
lst = ths;
}
return ans;
}
double calc2() {
int t;
cin >> t;
double pp = p[t - 1][t - 1];
return 1.0 + pp / (1 - pp);
}
int main() {
//cin.tie(0);
//cin.sync_with_stdio(false);
for (int i = 0; i < 4; ++i)
for (int j = 0; j < 4; ++j)
cin >> p[i][j];
getchar();
cout << fixed << setprecision(8) << calc1() << endl;
cout << fixed << setprecision(8) << calc1() << endl;
cout << fixed << setprecision(8) << calc2() << endl;
cout << fixed << setprecision(8) << calc2() << endl;
return 0;
}
{% endfold %}