大家都知道斐波那契数列,现在要求输入一个正整数 n ,请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足
的数列
数据范围:
要求:空间复杂度
,时间复杂度
,本题也有时间复杂度
的解法
一个正整数n
输出一个正整数。
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,所以答案为3。
1
1
2
1
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param n int整型 * @return int整型 */ export function Fibonacci(n: number): number { // write code here //if (n <= 2) return 1; let f1 = 1; let f2 = 1; for (let i = 3; i <= n; i++) { if (f1 > f2) f2 += f1; else f1 += f2; } return Math.max(f1, f2); }