首页 > 代码库 > 洛谷P1595 信封问题

洛谷P1595 信封问题

2024-10-04 08:53:02   214人阅读

P1595 信封问题

题目描述

某人写了n封信和n个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。

输入输出格式

输入格式：

一个信封数n

输出格式：

一个整数，代表有多少种情况。

输入输出样例

输入样例#1：
样例1：2样例2：3
输出样例#1：
样例1：1样例2：2

错排公式：F(n) = (n - 1) * ( F(n - 1) + F(n - 2))

已知n,F[n - 1],F[n - 2],求F[n]
我们记x位置的元素为ax
考虑an，有n - 1种放法。对于其中放在k位置的一种放法：
ak可能有两种放法：
1、放在n位置，相当于ak与an互换，只需要剩下的n - 2个元素错拍，答案F（n - 2）
2、不放在n位置：ak不能放在n位置，又不能放在k位置，此时k位置已经确定放n了，那么我们不妨把k位置直接去掉。这样，ak就只不能放在n位置。
因为其他元素与位置不能放的对应关系不变，而an对应n位置,ak对应k位置，an放到了k上，并且已经被拿掉，那么需要确定ak和n位置的关系即可。由于前提”不放在n位置“，所以ak与n位置是不能放的对应关系。所以，所有元素与剩下的（n - 1）个位置的对应关系形成一一映射！
也就是说，相当于将(n - 1)个元素进行错排。
1、2显然加法原理，(n - 1)与1,2用乘法原理

最终：F（n） = （n - 1） * （F（n - 1） + F（n - 2））

显然F（1） = 0，F（2） = 1

 1 #include <bits/stdc++.h> 2 inline void read(int &x) 3 { 4     x = 0;char ch = getchar();char c = ch; 5     while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar(); 6     while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar(); 7     if(c == ‘-‘)x = -x; 8 } 9 //f[n]表示n个信封的情况数 f[n] = (n - 1)*(f[n - 1] + f[n - 2])10 int n;11 int a,b,c;12 int main()13 {14     read(n);15     if(n == 1)16     {17         printf("0");18         return 0;19     }20     else if(n == 2)21     {22         printf("1");23         return 0;24     }25     a = 0;b = 1;26     for(int i = 3;i <= n;i ++)27     {28         int tmp = c;29         c = (i - 1) * (a + b);30         a = b;31         b = c;32     }33     printf("%d", c);34     return 0;35 }

 

洛谷P1595 信封问题


联系
我们