京东2016算法工程师笔试题
有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，请问小明登上这段楼梯有多少种不同的走法?()
A：2345 B:3261 C:5768 D:6843 这是京东的一道算法工程师笔试题，我们可以很容易想到，直接解这道题不好做，我花了一个上午找到一个思路（非算法）：通过不熟来算，最多15步（每步一级），最少5步（每步3级），就是说有5到15就是11种步数可能。每种步数分别对应几种情况，再把情况通过排列组合的方法算算出来。
--------------------------------------------------------------------------------
后来上网查了查结果是5768,我的结果不对，但是我的思路是没有错的。并且找到了简单的方法，就是斐波那契数列.
斐波那契数列是有规律的，两个数相加和为第三个数，如下：
1 1 2 3 5 8 13 21..........
回到题目中，假设小明开始在0级台阶上，，抛开一脚跨几级不管，到第一级只有1种方法（一脚一步），到第二级只有2种方法（一步两级或则一步一级再一步一级），到第三极只有4种方法（一步三级，一步一级一步2级，一步两级一步1级，一步一级一步一级一步一级），一次类推到4级有种方法。
f(n)=f(n-1)+f(n-2)+f(n-3)
1 2 4 7 ........就是斐波那契数列
既然知道了这个数列了，怎么算呢？
下面用编程的方式解出来：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 # 代码如下： /** * 斐波那契数列 * Created by tengxing on 17-2-6. */ public static void main(String[] args){ int f1 = 1; int f2 = 2; int f3 = 4; int result = 0; for(int i = 4;i<=15;i++){ result = f1+f2+f3; f1 = f2; f2 = f3; f3 = result; } System.out.println(result); } 输出结果为：5768一个有趣的问题：有一个人第一月底时在一间房子里放了一对刚出生的小兔，小兔一个月后能长成大兔，再过一个月便能生下一对小兔，次后每个月生一对小兔。如果不发生死亡，那么到年底这个人有多少对兔子？
这就是典型的斐波那契数列。1 1 2 3 5 .......
下面是java三种方式打印斐波那契数列前20
/** * 斐波那契数列测试 * Created by tengxing on 17-2-6. */ public class FibonacciTest { public static void main(String[] args) { var(); arr(); System.out.println("\n斐波那契数列前20项为："); for (int j = 1; j <= 20; j++) { System.out.print(getFibo(j) + "\t"); if (j % 5 == 0) System.out.println(); } } //定义三个变量方法 public static void var(){ int a=1, b=1, c=0; System.out.println("斐波那契数列前20项为："); System.out.print(a + "\t" + b + "\t"); for (int i = 1; i <= 18; i++) { c = a + b; a = b; b = c; System.out.print(c + "\t"); if ((i + 2) % 5 == 0) System.out.println(); } } //定义数组方法 public static void arr(){ int arr[] = new int[20]; arr[0] = arr[1] = 1; for (int i = 2; i < arr.length; i++) { arr[i] = arr[i - 1] + arr[i - 2]; } System.out.println("斐波那契数列的前20项如下所示："); for (int i = 0; i < arr.length; i++) { if (i % 5 == 0) System.out.println(); System.out.print(arr[i]+"\t"); } } //递归方法 private static int getFibo(int i) { if (i == 1 || i == 2) return 1; else return getFibo(i - 1) + getFibo(i - 2); } }
