HDOJ 2048 神、上帝以及老天爷

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2048

这里用到了错排公式。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 // Author: Tanky Woo
// HDOJ: 2048
#include <iostream>
using namespace std;
__int64 fib[22];
__int64 pala[22];
int nCases;
int main()
{
	pala[1] = 0;
	pala[2] = 1;
	fib[1] = 1;
	fib[2] = 2;
	for(int i = 3; i < 22; ++i)
	{
		pala[i] = (i-1)*(pala[i-1]+pala[i-2]);
		fib[i] = fib[i-1]*i;
	}
	scanf("%d", &nCases);
	int n;
	while(nCases--)
	{
		scanf("%d", &n);
		printf("%.2lf%%\n", ((double)pala[n])/fib[n]*100.0);
	}
	return 0;
}

===================================================

错排公式:

pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?
  这个问题推广一下,就是错排问题: n个有序的元素应有n!种不同的排列。如若一个排列式的所有的元素都不在原来的位置上,则称这个排列为错排。
  下面用递推的方法推导错排公式:
  当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
  第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
  第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;
  综上得到
  M(n)=(n-1)[M(n-2)+M(n-1)]
  特殊地,M(1)=0,M(2)=1

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注