n个人排队都不站在原来的位置

简介: 题目描述:有n个人首先站成一排,请问,当n个人第二次再重新排列,每个人都不在原来的位置上,问有多少种站法。例如,原来有3个人,ABC,那么第二次每个人都不在原来的位置上有2种站法,BCA和CAB。

题目描述:有n个人首先站成一排,请问,当n个人第二次再重新排列,每个人都不在原来的位置上,问有多少种站法。例如,原来有3个人,ABC,那么第二次每个人都不在原来的位置上有2种站法,BCA和CAB。


解决思路:

  • 假设有n个人,那么我们的问题规模是 A(n),A(n) 代表的是 n 个人都不站原来的位置一共有多少种站法。令第一个人站的是非1号位置,一共是 n-1 种站法,假设第一个人站在2号位置,那么第2个人站的位置分两种:第一类是第2个人站1号位置,那么第1个人和第2个人的位置都确定了,那么剩下 n-2 个位置,问题规模变成 A(n-2),相当于第3个人不站3号位置,第4个人不站4号位置....第n个人不站 n 号位置;第二类是第2个人不战1号位置,那么问题的规模变成了 A(n-1),相当于第2个人不站1号位置,第3个人不站3号位置...第 n 个人不站 n 号位置。所以最终得到 A(n) = (n-1) * [A(n-1) + A(n-2)]。其实代码很简单,就是一个递推的过程,反倒是想不到这么做。
import java.util.*;

public class Main {

    public static int queue(int n){
        if(n <= 1)
            return 0;
        if(n == 2)
            return 1;
        int num_1 = 0, num_2 = 1, num_3 = 0;
        for(int i = 3; i <= n; i++){
            //这里是一个递推的过程
            num_3 = (i - 1) * (num_2 + num_1);
            num_1 = num_2;
            num_2 = num_3;
        }
        return num_3;
    }

    public static int fun(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        int[] arr = new int[n + 1];
        arr[1] = 0;
        arr[2] = 1;
        //用数组表示,只是很方便的显示公式效果
        //有值有下标,可以一一对应。
        for(int i = 3; i <= n; i++) {
            arr[i] = (i - 1) * (arr[i - 1] + arr[i - 2]);
        }
        return arr[n];
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println(queue(n));
    }
}

目录
相关文章
|
8月前
leetcode-2045:到达目的地的第二短时间
leetcode-2045:到达目的地的第二短时间
100 0
|
7月前
|
小程序 API
技术心得记录:微信小程序之图片频繁变化,几秒之后输出结果(适用于抽奖)
技术心得记录:微信小程序之图片频繁变化,几秒之后输出结果(适用于抽奖)
41 0
|
8月前
1207.独一无二的出现次数
1207.独一无二的出现次数
47 2
|
消息中间件 算法 Dubbo
3面美团,4面阿里,5面百度,offer照单全收,最终还是选择了字节
十月已过半,金九银十同样也临近尾声。阿嘴希望能帮助大家有效抓住面试跳槽旺季的尾巴,连夜整合了GitHub最火的大厂的面经以及相关的真题干货,同时,还有一份2021字节跳动面经笔记给大家。
|
搜索推荐 算法
B站被删除的视频,该如何找回来?
B站被删除的视频,该如何找回来?
|
API UED
推特「崩了」:不登录不让看、推文数量严格设上限,马斯克反复横跳
推特「崩了」:不登录不让看、推文数量严格设上限,马斯克反复横跳
502 0
|
Java 数据库连接 Maven
头秃了,使用@AutoConfigureBefore调整配置顺序竟没生效?
前言 如何自定义一个starter? 分享一个经典的误区 源码分析自动配置类如何排序? 准备自己的自动配置类 将自动配置类设置在spring.factories 如何指定自动配置类的执行顺序? 总结
|
缓存 NoSQL 算法
这么秀的操作我竟然到现在才了解到?合并请求~
在几年前,我就看到过有些博客写关于合并请求的文章,一开始我没有太在意,最近在看一个up讲述关于商品模块的牛X设计,为了提高高并发的处理能力,一般会用redis 自增自减来实现库存扣减,但是他采用合并扣减库存,也就是同一时间n个扣减库存会合并成一个请求,这样无疑减少了IO次数,也提高系统性能
298 1
这么秀的操作我竟然到现在才了解到?合并请求~
刷爆力扣之较大分组的位置
刷爆力扣之较大分组的位置
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等