首页 > 代码库 > 浅析错排问题

浅析错排问题

2024-08-07 12:11:21   221人阅读

定义：n个有序的元素应有n！种不同的排列。如果一个排列使得所有的元素都不在原来的位置上，则称这个排列为错排。任给一个n，求出1，2，3，。。。，n的错排个数D为多少，并且给出所有的错排方案

推理：


第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；

第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；
so：
D(n)=(n-1)*[D(n-1)+D(n-2)];
D(1)=0,D(2)=1
e.g

Oh, my God!

时间限制：1000 ms  |  内存限制：65535 KB
难度：2
描述
In order to happy everyone, organizer HRW held an open up partythere have specific requirements for this activity is this:
First of all, all person in the party will have to write a note to his name into the box;Then, after all the note added is completed, each taking a note from the box;Finally, if made note of your name, then "Congratulations, won the party!"
Oh, my God!
Now to the question, you can calculate the probability of this happening?Don‘t count? Don‘t you want said by others as a  DouBi?!  AC it！
输入
Input file contains several test cases. Each test case consists of a integer numbers n on a line(one≤n≤ten ).The last test case is followed by a line that contains one zeroes. This line must not be processed.
输出
print the the probability
See the following example.
样例输入
2
3
0
样例输出
Case [1]: 50.00%.
Case [2]: 33.33%.
提示
要用到错排公式，计算所有人都抽到自己名字的概率
来源
原创
上传者
ACM_贺荣伟
题目翻译：首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
然后，待所有字条加入完毕，每人从箱中取一个字条；
最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”
求计算一下发生这种情况的概率吗？
思路：其实就错排公式的运用
p=D（n）/n!;
#include<stdio.h>
int main()
{
    double a[55];
    double b[55];
    a[0]=1;
    for(int i=1;i<=22;i++)
        a[i]=a[i-1]*i;
    b[1]=0;
    b[2]=1;
    b[3]=2;
    for(int i=4;i<=22;i++)
        b[i]=(i-1)*(b[i-1]+b[i-2]);
        int n,d=1;
    while(~scanf("%d",&n),n)
    {
        printf("Case [%d]: ",d++);
        if(n==1)
            printf("100.00%%.\n");
        else
        {
            printf("%.2lf%%.\n",100*b[n]/a[n]);
        }
    }
}


浅析错排问题


联系
我们