杭电oj 2048 神、上帝以及老天爷 C语言

 从n=3开始符合要求的情况数量满足排错公式f(n)=(n-1)*(f(n-1)+f(n-2));而总共会发生的情况符合 n!;最后将符合要求的数量除以总数取百分比即为所求；

#include
 
void main()
{
	int c, i,n;
	long long nums[21],sum;
	nums[0] = nums[1] = 0, nums[2] = 1;
	for (i = 3; i <= 20; i++)
		nums[i] = (i - 1) * (nums[i - 1] + nums[i - 2]);
	while (~scanf_s("%d", &c))
	{
		while (c--)
		{
			scanf_s("%d", &n);
			sum = 2;
			for (i = 3; i <= n; i++)
				sum *= i;
			printf("%.2f%%\n", (nums[n] * 100.0) / sum);
		}
	}
}