ZJU 2494 Coins of Luck

Luck is the key to life. When I have to decide something, I will make my decision by flipping a coin. And then, I have two things to do. First, I have the decision made. Second, I go to the nearest church and donate the coin.

But there are always too many things I have to decide. For example, what should I eat today for lunch? OK, now we are talking about a decision, so let us assume that I have two kinds of food: quick-served noodle A and quick-served noodle B.

I just have bought N bowls of noodle A and N bowls of noodle B. If I have some space to make a decision (i.e. having two kinds of quick-served noodle to choose from), then I will flip a coin to decide which kind of noodle to eat.

My question is, before I eat up all 2 * N bowls of quick-served noodle, what is the mathematical expectation of the number of coins I will have to donate.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 1000) which is the number of test cases. And it will be followed by T consecutive test cases.

Each test case contains an integer N (1 <= N <= 1000).

Output

Results should be directed to standard output. The output of each test case should be a single real number, which is the mathematical expectation of the number of coins I have to donate. The result should be accurate to two digits after the fractional point.

Sample Input

```2
1
2
```

Sample Output

```1.00
2.50```
` `
`该题目的思路很明确，就是概率题，尝试了两种解法，一种是用递推，另一种是直接利用组合公式`
`递推法：`
`//solution 1`
`以P[i][j]表示状态， i代表A种面条剩下的数量，j代表B种面条的数量。`
`P[i][j] = P[i - 1][j] * 0.5 + P[i][j - 1] * 0.5 (i - 1 != 0 &&　j - 1 != 0, i为0或者j为0则为终结态）`
`Result = `
```
#include <iostream>#include <queue>#include <cmath>using namespace std;#define MAXN 1100double P[MAXN][MAXN];    double dVal;double dResult[MAXN + 100];int main(){    int iCaseTimes;    int k, i, j;    double dVal;    scanf("%d", &iCaseTimes);    for(k = 0; k < iCaseTimes; k++)    {        scanf("%d", &iNum);        dRet = 0;        P[iNum + 1][iNum] = 1;        P[iNum][iNum + 1] = 1;        for(i = iNum; i >= 0; i--)        {            for(j = iNum; j >= 0; j--)            {                if(i + 1 >= 1 && j >= 1)                    P[i][j] += P[i + 1][j] * 0.5;                if(i >= 1 && j + 1 >= 1)                    P[i][j] += P[i][j + 1] * 0.5;                if(i == 0 || j == 0)                {                    dRet += P[i][j] * (iNum * 2 - i - j);                }            }        }                printf("%.2lf\n", dRet);    }    return 0;}
```
`很明显，算上总的Case数量，这种方法的时间复杂度为O(n^3), 所以，超时是必然的`
`这时转换下思路，想想能不能一下子就把1000规模的打好表呢？在上述表示情况下，打表是不行的，因为每次进行计算的时候，都需要将P[iNum][iNum]`
`设置为概率1，所以，当直接打好1000的规模，其子问题仍然没法计算出来。`
`//solution 2`
`换一状态表示方法`
`我们令P[i][j]来代表状态，其中的i, j代表A类面条吃了i碗，B类面条吃了j碗，这样我们可以这样得到答案：`
` `
`再观察这时候的子结构，假设先计算好规模为1000的表，此时的输入为iNum，我们可以看到，到数量为iNum - 1的结果都是对的，而数量为iNum的结果`
`是错误的，因为1000大于iNum，在1000的规模下，到iNum时没有进行终结，而当单类面条吃到iNum碗时，应该是结束态，所以，我们只能利用到规模为`
`iNum - 1数量的结果，并利用其推出最后答案。`
```//solution 1 O(n^2)#include <iostream>#include <cmath>using namespace std;#define MAXN 1100double dRet[MAXN][MAXN];int main(){    int i, j;    int iNum, iCaseTimes;    double dResult;    memset(dRet, 0, sizeof(dRet));    dRet[0][0] = 1;    for(i = 0; i <= 1000; i++)    {        for(j = 0; j <= 1000; j++)        {            if(i == 0 && j == 0) continue;            if(i - 1 >= 0)                dRet[i][j] += dRet[i - 1][j] * 0.5;            if(j - 1 >= 0)                dRet[i][j] += dRet[i][j - 1] * 0.5;            //dRet[i][j] += 1;        }    }    scanf("%d", &iCaseTimes);    while(iCaseTimes--)    {        scanf("%d", &iNum);        dResult = 0;        for(i = 0; i <= iNum - 1; i++)        {            dResult += dRet[iNum - 1][i] * (iNum + i) * 0.5;        }        dResult *= 2;        printf("%.2lf\n", dResult);    }    return 0;}
```
` 假如直接利用组合公式能否计算呢？`
`因为该事件发生的概率不是等可能事件，也就是说，假设有2 *　iNum 碗面条，2 ^ (iNum + 1)并不是其样本空间，因为其中一些序列是不可能发生的`
`那么假设抛硬币事件一定发生（有点像条件概率,我具体想不明白:( ）， 那么，可以得到下面的公式：`
`总的样本空间为2^K，因为抛了K次硬币，每次两种选择；而在这长度为K的串中，最后一碗必定是固定的（肯定为吃完的那种），`
`所以只要在剩下的K - 1碗中选出iNum - 1个位置便可。乘以二代表有两类面条吃完的对称情况，乘以K是转换成期望。`
```//solution 2 O(n^2)#include <iostream>using namespace std;#define MAXN 2100double C[MAXN][MAXN - 1000];int main(){    int i, j;    memset(C, 0, sizeof(C));    C[0][0] = 0.5;    C[1][0] = 0.25;    C[1][1] = 0.25;    for(i = 2; i <= 2000; i++)    {        C[i][0] = C[i - 1][0] / 2.0;        for(j = 1; j <= 1000; j++)        {            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) / 2.0;        }    }        int iNum;    int iN;    double dRetVal;        scanf("%d", &iNum);    while(iNum--)    {        scanf("%d", &iN);        dRetVal = 0;        for(i = iN; i <= iN * 2 - 1; i++)        {            dRetVal += C[i - 1][iN - 1] * i;        }        printf("%.2lf\n", dRetVal * 2);    }    return 0;}
```
`主要的思路是将组合数进行打表，更需要注意的是将2^k次也融入到整个组合数的表中，也就是说，在利用杨辉三角进行递推的时候就将除二操作加进去。`
`这里要注意double类型的精度问题，由于题目只要求精确到小数两位，所以利用double还是可以满足的。`
`对于上述方法，虽然时间复杂度是O(n^2)，但是其空间复杂度也为O(n^2)，观察到每两个f(K)函数之间也有递推关系，我们只要计算出第一个之后，再`
`乘上一个式子，除以一个式子，就可以得到下一个值，所以，再实现一个空间复杂度更小的O(n^2)的方法：`
```
//solution 3#include <iostream>using namespace std;int main(){    int i, j;        int iNum;    int iN;    double dRetVal;    double dPreVal;    double dStartValue;        scanf("%d", &iNum);    while(iNum--)    {        scanf("%d", &iN);        dRetVal = 0;        dStartValue = 1;        //(iN - 1, iN - 1)         for(i = iN; i >= 1; i--) dStartValue /= 2.0;                dRetVal = dStartValue * iN;        dPreVal = dStartValue;        for(i = iN + 1; i <= iN * 2 - 1; i++)        {            dRetVal += (double) dPreVal * (i - 1) / (i - iN) * i / 2;            dPreVal = dPreVal * (i - 1) / ((i - iN) * 2);        }        printf("%.2lf\n", dRetVal * 2);    }    return 0;}
```
`通过对该题的解决，可以看到，概率类的题目基本上两个方向：1.直接用组合公式解决。但是这种方法容易产生精度问题，而且不一定能够简单的推出来`
`2.用递推公式解决。这种方法比较容易想清楚方法，但是面临的问题便是时间与空间的限制。`

posted on 2009-03-08 19:32 Philip85517 阅读(1052) 评论(0)  编辑 收藏 引用

 只有注册用户登录后才能发表评论。 【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

导航

 < 2024年7月 >
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

• 随笔 - 14
• 文章 - 1
• 评论 - 3
• 引用 - 0

•