斐波那契数列

[编程题]斐波那契数列

热度指数：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

输入

输出

算法知识视频讲解

Kotlin

小林望北

import java.util.*

fun main() {
    val n = readLine()!!.toInt()
//    val n = 4
    println(fib(n))
}

private fun fib(n: Int): Int {
    // 1 1 2 3 5 8
    if (n < 1) return 0
    if (n == 1) return 1
    if (n == 2) return 1

    val dp = IntArray(n + 1)
    dp[1] = 1
    dp[2] = 1
    for (i in 3..n) {
        dp[i] = dp[i - 2] + dp[i - 1]
    }
    return dp[n]
}

发表于 2023-12-10 03:44:19 回复(0)