首页 > 试题广场 >

斐波那契数列

[编程题]斐波那契数列

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

菲波那契数列是指这样的数列：数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数K，要求菲波那契数列中第k个数是多少。

输入描述:

输入一行，包含一个正整数k。(0<k<47)

输出描述:

输出一行，包含一个正整数，表示菲波那契数列中第k个数的大小

示例1

输入

输出

算法知识视频讲解

Python

华科平凡

python3解法：

res = [1, 1]
for i in range(int(input()) - 2):
    res.append(res[-1] + res[-2])
print(res[-1])

编辑于 2019-02-23 10:35:14 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int k;
    cin>>k;
    int a[k];
    if(k<3)
    {
        cout<<1<<endl;
        return 0;
    }
    a[0]=a[1]=1;
    for(int i=2;i<k;i++)
        a[i]=a[i-2]+a[i-1];
    cout<<a[k-1]<<endl;
    return 0;
}

发表于 2019-06-26 20:06:34 回复(0)

呼叫-鲸鱼船长

#include <stdio.h>
#include <stdlib.h>

int Fbi(int i)
{
    if(i<2)
        return i == 0 ? 0 :1;
    return Fbi(i-1) +Fbi(i-2);
}

int main()
{
    int k;
    scanf("%d\n",&k);
    printf("%d\n",Fbi(k));
    return 0;
}

发表于 2019-04-11 19:01:42 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int k;     long long f[47] = {0,1};     for(int i=2;i<47;i++)         f[i] = f[i-1] + f[i-2];     while(cin>>k)          cout<<f[k]<<endl;     return 0;
}

发表于 2019-01-23 01:36:13 回复(0)

牛客332052002号

下面是我的代码：




k=input('');%matlab(Octave)的代码,读入控制台的数据，（这个地方我整了大概2天，因为matlab中很少用到这种方式）
a=1;
b=1;
c=0;
i=1;
if k<=2
    fprintf('%d',a);
end
while i<k-1
     c=a+b;
     a=b;
     b=c;
     i=i+1;
end
fprintf('%d',c);%这个地方的输出是为了和题目的要求一样，用disp输出的话会有格式错误，如果用disp和sprintf同时使用可以

发表于 2020-07-23 11:08:44 回复(0)

JavaScript Node

SualLuhn

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        function fib(n){
            if(n<3){
                return 1;
            }
            let a = 1,b=1;
            let Fn = 0;
            for(let i = 3; i <= n; i++){
                Fn = a+b;
                a = b;
                b = Fn;
            }
            return Fn;

        }

        console.log(fib(Number(line.trim())));
    }
}()

发表于 2023-07-25 12:54:59 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var k int
    fmt.Scan(&k)
    if k<3{
        fmt.Print(1)
    }else{
        a,b,c:=1,1,2
        for i:=4;i<=k;i++{
            a=b
            b=c
            c=a+b
        }
        fmt.Print(c)
    }
}

发表于 2023-03-18 01:39:29 回复(0)

Python

风花月下

a=b=1
for _ in range(2,int(input())):
    b,a=a+b,b
print(b)

#由于只需要输出第n个数，所有并不需要将前面的数都保存在数组里，只需要记住最后两个数即可。

编辑于 2020-07-31 22:26:00 回复(0)

牛客116930966号

这个题我太会了忍不住分享

#include<iostream>
using namespace std;
int main()
{
    int a[47],k;
    cin>>k;
    for(int i=2;i<=k;i++)
    {
        a[0]=1;
        a[1]=1;
        a[i]=a[i-1]+a[i-2];
    }
    cout<<a[k-1]<<endl;
}

发表于 2020-07-23 16:42:28 回复(0)

严格要求自己

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        System.out.println(fbnq(Integer.parseInt(s)));
    }

    public static int fbnq(int s) {
        if (s <= 2) return 1;
        return fbnq(s - 1) + fbnq(s - 2);
    }
}

编辑于 2020-07-10 22:34:55 回复(0)

windbells

发表于 2020-05-21 19:52:10 回复(0)

C/C++

奋斗之路不堵车

链接：https://www.nowcoder.com/questionTerminal/c245af6cfdce49ceb5435f649ee14f89
来源：牛客网

菲波那契数列:

1.非递归解法：

#include<iostream>
using namespace std;
int main()
{
int k;
while(cin>>k){
int a1=1,a2=1;
if(k==1 && k==2){
cout<<"1"<<endl;
}
else if(k>2){
int temp;
for(int i=2;i<k;i++){
temp=a1+a2;
a1=a2;
a2=temp;
}
cout<<temp<<endl;
}
}
return 0;
}

