Wrong arrangement (lottery, email)

Staggered concept ：

Encyclopedia of typology

 n An ordered element should have n! A different arrangement , If an arrangement Make all elements not in their original positions On , This arrangement is called Dislocation ; Some are called rearrangement .
  Such as ,1 2 The wrong arrangement of is the only , namely 2 1.1 2 3 The wrong arrangement is 3 1 2,2 3 1. These two can be regarded as 1 2 Dislocation ,3 Respectively with 1、2 From transposition .

 

Recursive relation derivation

To find its recurrence relation , A two-step ：

First step , Consider the n Elements , Put it in a certain position , For example, location k , Altogether n-1 Planting ;
The second step , Consider the k Elements , There are two scenarios ：

1. Put it in place n, So for division n Outside of the n-1 Elements , Due to the first k An element is placed in position n, So the rest is n-2 The staggered arrangement of elements can be , Species D(n-2) Release method ;
2. The first k Elements are not placed in position n, At this time, for this n-1 Staggered arrangement of elements , Yes D(n-1) Planting .

To sum up, we can get D(n) = (n-1) * ( D(n-2) + D(n-1) )

Specifically ,D(1) = 0, D(2) = 1
Besides ：

There are also several staggered generation algorithms ： Recursive method , If you are interested in the screening method based on dictionary order and the improved dictionary order method, you can have an in-depth understanding

 
 
 

Example

email

Cattle from — email
use A、B、C… Means three emails ,a、b、c … Express n People to send . Record the total number of misfits as
D(n). Suppose that A Wrong delivery b In the , There are two kinds of wrong installation methods that contain this error :

1. to b Sent A mail , At this time, every kind of wrong hair A->b The relationship has been established （ The rest is related to A、B、a、b irrelevant ）, due D(n - 2) Kind of wrong hair method .
2. to b send out A、B Another email , At this time, it is actually ( except A In addition to the ) n- 1 An email B、C issue ( except b Outside of the ) n - 1 personal a、c… …, Obviously, there are ways to send errors at this time D(n - 1) Kind of .

All in all A Wrong delivery b In the case of , Common wrong hair method D(n- 2)+ D(n- 1) Kind of .

A Wrong delivery c, issue d… Of n - 2 Under a mistake , There are also D(n- 1)+ D(n - 2) Kind of wrong hair method , therefore D(n) = (n-1) [ D(n-2) + D(n-1) ]
Specifically ,D(0) = 0, D(1) = 0, D(2) = 1

#include <iostream>
using namespace std;
//  Dislocation 
/* arr[1] = 0, arr[2] = 1; The recursive formula ：arr[n] = (n-1)*(arr[n-1]+arr[n-1]); */
int main()
{
    
    long long arr[22] = {
    0, 0, 1};
    for(int i = 3; i < 21; ++i)
        arr[i] = (i-1) * (arr[i-1]+arr[i-2]);

    int n;
    while(cin >> n){
    
        cout << arr[n] << endl;
    }
    return 0;
}

 
 
 

The annual meeting draw

Cattle from — The annual meeting draw

This year's annual awards are especially awesome. , But the rules for winning awards are wonderful ：

1. First , All the staff put a note with their names in the lucky draw box ;
2. When all the notes have been added , Take a note from the box ;
3. If the note drawn is written with your name , that “ congratulations , I won the prize ！”
   Now let me tell you the number of people attending the party , Please calculate the probability that no one will win the prize ？
   

Reference code ：

#include <iostream>
using namespace std;

//  Recursively calculate the number of staggered sequences 
long long Derangement(int n){
    
    if(1 == n) return 0;
    if(2 == n) return 1;
    //  The recursive formula 
    return (n-1)*(Derangement(n-2)+Derangement(n-1));
}

//  Calculate the factorial （ All possible sequence numbers ）
long long factorial(int n){
    
    long long f = 1;
    for(int i = 1; i <= n; ++i)
        f *= i;
    return f;
}

int main()
{
    
    int n;
    while(cin >> n){
    
        double res = (double)Derangement(n) / factorial(n);
        printf("%.2lf%c\n",res*100, '%');  
    }
}