编程:跳台阶问题
程序员文章站
2022-08-21 14:54:09
题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 对于每次只跳1/2个台阶的情况来说: 1.假设第一次跳1个台阶,则剩下n-1个台阶的所有跳法数f(n-1); 2.假设第一次跳2个台阶,则剩下n-2个台阶的所有跳法数f( ......
- 题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
1 public class solution { 2 3 public static int jumpfloor(int target) { 4 if(target <=0) 5 return 0; 6 if(target ==1) 7 return 1; 8 if(target==2) 9 return 2; 10 int one = 1; 11 int two = 2; 12 int result = 0; 13 for(int i = 2; i < target; i++){ 14 result = one+ two; 15 one = two; 16 two = result; 17 } 18 return result; 19 } 20 }
对于每次只跳1/2个台阶的情况来说:
1.假设第一次跳1个台阶,则剩下n-1个台阶的所有跳法数f(n-1);
2.假设第一次跳2个台阶,则剩下n-2个台阶的所有跳法数f(n-2);
3.在此特定条件下,可以判断出符合斐波那契数列规律;
4.f(1)=1;f(2)=2;以此进行f(n)=f(n-1)+f(n-2)的计算;
- 题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class solution { public int jumpfloorii(int target) { if(target<1) return 0; if(target==1) return 1; int num=0; for(int i=1;i<target;i++) { num+=jumpfloorii(target-i); } return num+1; } }
- 整体思路与第一个问题一致:将f(n)的问题转化为f(n-1)、f(n-2)……的问题
- 本题采取递归方法;
- 返回num+1的问题尚待补充;
上一篇: Spring事务管理