package com.ll.cst;
import java.math.BigInteger;
/**
* 测试用例:
* 功能测试(输入3,5,10)
* 边界值测试(输入0,1,2)
* 性能测试(输入较大的数40,50,100)
* @author 30140
*
*/
public class Demo01 {
public static void main(String[] args) {
Demo01 demo01 = new Demo01();
// 获取当前时间戳
long currentTimeMillis1 = System.currentTimeMillis();
// 输入100时,数据溢出,用Long类型
Long flag = demo01.Fibonacci1(100);
System.out.println("flag: "+flag);
// int flag2 = demo01.Fibonacci2(30);
// System.out.println("flag2: "+flag2);
// System.out.println(demo01.Fibonacci3(500));
// 获取计算过的当前时间戳
long currentTimeMillis2 = System.currentTimeMillis();
// 获取结果用时多少
System.out.println("递归实现用时" + (currentTimeMillis2 - currentTimeMillis1) + "毫秒");
}
/*
* 裴波那契数列:
* 从下往上计算,先根据f(0)和f(1)算出f(2),再根据f(1)和f(2)算出f(3)......以此类推
* 时间复杂度为O(n)
*/
public Long Fibonacci1(int n) {
if (n < 2)
return (long) n;
Long fibOne = 0L;
Long fibTow = 1L;
Long fbn = 0L;
for (int i = 2; i <= n; i++) {
fbn = fibOne + fibTow;
fibOne = fibTow;
fibTow = fbn;
}
return fbn;
}
/*
* 递归解法:
* 有大量的重复计算
* 时间复杂度以n的指数的方式递增
*/
public int Fibonacci2(int n) {
if(n < 2) return n;
return Fibonacci2(n-1)+Fibonacci2(n-2);
}
/**
* 解决数据溢出的问题:
* 1.使用Long类型,但输入更大的数还是会溢出
* 2.BigInteger类型的数字范围较Integer，Long类型的数字范围要大得多，它支持任意精度的整数，
* 也就是说在运算中 BigInteger 类型可以准确地表示任何大小的整数值而不会丢失任何信息
* @param n
* @return
*/
public BigInteger Fibonacci3(int n) {
// 实例化BigInteger
BigInteger bigInteger = new BigInteger(String.valueOf(n));
if (n < 2)
return BigInteger.valueOf(n);
BigInteger fibOne = BigInteger.valueOf(0);
BigInteger fibTow = BigInteger.valueOf(1);
BigInteger fbn = BigInteger.valueOf(0);
for (int i = 2; i <= n; i++) {
fbn = fibOne.add(fibTow);
fibOne = fibTow;
fibTow = fbn;
}
return fbn;
}
/**
* 青蛙跳台阶问题
* @param target
* @return
*/
public int jumpFloor(int target) {
if(target < 2) return target;
int jumpOne = 1;
int jumpTow = 1;
int Fib = 0;
for(int i=2;i<=target;i++){
Fib = jumpOne + jumpTow;
jumpOne = jumpTow;
jumpTow = Fib;
}
return Fib;
}
}