#DS826001. 斐波那契数列 1
斐波那契数列 1
时间限制: 1.0 秒
空间限制: 512 MB
题目描述
定义 Fibonacci 数列:
$$fib(n) = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ fib(n - 1) + fib(n - 2), & n \ge 2 \end{cases} $$给定正整数 ,求 的值。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 ,表示共有 组数据。
接下来 行,每组数据占一行,分别包含一个正整数 。
输出格式
输出到标准输出。
共输出 行,第 行对应第 组询问所求的答案。
2
10
1000
55
517691607
子任务
对于所有数据,保证 。
提示
Chap 01 绪论,Fibonacci 数,线性递归策略。
暴力递归的复杂度为 ,可以考虑对递归过程做记忆化搜索,或者使用动态规划递推。
此外,请注意 的限制,单次运算复杂度 的算法无法通过。但是你可以将所有对应的答案进行记忆化。
Related
In following contests: