Email: analysis of wrong arrangement

Raise questions ： one day , Five people each received a letter , Everyone has a mailbox in front of their home , But the messenger just delivered everyone's letter to someone else's mailbox when delivering the letter , ask ： How many delivery schemes are there to meet this requirement ？

• To analyze problems

When n A number element is placed in n A number position , Remember the number of staggered methods D(n)～

⒈ The first n Put two elements in one place , For example, location k, Altogether （n-1） Methods ;

⒉ Put number as k The elements of , There are two scenarios ：
1° Put it in place n, that , For the rest （n-1） Elements , Due to the first k An element is placed in position n, be left over （n-2） One element has D(n-2) Methods ;
2° The first k An element doesn't put it in position n, At this time , For this （n-1） Elements , Yes D(n-1) Methods ;.

So there is ：
D(n) = (n-1) [D(n-2) + D(n-1)]

• solve the problem

Let's take the same question of sending emails as an example , Based on the above analysis , We can get the following code ：

import java.util.Scanner;

public class Main {
    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);
        }

    }

    // Calculate the situation that everyone can't receive their own email ： Staggered algorithm 
    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));
        }
    }
}