题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1948
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
Author: CHEN, Zhengguang
Source: Zhejiang University Local Contest 2008
题意：
有一个人要吃A和B两种面，分别n碗；每一次用抛硬币的方式决定吃哪一种面！
求吃完面需要跑硬币的次数的期望！
PS:
dp[i][j]:表示吃了A种面 i 碗，B种面j碗的期望！
dp[i][j] = dp[i-1][j] * 0.5 + dp[i][j-1]*0.5 + 1; 因为从dp[i][j] 变为dp[i-1][j] 或者dp[i][j-1]还需要抛一次硬币！
一般来说求概率是正推，求期望是倒推的！
代码如下：（正推）
#include <cstdio>
#include <cstring>
double dp[1017][1017];
void init()
{
dp[0][0] = 0;
for(int i = 0; i <= 1000; i++)
{
dp[i][0] = 0;
dp[0][i] = 0;
}
for(int i = 1; i <= 1000; i++)
{
for(int j = 1; j <= 1000; j++)
{
dp[i][j] = dp[i-1][j]*0.5 + dp[i][j-1]*0.5+1;
}
}
}
int main()
{
int t;
init();
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
printf("%.2lf\n",dp[n][n]);
}
return 0;
}
（倒推）
代码如下：
#include <cstdio>
#include <cstring>
int n;
double dp[1017][1017];
void init()
{
memset(dp,0,sizeof(dp));
dp[1000][1000] = 1;
for(int i = 1000; i >= 0; i--)
{
for(int j = 1000; j >= 0; j--)
{
dp[i][j] = dp[i+1][j]*0.5 + dp[i][j+1]*0.5+1;
}
}
}
void cal()
{
memset(dp,0,sizeof(dp));
dp[n][n] = 1;
for(int i = n-1; i >= 0; i--)
{
for(int j = n-1; j >= 0; j--)
{
dp[i][j] = dp[i+1][j]*0.5 + dp[i][j+1]*0.5+1;
}
}
}
int main()
{
int t;
scanf("%d",&t);
init();
while(t--)
{
scanf("%d",&n);
// cal();//超时
// printf("%.2lf\n",dp[0][0]);
printf("%.2lf\n",dp[1000-n+1][1000-n+1]);
}
return 0;
}