[编程题]斐波那契数列
课程设计
1
斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 fib(x)={1x=1,2fib(x−1)+fib(x−2)x>2fib(x)=\left{ \begin{array}{rcl} 1 & {x=1,2}\ fib(x-1)+fib(x-2) &{x>2}\ \end{array} \right. f i b ( x ) = { 1 f i b ( x − 1 ) + f i b ( x − 2 ) * x = 1 , 2 x > 2* 的数列
数据范围：1≤n≤391\leq n\leq 391≤n≤39
要求：空间复杂度 O(1)O(1)O(1)，时间复杂度 O(n)O(n)O(n) ，本题也有时间复杂度 O(logn)O(logn)O(logn ) 的解法
输入描述:
一个正整数n
输出描述:
输出一个正整数。
示例1
输入
4
输出
3
说明
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为4。
示例2
输入
1
输出
1
示例3
输入
2
输出
1
-
给一个 尾递归 的解答：不是不能用递归，递归本质上是栈，可能导致栈溢出，只要避免溢出就可以了。大家不要被惯性思维所限制啊，熟悉的题目只想到了熟悉的解答，那样还是书呆子！
public class Solution { public int Fibonacci(int n) { return Fibonacci(n,0,1); } private static int Fibonacci(int n,int acc1,int acc2){ if(n==0) return 0; if(n==1) return acc2; else return Fibonacci(n - 1, acc2, acc1 + acc2); } }
发表回复