专栏首页magicsoar全错位排列

全错位排列

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

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

一个人写了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 条评论
登录 后参与评论

相关文章

  • openresty源码剖析——lua代码的执行

    上一篇文章中(https://cloud.tencent.com/developer/article/1037840)我们讨论了openresty是如何加载lu...

    magicsoar
  • 《驾驭大数据》读书笔记

    花费一个礼拜的时间把驾驭大数据这本书看完了,书不是很厚,200多页。(写读书笔记又花费了我一个礼拜的时间……………) 就像前言里讲的那样,书里并没有涉及到太多余...

    magicsoar
  • HHVM源码剖析

    一、前言 hhvm源码中充满了很多C++11的新特性,并且使用了各种设计模式如工厂,模板方法等,利用智能指针包裹指针,让delete没有肆意的出现 模板,继承,...

    magicsoar
  • LeakCanary原理分析

    用户1205080
  • 彻底解决mysql字符编码问题

    一、可以通过Everything查找文件。“ Everything ”是Windows的文件名搜索引擎。

    wuweixiang
  • 深度学习——CNN(3)CNN-AlexNetCNN-GoogleNet其他网络结构

    DC童生
  • SharedPreference 的commit和apply

    SharedPreference是Android开发中经常用到的一个数据持久化类, 我们可以把一些需要持久化的数据放到一个指定的 Preference文件中,并...

    PhoenixZheng
  • Apache开启浏览器缓存、开启gizp

    ExpiresActive On ExpiresDefault "access plus 12 month" ExpiresByType text/html "...

    苦咖啡
  • Oracle如何重启mmon/mmnl进程(AWR自动采集)

    环境:Oracle 11.2.0.4 RAC 现象:sysaux空间满导致无法正常生成快照,清理空间后,手工生成快照可以成功,但是观察自动生成快照依然是不成功...

    Alfred Zhao
  • CentOS7安装openjdk、tomcat和mysql流程介绍

    首先是前戏,推荐一个远程工具Xshell和Xftp搭配使用,以下是Xshell的官网  http://www.netsarang.com/products/xs...

    庞小明

扫码关注云+社区

领取腾讯云代金券