2.递归解法：

#include<iostream>
using namespace std;
int Fibonacci(int k);
int main()
{
int k;
while(cin>>k){
cout<<Fibonacci(k)<<endl;
}
return 0;
}
int Fibonacci(int k)
{
if(k==1 || k==2){
return 1;
}
else{
return Fibonacci(k-1)+Fibonacci(k-2);
}
}

总结：递归方法代码短，非递归代码相对较长，非递归方法运行速度快，占用内存少，递归方法运行速度慢。

发表于 2019-09-17 20:33:52 回复(0)

秃头闪闪亮

#include <stdio.h>

int main()
{
    int k,i;
    scanf("%d",&k);
    int a[k];
    a[0]=1;
    a[1]=1;
    if(k==1||k==2)
        printf("1\n");
    else
    {
        for(i=2;i<k;i++)
        {
            a[i]=a[i-1]+a[i-2];
        }
        printf("%d",a[k-1]);
    }
    return 0;
}

发表于 2019-09-17 01:05:07 回复(0)

1456

我有点懵，你们用递归求斐波那契数列？

发表于 2019-08-10 17:08:44 回复(0)

yang20180518

import java.util.Scanner;
public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //System.out.println("请输入一个整数(0<k<47):")；
        int k = sc.nextInt();
        if(k <= 0 || k >= 47){
            //System.out.println("您输入的整数有误，请重新输入：):");
            k = sc.nextInt();
        }
        System.out.println(fun(k));
    }
    //递归法
    public static int fun(int num){
        if(num == 1 || num == 2){
            return 1;
        }
        return fun(num - 1) + fun(num - 2);
    }
}

发表于 2019-08-07 09:18:34 回复(0)

lx的流星

while True:
    try:
        k=int(input().strip())
        list1=[1,1]
        while k>2:
            num=list1[-1]+list1[-2]
            list1.append(num)
            k-=1
        print(list1[-1])
    except:
        break

发表于 2019-07-27 13:22:57 回复(0)

Arsent

def fabonacci(input):
    if input > 3:        
        fibo = [1,1,2]
        
        for i in range(3,input):
            temp = fibo[i-2] + fibo[i-1]
            fibo.append(temp)
        print(fibo[input-1])
    elif input == 3:
        print(2)
    else:
        print(1)
if __name__ == '__main__':
    input = int(input())
    fabonacci(input)

发表于 2019-05-09 16:02:41 回复(1)

Java

人才库收割机

矩阵乘法解决，保证时间复杂度为O(logN)

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = k - 2;
        if (n <= 2) {
            System.out.println(1);
            return;
        }

        int[][] matrix = new int[][]{{1, 1}, {1, 0}};
        matrix = matrixPower(matrix, n);
        int result = matrix[0][0] + matrix[1][0];
        System.out.println(result);
    }

    private static int[][] matrixPower(int[][] m, int n) {

        int[][] result = new int[m.length][m[0].length];
        for (int i = 0; i < m.length; i++) {
                result[i][i] = 1;
        }

        while (n != 0) {
            result = (n & 1) == 1 ? matrixMultiply(result, m) : result;
            m = matrixMultiply(m, m);
            n >>= 1;
        }

        return result;
    }

    private static int[][] matrixMultiply(int[][] a, int[][] b) {
        if (a[0].length != b.length)
            return null;

        int[][] result = new int[a.length][b[0].length];
        for (int row = 0; row < a.length; row++) {
            for (int column = 0; column < b[0].length; column++) {
                int temp = 0;
                for (int i = 0; i < a[row].length; i++) {
                    temp += a[row][i] * b[i][column];
                }
                result[row][column] = temp;
            }
        }

        return result;
    }
}

发表于 2019-04-24 15:27:35 回复(0)

喜欢飞来飞去的无尾熊这就开摆

#include<stdio.h>
int main(){
    int i,n,t1=0,t2=1,nextTerm;
   while( scanf("%d",&n)!=EOF){
       for(i=1;i<=n;i++){
           nextTerm=t1+t2;
           t1=t2;
           t2=nextTerm;
       }
       printf("%d",t1);
   }
    return 0;
}

发表于 2019-03-15 15:24:29 回复(0)

merci95

def fib(n):
    if n <= 2:
        return 1
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

n = int(input())
print(fib(n))

发表于 2019-03-14 15:34:22 回复(0)