全错位排列

全错位排列是由著名数学家欧拉提出的。

最典型的问题是装错信封问题

一个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多少种?

用a、b、c,d……表示n份相应的写好的信纸,A、B、C,D……表示写着n位友人名字的信封,错装的总数为记作f(n)。

假设把a错装进B中,然后接下来我们可以分为两种情况,

第一种是b错装进了A中,那么问题就变为c,d,e…..n-2个信纸放入C,D,E……n-2个信封时完全放错时完全装错有多少种,有f(n-2)种

第二种是b错装进了除A之外的一个信封内,这个时候问题就相当于已知a错装进B中,将b,c,d,e…..n-2个信纸放入A,C,D,E……n-2个信封时,b不能放入A中,这里如果我们把A

想象成B0的话,就相当于将b,c,d,e…..n-2个信纸放入B0,C,D,E……n-2个信封时完全放错,有f(n-1)种

a错装进B中,有f(n-1)+f(n-2)种,同样a错装进C中也有f(n-1)+f(n-2)种…..

a错装进B中,有f(n-1)+f(n-2)种

a错装进C中,有f(n-1)+f(n-2)种

a错装进D中,有f(n-1)+f(n-2)种

a错装进E中,有f(n-1)+f(n-2)种

a错装进F中,有f(n-1)+f(n-2)种

所以一共有

f(n)=(n-1)(f(n-1)+f(n-2));

//C++示例代码
#include <iostream>
using namespace std;

long long getvalue(int num)
{
    if (num == 1)
    {
        return 0;
    }
    else if (num == 2)
    {
        return 1;
    }
    else if (num == 3)
    {
        return 2;
    }
    else
    {
        long long f1 = 1;
        long long f2 = 2;
        for (int i = 4; i <= num; i++)
        {
            long long t = f2;
            f2 = (i - 1)*(f1 + f2);
            f1 = t;
        }
        return f2;
    }
}

int main()
{
    int num;
    cout << "input the number of envelop with -1 to end" << endl;
    while (cin>>num)
    {
        if (num == -1)
            break;
        long long r = getvalue(num);
        cout<<"Result:" << r << endl;
    }
    return 0;
}

相关的题目有

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

假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

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

神,上帝和老天爷

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏GIS讲堂

Arcgis for JS之Cluster聚类分析的实现

在做项目的时候,碰见了这样一个问题:给地图上标注点对象,数据是从数据库来的,包含XY坐标信息的,通过graphic和graphiclayer 的方式添加到地图上...

1773
来自专栏向治洪

android动画之interpolator和typeEvaluator用法详解

Interpolator (插值器) 我们在写动画的时候为了达到某种效果往往需要设置插值器,用来真实的模拟生活中的场景。  Interpolator (插值器)...

2149
来自专栏前端知识分享

第152天:表单短标题的两端对齐

在做前端界面的时候,比如一些文字的列表或者一些表单的标题,经常是2个字,3个字,4个字的类型。

1462
来自专栏儿童编程

Python的艺术玩法——“孔雀开屏”篇

本文用Python实现一个“孔雀开屏”的效果,Python也可以这么玩。下面是源码,注释里面的是不同画面的执行代码。

1672
来自专栏HansBug's Lab

3359: [Usaco2004 Jan]矩形

3359: [Usaco2004 Jan]矩形 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 8  Solv...

3566
来自专栏向治洪

android画图之贝塞尔曲线讲解

首先对于《赛贝尔曲线》不是很了解的童鞋,请自觉白度百科、google等等... 为了方便偷懒的童鞋,这里给个《贝赛尔曲线》百科地址,以及一段话简述《贝赛尔曲线...

3027
来自专栏程序你好

CSharp代码示例每日一讲: 在GDI+中使用填充Fill方法

752
来自专栏菩提树下的杨过

Flash/Flex学习笔记(48):反向运动学(下)

先要复习一下三角函数与余弦定理: 对于直角三角形,三边长a,b,c与三个角A,B,C的关系如下: ? 正弦函数: ? 余弦函数: ? 正切函数: ? 反正切函数...

24210
来自专栏菩提树下的杨过

Silverlight:Mouse Avoiding 躲避鼠标效果

昨晚在一国外博客上(从域名后缀pl上猜想应该是波兰)看到这种效果(Mouse Avoid 躲避鼠标),是基于Flash/AS3开发的,这个示例把弹性运动,摩擦力...

2127
来自专栏Flutter&Dart

Flutter之通过AnimationController源码分析学习使用Animation

他实际上就是一个抽象类,在dart里面抽象类可继承可实现,看源码知道,他主要的一个方法就是dispose,用于规定释放资源的方法

3202

扫码关注云+社区

领取腾讯云代金券