菲波那契数列

GitHub跳转原题关系图返回列表

用两个滚动变量迭代计算第 k 个斐波那契数。

OJ: noi_openjudge

题目 ID: ch0105-17

难度:入门

标签:递推循环python

日期: 2026-07-30 23:01

目录

  1. 题意
  2. 思路
  3. 代码
  4. Python代码
  5. C++代码
    1. 复杂度
    2. 总结

题意

数列前两项均为 1，之后每项为前两项之和，求第 kk 项。

思路

只需要保存相邻两项。每轮赋值 first, second = second, first + second，同时完成状态推进；位置为 1 时直接输出第一项。

代码

Python代码

python
position = int(input())
first = second = 1

for _ in range(position - 2):
    first, second = second, first + second

print(first if position == 1 else second)

C++代码

cpp
#include <cstdio>

int main(){
    int k;
    int a=1,b=1,c;
    int i;
    scanf("%d",&k);
    if( k==1 || k == 2){
        printf("1");
        return 0;
    }

    for (i=3;i<=k;i++){
        c = a +b;
        a = b;
        b = c;
    }
    printf("%d\n",c);
    return 0;
}

复杂度

时间复杂度为 O(k)O(k)，额外空间复杂度为 O(1)O(1)。

总结

线性递推若只依赖有限个前项，就用滚动变量替代整个数组。