计蒜客 17308.Weather Patterns

350


题目



点击显/隐题目

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], 1le i,j le N$.

For the special case of a discrete, first order, Markovchain, the probabilistic description for the current state (at time $t$) and the predecessor state is $s_{t}$. Furthermore we only consider those processes being independent of time, thereby leading to the set of state transition probability $a_{ij}$ of the form: with the properties $a_{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 $1$: snow
  • State $2$: rain
  • State $3$: cloudy
  • State $4$: sunny

The matrix $A$ 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 $k$ 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 $O$ as $O = left \{ s_{1}, s_{2}, s_{3}, ... , s_{k} right \}$, and the probability of the observation sequence $O$ given the model is defined as $p(O|model)$.

Also, let the expected number of consecutive days to stayin state $i$ be $E_{i}$. Assume that the initial state probabilities $p[s_{1} = i] = 1, 1 leq i leq N$. Both $p(O|model)$ and $E_{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 $1$: $a_{11} a_{12} a_{13} a_{14}$
Line $2$: $a_{21} a_{22} a_{23} a_{34}$
Line $3$: $a_{31} a_{32} a_{33} a_{34}$
Line $4$: $a_{41} a_{42} a_{43} a_{44}$
Line $5$: $s_{1} s_{2} s_{3} ... s_{k}$
Line $6$: $s_{1} s_{2} s_{3} ... s_{l}$
Line $7$: $i$
Line $8$: $j$


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




题解


给你一个状态转移的概率矩阵,有四组询问,前两组询问按照序列顺序出现的概率;后两种询问指定状态连续出现的期望天数


显然前者就是按照顺序求一下概率的乘积
后者可以很容易推出是等比数列求和

难点在于输入和读题


代码


点击显/隐代码
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论