首页 > 其他分享 >hdu2048递归问题

hdu2048递归问题

时间:2024-05-12 12:30:31浏览次数:20  
标签:递归 个人 hdu2048 问题 xx 牌子 import 错排

题目思路:

其实我还真没怎么看出来这个是递推(嘤嘤自己好菜哇)……不过很清楚的是我们需要求出每个人拿到的都不是自己的牌子的情况有几种,按照日常经验,如果前n个人已经做到了错排(也就是拿的都不是自己的牌子),当第n+1个人来的时候,他跟任意一个人交换后就能做到这n+1个人都实现错排,!!但是注意还有一种情况,就是前n个人并没有实现完全错排,有一个人拿的牌子是正确的,这时第n+1个人来了之后,他只要跟这个拿对了牌子的人交换也可以做到n+1个人错排,这时可以看作是n-2个人实现了错排;

所以综上,递推式就可以出来了:

f [ i ] = ( f [ i - 2 ] + f [ i - 1 ] ) * ( i - 1 ) ;
————————————————

参考链接:https://blog.csdn.net/destiny1507/article/details/81229565

 

import java.text.DecimalFormat;
import java.util.Scanner;

public class hdu2048 {
    public static long jc(int xx) {
        long yy = 1;
        if (xx==0) {
            return 1;
        }
        for (int i = 1; i <= xx; i++) {
            yy *= i;
        }
        return yy;
    }
    
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        long[] aa = new long[21];
        aa[1] = 0;
        aa[2] = 1;
        DecimalFormat df = new DecimalFormat("#.00");
        for (int i = 3; i < aa.length; i++) {
            aa[i] =(i-1)*(aa[i-1]+aa[i-2]);
        }
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            System.out.println(df.format(aa[x]*100.0/jc(x))+"%");
        }
        sc.close();
    }

}

 

标签:递归,个人,hdu2048,问题,xx,牌子,import,错排
From: https://www.cnblogs.com/xiaohuangTX/p/18187639

相关文章

  • hdu2045 递归水题
    这道题的解法就是站在涂色后的最后一块,思考前一块是怎么涂色的就可以了,比如如果最后一块的前一块是与第一块颜色不同的情况,则最后一块只有一种颜色可以涂,其方法的数目等于f(n-1),而当最后一块前面一块的颜色与第一块相同时,则倒数第三块一定与第一块的颜色不同,则涂到倒数第三块有f(n-......
  • 数据结构学习笔记-递归求解森林高度
    森林的高度递归求解问题描述:设计算法求解森林的高度【算法设计思想】两个函数,一个用于计算单个二叉树的高度,另一个用于计算二叉树森林(即一组二叉树)的最大高度。下面是对两个函数的详细解释:1.treeHeight函数这个函数用于计算单个二叉树的高度。二叉树的高度定义为从根节点到......
  • vue绑定对象,绑定的值不改变的问题
    在使用vue结合elmentui的table组件,对数组绑定,需要编辑数组里一些属性的值。我的情况是,需要在打开这个表时,根据条件插入一些对象到table里,经测试,到这里是没问题的,可以显示新插入的对象。问题在于,当我改变这些新插入对象的count字段时,发现输入数字,输入框的数字并没有改变,而在不是新......
  • tp6 递归函数使用
    publicfunctionfindLastClass($id){$classInfo=Db::name('class')->where('id',$id)->find();if($classInfo&&$classInfo['islast']==1){//如果当前记录的islast为1,直接返回return$classInfo......
  • JAVA开发使用@JsonFormat注解,日期比实际日期少一天问题
    前言最近同事反馈一个问题,说是日期保存后未发生变化。刚开始以为是字段未对应或者是未保存成功,当我去进行排查的时候发现,发现数据保存没有问题。奇了怪了。问题现象库里日期数据保存正确,但是后台返回前台页面发现不正确。排查过程刚开始怀疑是数据未保存成功,经过测试发现数据......
  • Java-线程-并发问题和ConcurrentHashMap
    0.背景在经典八股文中,我们会背:啊,hashmap是线程不安全的,concurrentHashMap是线程安全的。然后呢,又背:啊,为啥ConcurrentHashMap是安全的,因为加锁了。好好好,接着八股:啊,啥啥分段锁。本文,结合实际例子来进行分析,这他妈的到底是在叭叭啥。一切,从一个Hashmap的demo谈起。pu......
  • 困扰了一天的flask结合智谱ai langchain流式输出json问题终于解决了
    本次对接的大模型是智谱,首先想到去智谱开放平台找找有没有和langchain结合的文档: 结果还真有,就省去了谷歌的时间,但是智谱的文档只提供了非流式的示例代码,想着先拷过来跑一下再说,结果就是非流式是正常输出的,流式就遇到问题了,不管我咋配置,好像只能在控制台输出流失内容,遂去谷歌......
  • 递归+回溯解决有效括号问题
    题目描述:数字n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合例如:当n=1时,有效的括号组合['()']当n=2时,有效的括号组合['(())','()()']当n=3时,有效的括号组合有['((()))','(()())','(())()'.'()(())','()()()&......
  • 关于蓝图实现的问题
    现在蓝图子对象已经可以调用父类的函数,并且持有父对象。如何解决父类的虚函数问题,如果通过子类蓝图对象,可以调用内部Parent对象的函数而直接创造父类对象,他如何调用蓝图类,或者说他根本不支持。,也就是说蓝图里的对象c++不能访问。   而蓝图子对象要调用父类,可以两种方式 ......
  • 工作疑难问题解决4例
      记录一下工作上疑难问题解决:  一,方便的页面监控     前几天早上,负责的kettle抽取数据表的任务又报错了,早上看手机有4个未接报警电话,一看是人员表,原来昨天报表系统有个大的查询一直未查询完成,导致truncate这个人员表,无法活动meta的锁,后续执行抽取和计算的都报错......