斐波那契数列

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列是一个满足 $fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.$ 的数列

数据范围： $1\leq n\leq 40$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ ，本题也有时间复杂度 $O(logn)$ 的解法

一个正整数n

输出一个正整数。

示例1

复制

复制

根据斐波那契数列的定义可知，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。

示例2

复制

复制

示例3

复制

复制