【Java】用递归的思想解决青蛙跳台阶问题
2021/9/29 22:12:56
本文主要是介绍【Java】用递归的思想解决青蛙跳台阶问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
青蛙跳台阶:一只青蛙一次可以跳上一级台阶,也可以跳上两级台阶。求该青蛙跳上一个n级台阶共有几种跳法
青蛙在跳的时候可以随机跳1下或者2下
- 但是若只有一个台阶的时候青蛙只能跳一下
F(1)=1 - 当剩下两级台阶的时候就会出现两种方式一次跳一级跳两次或者一次跳两级跳一次
F(2)=2 - 当有三级台阶的时候我们发现可以逆着思考这个问题,三级台阶不管前面跳的什么情况最后都只会有两种情况剩一个台阶或者两个,所以跳三级台阶的问题就变成了跳2(3-1)个台阶和跳1(3-2)个台阶的问题
F(3)= F(1)+ F(2) - 当有四级台阶的时候,最后剩一个或者两个,转换为跳3(4-1)级台阶和跳2(4-2)级台阶的问题
F(4)= F(2)+F(3) - 那么以此类推,当有n级台阶的时候就可以把问题转换为跳(n-1)级台阶和(n-2)级台阶的问题
F(n)=F(n-1)+F(n-2)
那么就形成一个一个递归的逻辑,递归出口就是当只有一级台阶的时候只有一种跳法,当有两级台阶的时候有两种跳法
public static int frogjump(int n){ if(n==0) //当没有台阶的时候返回0 { return 0; } if(n==1) //当只有一个台阶的时候只有一种跳法,返回1 { return 1; } if(n==2) //当只有两个台阶的时候有两种跳法,返回2 { return 2; } int count=frogjump(n-1)+frogjump(n-2); //当有n个台阶等于跳n-1和n-2两种台阶数量的方法之和 return count; } public static void main(String[] args){ //青蛙跳台阶问题 Scanner scanner=new Scanner(System.in); System.out.println("请输入共有几级台阶:"); int x=scanner.nextInt(); int result=frogjump(x); System.out.println(x+"级台阶共有"+result+"种跳法"); }
结果:
这篇关于【Java】用递归的思想解决青蛙跳台阶问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?