The Growning Pains

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 1100
double 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 1100

double 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 2100

double 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.用递推公式解决。这种方法比较容易想清楚方法，但是面临的问题便是时间与空间的限制。