Fibonacci数列特点
头两个元素都为1
从第三个元素起，当前元素数值为前两个元素的数值和
例如：1, 1, 2, 3, 5, 8, 13 .........
总结了四种方法生成Fibonacci数列 - 有3种是递归、有1种不使用递归
public class FibonacciUtil {
// 返回斐波那契数列第index个位置的数字
public static int fiboNum(int index) {
if(index == 1 || index == 2) {
return 1;
}else {
return fiboNum(index-1) + fiboNum(index-2);
}
}
/**
*
* @param length 斐波那契数列的长度
* @param fiboArr 保存到某个固定长度空数组中 - length与foboArr长度必须对应
* @return 返回的还是形参fiboArr对象
*/
public static int[] fibonacci(int length, int[] fiboArr) {
if(length == 1 ) {
fiboArr[0] = 1;
}else if(length == 2 ) {
fiboArr[0] = 1;
fiboArr[1] = 1;
}else {
fiboArr[length-1] = fibonacci(length-1, fiboArr)[length-2] + fibonacci(length-2, fiboArr)[length-3];
}
return fiboArr;
}
/**
*
* @param length
* @return 返回一个length长的fibonacci数组
*/
public static int[] fibonacci2(int length) {
int[] fibos = new int[length];
for(int index = 0; index<length; index++) {
fibos[index] = fiboNum(index+1);
}
return fibos;
}
/**
*
* @param maxValue 斐波那契数列最后一个元素 大于 等于该元素
* @return
*/
public static Integer[] fibonacci3(int maxValue) {
List<Integer> fiboList = new ArrayList<>();
int length = 1;
while(true) {
int fiboNum = fiboNum(length);
fiboList.add(fiboNum);
if(fiboNum >= maxValue)
break;
length++;
}
Integer[] fiboNums = new Integer[fiboList.size()];
return fiboList.toArray(fiboNums);
}
/**
* 不使用递归
* @param length
* @return 返回一个length长的fibonacci数组
*/
public static int[] fibonacci4(int length) {
int[] fiboNums = new int[length];
if(length > 0) {
fiboNums[0] = 1;
}
if(length > 1) {
fiboNums[1] = 1;
}
if(length > 2) {
int index = 2;
while(true) {
fiboNums[index] = fiboNums[index-1] + fiboNums[index-2];
if(index+1 == length)
break;
index++;
}
}
return fiboNums;
}
public static void main(String[] args) {
int[] fibonacci = fibonacci(10, new int[10]);
System.out.println(Arrays.toString(fibonacci));
int[] fibonacci2 = fibonacci2(10);
System.out.println(Arrays.toString(fibonacci2));
Integer[] fibonacci3 = fibonacci3(100);
System.out.println(Arrays.toString(fibonacci3));
int[] fibonacci4 = fibonacci4(10);
System.out.println(Arrays.toString(fibonacci4));
}
}
