算法学习——递归之排队购票问题
2023-02-18 16:40:25 时间
算法描述
一场球赛开始前,售票工作正在紧张的进行中.每张球票为50元,现有m+n个人排队等待购票,其中有m个人手持50元的钞票,另外n个人手持100元的钞票.假设开始售票时售票处没有零钱,求出m+n排队购票,
算法思路
定义函数f(m,n)表示m个人手持50元,n个人手持100元共有的排队种数
-
当n=0,没有手持100元的人排队,这个情况是找得开钱
f(m,0) =1
-
当m<n,(手持50元的人数小于手持100元的人数)
f(m,n)=0
-
其他情况
当第m+n个人手持100元,他之前的m+n-1个人有m个人手持50元,n-1个人手持100元,共有的排队种数为f(m,n-1)
当第m+n个人手持50元,他之前的m+n-1个人有m-1个人手持50元,n个人手持100元,共有的排队种数为f(m-1,n)
根据上述情况可得到
递归公式f(m,n)=f(m-1,n)+f(m,n-1)
递归出口n=0 f(m,0)=1
m<n f(m,n)=0
算法实现
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
scanner.close();
long temp = digui(m, n);
System.out.println(temp);
}
public static long digui(int m,int n){
if(n==0){
return 1;
}else if(m<n){
return 0;
}else{
return digui(m-1,n)+digui(m,n-1);
}
}
结果
相关文章
- Redis被问到哭?看完这篇,她站起来了……
- Redis-技术专区-帮从底层彻底吃透RDB技术原理
- Mybatis-技术专区-如何清晰的解决出现「多对一模型」和「一对多模型」的问题
- 🏆【JVM技术专区】「难点-核心-遗漏」TLAB内存分配+锁的碰撞(技术串烧)!
- 🏆【Alibaba微服务技术系列】「Dubbo3.0技术专题」回顾Dubbo2.x的技术原理和功能实现及源码分析(温故而知新)
- 【微服务技术专题】Netflix动态化配置服务-微服务配置组件变色龙Archaius
- 🏆【JVM技术专区】「虚拟机专题」JDK/JVM的新储君—GraalVM和Quarkus
- Alibaba-技术专区-RocketMQ 延迟消息实现原理和源码分析
- 【SpringBoot技术专题】「JWT技术专区」SpringSecurity整合JWT授权和认证实现
- Alibaba-技术专区-Dubbo3总体技术体系介绍及技术指南(目录)
- Alibaba-技术专区-Dubbo3总体技术体系介绍及技术指南(序章)
- SpringBoot-技术专区-用正确的姿势如何用外置tomcat配置及运行(Tomcat优化分析)
- 【SpringCloud技术专题】「原生态Fegin」打开Fegin之RPC技术的开端,你会使用原生态的Fegin吗?(下)
- 【SpringCloud技术专题】「原生态Fegin」打开Fegin之RPC技术的开端,你会使用原生态的Fegin吗?(中)
- 【SpringCloud技术专题】「原生态Fegin」打开Fegin之RPC技术的开端,你会使用原生态的Fegin吗?(上)
- 🏆(不要错过!)【CI/CD技术专题】「Jenkins实战系列」(4)jenkins+pipeline构建自动化部署
- 🏆(不要错过!)【CI/CD技术专题】「Jenkins实战系列」(3)Jenkinsfile+DockerFile实现自动部署
- 【Maven实战技巧】「插件使用专题」Maven-Assembly插件实现自定义打包
- [书单]
- MySQL-技术专题-innodb存储引擎