1870.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1870 on 2006-01-15 at 00:02:26 */ 
#include <cstdio>

bool race[16] = { false };
int f[16] = { 1 };

int com(const int, int, int);

int main()
{
	int i, n, t;
	double p[16];
	
	for(i = 1; i <= 10; i++) {
		f[i] = f[i-1] * i;
		p[i] = (double)com(i, 0, 0) / f[i];
	}
	scanf("%d", &t);
	for(i = 0; i < t; i++) {
		scanf("%d", &n);
		printf("%.3lf\n", p[n]);
	}
	
	return 0;
}

int com(const int k, int p, int s)
{
	int i, x = 0;
	if(s == k/2+1) return f[k-p];
	else if(p-s == (k+1)/2) return 0;
	else {
		for(i = 0; i < k; i++)
			if(!race[i]) {
				race[i] = true;
				if(i > p) x += com(k, p+1, s+1);
				else x += com(k, p+1, s);
				race[i] = false;
			}
		return x;
	}
}