我要招人

去企业版

首页 > 试题广场 >

算法题 N个人去旅行，在旅店开了N个房间，钥匙挂在大厅的

[问答题]

算法题

N个人去旅行，在旅店开了N个房间，钥匙挂在大厅的墙上，钥匙上没有标号，每人随手拿一把钥匙，请用程序实现算出所有人都拿错钥匙的可能性有几种。

天生我才至尊宝

看了别人的博客，还是觉得这些题太tm难了，https://blog.csdn.net/sxh850297968/article/details/39995499

发表于 2019-08-30 16:01:19 回复(1)

Let_Life_Stop

D（n） = ( n - 1 ) *( D( n - 1 ) + D( n - 2)). 具体的分析方法，就是假设当前要处理这n个的错排，将第一个放置到了位置k，然后剩下还有n - 1 个需要排序。然后再对k进行分类讨论。如果第k个放到第 1 个的位置，那么剩下的就是 D（n-2）。如果k不放到第1个的位置，然后我们假设第k个原来对应的位置就是第一个，然后这样就是第k个和剩下的n-2个进行乱排，然后就是D（n - 2 +1 ）。然后再乘以 n -1 ，代表 n - 1 个都有可能是这样，然后就是 D（n） = （n- 1） *（ D（n-1）+ D（n - 2 ））；

发表于 2019-08-30 17:45:01 回复(1)

D3mi

public int process(int n) {
    if(n == 0 || n == 1) {
        return 0;
    }
    if(n == 2) {
        return 1;
    }
    return process(n - 1) + process(n - 2);
}

发表于 2021-09-23 10:30:04 回复(0)

TMAIAM

#include<iostream>
using namespace std;
/*
错排递推公式：
f(n) = (n-1) * {f(n-1)+f(n-2)}
*/
int f(int n){
    if(n==0 || n==1) return 0;
    if(n==2) return 1;
    return f(n-1)+f(n-2);
}
int main(){
    int n =10;
    cout<< (n-1) * f(n);
    system("pause");
    return 0;
}

发表于 2020-10-30 15:46:12 回复(6)

平头蜗牛

n-1！

发表于 2019-08-28 18:24:05 回复(2)

offer四面八方朝我来

终于明白为何要加上f(n-2)了。

前面n-1个人，可以有一个人拿对了，因为要加入的第n个人可以用来害这个唯一拿对的人。

编辑于 2024-03-20 16:08:29 回复(0)

南屏机修组扛把子

有那么难吗各位，这是编程题啊，用暴力深搜或者全排列，去掉ai=i的情况

发表于 2022-12-09 21:08:41 回复(0)

徐风

这算是什么难度的题目啊？

我想半天，硬是想不出来。

发表于 2022-02-20 17:16:09 回复(1)

hslee_99

public Class Test{
        public static int rank(int num){
        //rank，排列
        //错排公式：Dn=[n!/e+0.5]，e，即 自然对数的底，约等于2.7，[x]为取整函数即x向下取整
        double res = Math.floor(factorial(num)/2.71 + 0.5);
        return (int)res;
    }
    public static int factorial(int num){
        //Factorial,阶乘
        if (num <= 1) return 1;
        else return num * factorial(num-1);
    }
    public static void main(String[] args){
        System.out.println(rank(3));//2
        System.out.println(rank(4));//9
        System.out.println(rank(5));//44
    }
}

发表于 2020-10-07 22:04:54 回复(0)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师恒生电子 2015 c#工程师 Java工程师

来自：恒生公司2015秋招开...

上传者：小小

难度：

9条回答 93收藏 7220浏览

算法题 N个人去旅行，在旅店开了N个房间，钥匙挂在大厅的

问题信息

热门推荐

相关试题