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