昆明学校网站建设/大兴今日头条新闻

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

n<=39

解题思路

思路1：递归
思路2：循环 

/*** 斐波那契数列* * @author admin**/
public class test09 {public static void main(String[] args) {int n = 39;System.out.println(Fibonacci3(n));}// 递归（如果输入数据很大的话，递归会占用很大的内存，可能导致栈溢出，递归会做很多重复无用的运算。//递归解题相对常用的算法如普通循环等，运行效率较低737ms）public static int Fibonacci(int n) {if (n <= 0) {return 0;}if (n == 1 || n == 2) {return 1;}return Fibonacci(n - 1) + Fibonacci(n - 2);}// 尾递归（不会导致栈溢出，尾递归其实是保存运算过程中的中间变量传递到下一个调用过程，//运算过程中只保留一个函数堆栈即可，之前的可优化删除14ms）public static int Fibonacci2(int n) {return TailFibonacci2(n, 1, 1);}public static int TailFibonacci2(int n, int ac1, int ac2) {if (n <= 0) {return 0;}if (n == 1 || n == 2) {return ac2;}return TailFibonacci2(n - 1, ac2, ac1 + ac2);}// for循环（用变量记录前两个数的值，其实也是不断递归的过程，但是for循环的效率要比递归高16ms）public static int Fibonacci3(int n) {int target = 0;if (n <= 0) {return 0;}if (n == 1) {return 1;}int one = 0;int two = 1;for (int i = 2; i <= n; i++) {target = one + two;one = two;two = target;}return target;}
}