必威全错位排列。发邮件。

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

前言

牛客网PAT乙级训练1020

极致登峰造极的题材是装错信封问题

题目叙述

NowCoder每天只要叫许多总人口发邮件。有同样上他发现发错了邮件,把发给A的邮件发给了B,把发给B的邮件发给了A。于是他就想,要给n个人发邮件,在每个人偏偏接到1封邮件的状况下,有多少种状态是所有人且吸纳了错误的邮件?
纵然没有丁接受属于自己的邮件。

一个总人口形容了n封不同的信及相应的n个不同的信封,他拿当下n查封信还作错了信封,问还装错信封的装法有稍许种?

输入描述

输入包含多组数据,每组数据包含一个正整数n(2≤n≤20)。

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

输出描述

对诺每一样组数,输出一个刚好整数,表示不管人接到自己邮件的种数。

一经把a错装上B中,然后连下去我们可分为两种情景,

输入例子

2
3

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

出口例子

1
2

第二种植是b错装上了除A之外的一个信封内,这个时刻问题不怕一定给已知a错装进B中,将b,c,d,e…..n-2独信纸放入A,C,D,E……n-2个信封时,b不能够放入A中,这里要我们把A

解析

马上道题是平等鸣独立的错排问题,核心在递归思想之以。
用A、B、C、D………代表写着n位友人名字的信封,a、b、c、d………表示n份相应的信奉,把n份信装错的总额记为D(n),那么n-1份信封装错的总和就是D(n-1)。
当今,假要这么平等种情景,把a错装进B中,那么对于信b有以下简单种植分法:

  1. b装入A中,这样多余的(n-2)份信和信封A、B,和信a、b就从未有过其它关联了,所以此时装错的可能性总共有D(n-2)。
  2. b不自然装入A中,那么尽管时有发生或装入A、C、D等任何除B之外的信封了,这时总共就是(n-1)种装错的可能了。
    故而对于信b来说,总共有D(n-2)+D(n-1)种装错的可能。所以最终除a之外还有(n-1)封信,所以最后的关系式如下:

D(n)=(n-1)*[D(n-1)+D(n-2)]

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

解决方案

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            long a[] = new long[n + 1];
            a[1] = 0;
            a[2] = 1;
            if (n==2){
                System.out.println(1);
            }else {
                for (int i = 3; i < n + 1; i++) {
                    a[i] = (i - 1) * (a[i - 1] + a[i - 2]);
                }
                System.out.println(a[n]);
            }
        }
    }
}

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

见微知著,上帝和天

相关文章