[递推] A. 【例题1】错排问题
A. 【例题1】错排问题
题目描述
求多少个
n
n
n个数的排列
A
A
A ，满足对于任意的
i
(
1
≤
i
≤
n
)
i(1 ≤ i ≤ n)
i(1≤i≤n) 使
A
i
≠
i
Ai ≠ i
Ai=i 。
输入格式
一个整数 。
输出格式
一个整数，表示答案。
样例
输入样例
2
输出样例
1
数据范围与提示
对于
100
%
100\%
100%的数据，
1
≤
n
≤
20
1 ≤ n ≤ 20
1≤n≤20。
题目解析
首先这道题我们考虑递推;
首先,先以
f
(
1
)
=
0
,
f
(
2
)
=
1
f(1) = 0,f(2) = 1
f(1)=0,f(2)=1.(手推
1
,
2
1,2
1,2项您总会吧)
再从
3
3
3开始进行递推.
考虑从
n
n
n个数分别放在不同的位置有
n
n
n种方法,那么不放在原位就有
n
−
1
n-1
n−1种方法.
再考虑从
n
n
n中提取一个数
l
l
l.
考虑两种情况
- 把
l
l
l放在原位上:那么除
l
l
l外的
n
−
1
n-1
n−1个数的方法就为
f
(
n
−
2
)
f(n-2)
f(n−2)
(n
−
1
n-1
n−1个数放在不同的位置,有
n
−
1
n-1
n−1种方法)
- 不把
l
l
l放在原位上:那么对于剩余的
n
−
1
n-1
n−1个数就可以放在任何位,那么就是
f
(
n
−
1
)
f(n-1)
f(n−1)种方法(同
n
n
n个数分别放在不同的位置,不放在原位的就是
l
l
l)
那么我们就很容易可以得出递推式:
f
(
i
)
=
{
f
(
1
)
=
0
f
(
2
)
=
1
f
(
i
)
=
(
n
−
1
)
∗
(
f
(
n
−
1
)
+
f
(
n
−
2
)
)
(
i
>
2
)
f(i) = \left\{\begin{matrix} &~~~~~~~f(1) = 0~~~~~~~~~f(2) = 1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \\ & f(i) = (n - 1) * (f(n-1)+f(n-2)) ~~~~~~~~~~~(i>2)\\ \end{matrix}\right.
f(i)={ f(1)=0 f(2)=1 f(i)=(n−1)∗(f(n−1)+f(n−2)) (i>2)
Code
小小的提醒:
20
20
20的数据也要开
l
o
n
g
long
long
l
o
n
g
long
long
#include <cstdio>
#include <iostream>
#define ll long long
using namespace std;
ll n, ans, a[25];
int main ()
{
scanf ("%lld", &n);
a[2] = 1;
for (int i = 3; i <= n; ++ i)
a[i] = (i - 1) * (a[i - 1] + a[i - 2]);
printf ("%lld", a[n]);
return 0;
}
最新文章
- 用Python生成测试数据
- 使用 apache2 + `mod_proxy_uwsgi` + uwsgi + upstart 部署
- invalidate()和postInvalidate()的使用与区别
- PhoneGap(二维码扫描 )
- [转载]localhost与127.0.0.1的区别
- 《The Book of CSS3》学习笔记
- 小白学数据分析----->ARPDAU的价值
- VC调用系统的调色板
- MTK6577+Android4.04编译
- android利用剪切板来实现数据的传递
- Linux kernel ‘net/key/af_key.c’信息泄露漏洞
- Python 自动化脚本学习（三）
- Tree（prime）
- Velocity脚本新手教程
- python新手 实践操作 作业
- 单台PC玩转NEUTRON（一：环境准备）
- 定制kickstart重建CentOS7.5镜像用于U盘引导安装
- volatile(一)
- Unix.Trojan.DDoS_XOR-1木马症状及清理办法
- Docker 镜像操作