地方网站,宁波网络公司排行榜,寻找客户资源的网站,如何做个网站教程需求#xff1a; 一天一只顽猴想去从山脚爬到山顶#xff0c;途中经过一个有个N个台阶的阶梯#xff0c;但是这猴子有一个习惯#xff1a;每一次只能跳1步或跳3步#xff0c;试问猴子通过这个阶梯有多少种不同的跳跃方式#xff1f; 输入描述 输入只有一个整数N#xff…需求 一天一只顽猴想去从山脚爬到山顶途中经过一个有个N个台阶的阶梯但是这猴子有一个习惯每一次只能跳1步或跳3步试问猴子通过这个阶梯有多少种不同的跳跃方式 输入描述 输入只有一个整数N0N50此阶梯有多少个台阶。 输出描述 输出有多少种跳跃方式解决方案数。 输入 3 输出 2 输入 50 输出 122106097 分析: 上山最后一步到达第50级台阶完成上山共有f50种不同的爬法 到第50级之前位于哪一级呢无非是位于第49级上跳1级即到有f49种 或位于第48级上跳3级即到有f48种于是 f50f49f47 f49 f48f46 f48 f47f45 依次类推 以此类推一般地有递推关系 fnfn-1fn-3 n3 初始条件 f11即11 f21即211注意跳法中不允许直接跳2级 f32即311133 故此递推设计比较简单时间复杂度为On 编码 public class TestDump {public static void main(String[] args) {Scanner scannernew Scanner(System.in);System.out.print(请输入阶梯数);int numscanner.nextInt();System.out.println(showF(num));}/*** 递归算法f(n) f(n-1) f(n-3);* f(1) 1;f(2) 1;f(3) 2*/public static long showF(int n) {if (n 1 || n 2) {return 1;}if (n 3) {return 2;}return showF(n - 1) showF(n - 3);}
}效果
