编程题：发邮件（错排算法）

旧城等待， 2023-07-12 08:54 1阅读 0赞

### 文章目录 ###

*   *  问题描述：
     *  解题思路：
     *  解题代码：

链接： [发邮件][Link 1]  
来源：牛客网

## 问题描述： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]

## 解题思路： ##

分析题意：就是让我们找什么情况下所有人都会收到错误的邮件。

假设a给b和c发邮件，有两种选择:
      第一种：a把给b的邮件给c,然后把给c的邮件给b（就是把他两的邮件互换），剩下N-2个人也都这么处理（就是N-2个子问题），那么就有f(n-2)种情况；
      第二种：a没有把给b的邮件给c，反而是给了其他的人，那么问题就转换成了N-1人的子问题，有f(n-1)种情况。
    
    因此我们可以得出递推公式：f（n）=(n-1)*(f(n-1)+f(n-2))  (n>=3低于三个人没法玩)

## 解题代码： ##

import java.util.Scanner;
    
    public class Main2 { 
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) { 
                int n = sc.nextInt();
                long sum = count(n);
                System.out.println(sum);
            }
    
        }
    
        //计算所有人都收不到自己的邮件的情况情况：错排算法
        private static long count(int n) { 
            if (n == 1) { 
                return 0;
            } else if (n == 2) { 
                return 1;
            } else { 
                return (n - 1) * (count(n - 1) + count(n - 2));
            }
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/95e35e7f6ad34821bc2958e37c08918b?orderByHotValue=2&page=1&onlyReference=true
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200307214745219.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4,size_16,color_FFFFFF,t_70