首页 > 代码库 > UVA - 12024 Hats (错排问题)
UVA - 12024 Hats (错排问题)
Description
F- Hats |
Background
John Hatman, the honest cloakroom attendant of the RoyalTheatre of London, would like to know the solution to the followingproblem.
TheProblem
Whenthe show finishes, all spectators in the theatre are in a hurry to see the Final of the UEFAChampionship. So, they run to the cloakroom to take their hats back.
Some of them take a wrong hat. But, how likely is thateveryone take a wrong hat?
TheInput
The first lineof the input contains an integer, t,indicating the number of test cases. For each test case, one lineappears, that contains anumbern, 2<=n<=12,representing the number of people and hats.
TheOutput
For each test case, the output should contain asingle line with the number representing the number of favourable cases(i.e., the number of cases where all people take a wrong hat),followed by a bar, "/", and followed by a number representing thetotal number of possible cases.
SampleInput
3 2 3 4
SampleOutput
1/2 2/6 9/24 题意:求每个人拿走不是自己帽子的可能思路:经典的错排问题:当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用D(n)表示,那么D(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;第二步,放编号为k的元素,这时有两种情况:⑴把它放到位置n,那么,对于剩下的n-1个元素,由于第k个元素放到了位置n,剩下n-2个元素就有D(n-2)种方法;⑵第k个元素不把它放到位置n,这时,对于这n-1个元素,有D(n-1)种方法;综上得到D(n) = (n-1) [D(n-2) + D(n-1)]特殊地,D(1) = 0, D(2) = 1.#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> typedef long long ll; using namespace std; const int maxn = 15; ll num1[maxn], num2[maxn]; ll n; void init() { num1[1] = 0; num1[2] = 1; num2[1] = 1; num2[2] = 2; for (int i = 3; i < maxn; i++) { num1[i] = (i-1) * (num1[i-2] + num1[i-1]); num2[i] = num2[i-1] * i; } } int main() { init(); int t; scanf("%d", &t); while (t--) { scanf("%lld", &n); printf("%lld/%lld\n", num1[n], num2[n]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。