本文共 2650 字,大约阅读时间需要 8 分钟。
public class Test09 { /** * 写一个函数,输入n,求斐波那契(Fibonacci) 数列的第n项 * @param n Fibonacci数的项数 * @return 第n项的结果 */ public static long fibonacci(int n) { // 当输入非正整数的时候返回0 if (n <= 0) { return 0; } // 输入1或者2的时候返回1 if (n == 1 || n == 2) { return 1; } // 记录前两个(第n-2个)的Fibonacci数的值 long prePre = 1; // 记录前两个(第n-1个)的Fibonacci数的值 long pre = 1; // 记录前两个(第n个)的Fibonacci数的值 long current = 2; // 求解第n个的Fibonacci数的值 for (int i = 3; i <= n ; i++) { // 求第i个的Fibonacci数的值 current = prePre + pre; // 更新记录的结果,prePre原先记录第i-2个Fibonacci数的值 // 现在记录第i-1个Fibonacci数的值 prePre = pre; // 更新记录的结果,pre原先记录第i-1个Fibonacci数的值 // 现在记录第i个Fibonacci数的值 pre = current; } // 返回所求的结果 return current; } public static void main(String[] args) { System.out.println(fibonacci(0)); System.out.println(fibonacci(1)); System.out.println(fibonacci(2)); System.out.println(fibonacci(3)); System.out.println(fibonacci(4)); System.out.println(fibonacci(5)); System.out.println(fibonacci(6)); System.out.println(fibonacci(7)); }}
public class Solution { public int JumpFloor(int target) { return JumpFloor(target, 1, 2); } public int JumpFloor(int target, int p, int q) { if (target == 1) { return 1; } if (target == 2) { return q; } return JumpFloor(target - 1, q, p + q); }}
public class Solution { //f(n)=f(1)+f(2)+...+f(n-1) //f(n)=2*f(n-1) public int JumpFloorII(int target) { if (target == 0) { return 1; } if (target == 1) { return 1; } int total = 1; while (target != 1) { total *= 2; target--; } return total; }}
抽象问题:画图,举例子!!!发现规律或者隐含的逻辑条件!
public class Solution { //尾递归 public int RectCover(int target) { return RectCover(target, 1, 2); } private int RectCover(int target, int p, int q) { if (target < 1) { return 0; } if (target == 1) { return 1; } if (target == 2) { return q; } return RectCover(target - 1, q, p + q); }}