hd acm 1465
2024-09-28 05:58:06
问题:某人写了n封信和n个信封,如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。
思路:由这道题引入错排公式:f(n)=(n-1)*[f(n-1)+f(n-2)]。
当N=1和2时,易得解~,假设F(N-1)和F(N-2)已经得到,重点分析下面的情况:
当有N封信的时候,前面N-1封信可以有N-1或者 N-2封错装
前者,对于每种错装,可从N-1封信中任意取一封和第N封错装,故=F(N-1)*(N-1)
后者简单,只能是没装错的那封和第N封交换信封,没装错的那封可以是前面N-1封中的任意一个,故= F(N-2) * (N-1)
代码:
#include <stdio.h>
#include <stdlib.h>
long long errorstage(int n);
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
printf("%lld\n",errorstage(n));
}
return 0;
}
long long errorstage(int n)
{
if(n==1) return 0;
else if(n==2) return 1;
else return (n-1)*(errorstage(n-1)+errorstage(n-2));
}
最新文章
- Knockout.js随手记(5)
- linux后台进程管理工具supervisor
- hdu2037-----------贪心, 活动安排问题
- sqlserver 字符串拼接及拆开联表查询的问题
- 数据结构及算法分析(0)&mdash;&mdash;引论
- c#执行Dos命令
- linux 防火墙 iptables实例讲解
- Python Extension Packages下载链接
- Beanstalkd使用
- Elasticsearch High Level Rest Client 发起请求的过程分析
- Java IO(四)——字符流
- 新鲜出炉的jquery fileupload 插件
- hbase运行mapreduce设置及基本数据加载方法
- libnsq编译、使用记录
- Maven项目下update maven后Eclipse报错
- suse glibcxx版本过高问题
- tomcat之日志切割
- PostgreSQL内部结构与源代码研究索引页
- ps4 如何导出切片 单个图片
- Android进程和线程(Android开发指南--译)
热门文章
- Docker: devicemapper fix for “device or resource busy” (EBUSY) Cannot start container
- MQTT--入门 续
- BMP图片的C++水印算法
- js-音乐播放器,播放|暂停|滑块的功能
- map端join
- JAVA读取文件夹大小的几种方式
- nginx proxy_pass 里的”/”
- php 模拟get和post提交方法[解决ajax跨域问题]
- JSP(Java Server Pages,即:Java服务器页面
- JVM调优- 学习笔记(转)