首页 > ACM题库 > HDU-杭电 > hdu 2407 Knots-数论应用-[解题报告]C++
2014
01-26

hdu 2407 Knots-数论应用-[解题报告]C++

Knots

问题描述 :

An even number N of strands are stuck through a wall. On one side of the wall, a girl ties N/2 knots between disjoint pairs of strands. On the other side of the wall, the girl’s groom-to-be also ties N/2 knots between disjoint pairs of strands. You are to find the probability that the knotted strands form one big loop (in which case the couple will be allowed to marry).

For example, suppose that N = 4 and you number the strands 1, 2, 3, 4. Also suppose that the girl has created the following pairs of strands by tying knots: {(1, 4), (2,3)}. Then the groom-to-be has two choices for tying the knots on his side: {(1,2), {3,4)} or {(1,3), (2,4)}.

输入:

The input file consists of one or more lines. Each line of the input file contains a positive even integer, less than or equal to 100. This integer represents the number of strands in the wall.

输出:

The input file consists of one or more lines. Each line of the input file contains a positive even integer, less than or equal to 100. This integer represents the number of strands in the wall.

样例输入:

4
20

样例输出:

0.66667
0.28377

//公式为:((n-2)*(n-4)*(n-6)*(n-8)*(n-10)*........)/((n-1)*(n-3)*(n-5)*(n-7)*(n-9)*........)
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i;
        double ans=1.0;
        for(i=2;i<=n-2;i+=2)
            ans*=(double)i/(double)(i+1);
        printf("%.5lf/n",ans);
    }
    return 0;
}

解题转自:http://blog.csdn.net/scnujack/article/details/6263795