斐波那契数列

[编程题]斐波那契数列

热度指数：17892 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

大家都知道斐波那契数列，现在要求输入一个正整数 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。

输出描述:

输出斐波那契数列中第 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

输入

输出

算法知识视频讲解

Python3

牛客418032972号

a = int(input())

a = int(input())

def fib(a):
    q = 0
    s = 0
    p = 1
    if a <= 1:
        return a
    else:
        for i in range(1,a+1):
            s = p+q
            q = p
            p = s 
        return q
print(fib(a))

def fib(a):

q = 0

s = 0

p = 1

if a <= 1:

return a

else:

for i in range(1,a+1):

s = p+q

q = p

p = s

return q