Uva557 Burger

题目：

When Mr. and Mrs. Clinton’s twin sons Ben and Bill had their tenth birthday, the party was held at the McDonald’s restaurant at South Broadway 202, New York. There were 20 kids at the party, including Ben and Bill. Ronald McDonald had made 10 hamburgers and 10 cheeseburgers and when he served the kids he started with the girl directly sitting left of Bill. Ben was sitting to the right of Bill. Ronald flipped a (fair) coin to decide if the girl should have a hamburger or a cheeseburger, head for hamburger, tail for cheeseburger. He repeated this procedure with all the other 17 kids before serving Ben and Bill last. Though, when coming to Ben he didn’t have to flip the coin anymore because there were no cheeseburgers left, only 2 hamburgers.
Ronald McDonald was quite surprised this happened, so he would like to know what the probability is of this kind of events. Calculate the probability that Ben and Bill will get the same type of burger using the procedure described above. Ronald McDonald always grills the same number of hamburgers and cheeseburgers.
Input
The first line of the input-file contains the number of problems n , followed by n times: a line with an even number [2,4,6,...,100000], which indicates the number of guests present at the party including Ben and Bill.
Output
The output consists of n lines with on each line the probability (4 decimals precise) that Ben and Bill get the same type of burger.
Note: a variance of ±0.0001 is allowed in the output due to rounding differences.
Sample Input
3
6
10
256
Sample Output
0.6250
0.7266
0.9500

题意：
有n个人参加Ben和Bill的聚会（包括Ben和Bill），一共有n块汉堡，平均分成两种类型（n为偶数）。Ben和Bill坐最右边，然后从最左边的位置开始每人轮流抛硬币决定吃哪一种。如果剩余的汉堡只有一种类型则无需再抛。问最终Ben和Bill吃同一种汉堡的概率。
这道题可以用对立事件来算，因为如果Ben和Bill吃的汉堡是不同类型，则之前所有的人都肯定抛过硬币且平分吃两种汉堡，因此前面(n-2)个人肯定有(n-2) / 2即((n / 2) - 1)个人吃同一种汉堡，另一半吃另一种汉堡，且硬币为正反两面的概率都是1 / 2，因此对立事件发生的概率为p = (1 / 2) ^ (n - 2) * C(n - 2, (n / 2) - 1)，进而最终结果为1 - p.
但进一步通过将部分对立事件的值比较我们可以发现一个递推公式：p[i+1] = (1 - 1 / (2 * i)) * p[i].

参考代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iomanip>
using namespace std;
const int N = 50000+10;//n / 2;

vector<double> v;

void dabiao() {
    v.push_back(1);//v[0];
    v.push_back(1);//v[1];
    for (int i = 2;i < N;++i) {
        double num = (1 - 1.0 / (2 * (i - 1))) * v[i-1];
        v.push_back(num);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    dabiao();
    //for (int i = 1;i <= 10;++i) {
    //  cout << v[i] << endl;
    //}
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        double ans = 1 - v[n / 2];
        cout << fixed << setprecision(4) << ans << endl;
    }
    return 0;
}