首页 > 试题广场 >

Fibonacci

[编程题]Fibonacci

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

The Fibonacci Numbers{0,1,1,2,3,5,8,13,21,34,55...} are defined by the recurrence: F0=0 F1=1 Fn=Fn-1+Fn-2,n>=2 Write a program to calculate the Fibonacci Numbers.

输入描述:

    Each case contains a number n and you are expected to calculate Fn.(0<=n<=30) 。

输出描述:

   For each case, print a number Fn on a separate line,which means the nth Fibonacci Number.

示例1

输入

输出

算法知识视频讲解

爱吃花椒的🐱酱

#include <iostream>
#include <string.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
// 最纯粹的斐波那契
int f(int n){
    if(n==0) return 0;
    else if(n==1) return 1;
    else return f(n-1) + f(n-2);
}

int main(int argc, char** argv) {
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

发表于 2021-01-28 15:26:44 回复(1)

C/C++

胡桃夹子🎈

#include<iostream>
using namespace std;
int** multi(int** m1, int** m2)//简易矩阵乘法
{
	int** ans = new int* [2];
	for (int t = 0; t < 2; t++)
		ans[t] = new int[2];

	for (int i = 0; i < 2; i++)//i:行
	{
		
		for (int j = 0; j < 2; j++)//j:列
		{
			int sum = 0;
			for (int k = 0; k < 2; k++)//k:元素
			{
				sum += m1[i][k] * m2[k][j];
			}	
			ans[i][j] = sum;
		}			
	}
	return ans;
}
int fibonacci_3(int n)//矩阵快速幂法O(logn)
{
	int i;
	int** mat = new int* [2];
	for ( i = 0; i < 2; i++)
		mat[i] = new int[2];
	mat[0][0] = 1, mat[0][1] = 1, mat[1][0] = 1, mat[1][1] = 0;
	/*//求n次幂一般写法
	int** base = mat;
	for ( i = 0; i < n; i++)
	{
		mat = multi(mat, base);
	}
	reutrn mat[0][1];*/
	//快速幂
	int** ans = new int* [2];
	for (i = 0; i < 2; i++)
		ans[i] = new int[2];
	ans[0][0] = 1, ans[0][1] = 0, ans[1][0] = 0, ans[1][1] = 0;//单位阵
	while (n != 0)
	{
		if (n % 2 == 1)
			ans = multi(ans, mat);
		n /= 2;
		mat = multi(mat, mat);
	}
	return ans[0][1];
}

int main()
{
	int n;
	while (cin>>n)
	{
		cout << fibonacci_3(n) << endl;
	}
	return 0;
}

利用公式：

$\left[ \begin{matrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{matrix} \right] \ = \left[ \begin{matrix} 1 & 1\\ 1 & 0 \end{matrix} \right]^{n}\$

数学归纳法可以证明，时间复杂度O(logn)

编辑于 2020-06-16 16:06:29 回复(1)

C/C++

dolphin_ink

//简单的递归题，麻烦路过的朋友点个赞拿个徽章~谢谢
#include<iostream>
(720)#include<cstdio>

using namespace std;

int Function(int n){
    if(n == 0||n == 1){
        return n;
    }else{
        return (Function(n - 1)+Function(n - 2));
    }
}

int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        printf("%d",Function(n));
    }
    return 0;
}

发表于 2020-05-04 20:38:40 回复(0)

C/C++

YhX.

#include<stdio.h>
int main()
{
    int a[31],i,n;
    a[0]=0;a[1]=1;
    scanf("%d",&n);
    for(i=2;i<=n;i++)
        a[i]=a[i-1]+a[i-2];
    printf("%d",a[n]);
}

发表于 2020-05-01 10:50:34 回复(0)

Java

LHC0512

Java 解法，动态规划

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        //由于输入的n大小不确定，使用动态数组ArrayList
        ArrayList<Integer> dp = new ArrayList<>();
        dp.add(0);
        dp.add(1);
        for (int i = 2; i <= n; i++)
            // 状态转移方程： dp[n]=dp[n-1]+dp[n-2]
            dp.add(dp.get(i-1)+dp.get(i-2));
        System.out.println(dp.get(n));
    }
}

发表于 2020-03-06 10:31:43 回复(0)

Python

TimeMac

#最简洁实现
while True:
    try:
        num,a,b = int(input()),0,1
        for _ in range(num):
            a,b = b,a+b
        print(a)
    except Exception:
        break

编辑于 2018-10-14 12:46:06 回复(0)

飞越地平线

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[200];
int n;
cin>>n;

    if(n>=2)

{
int sum;
a[0]=0,a[1]=1;
for(int i=2; i<=n; i++)
{
a[i]=a[i-2]+a[i-1];
sum=a[i];
}
cout<<sum<<endl;
}
else
{
if(n==1)
cout<<1<<endl;
else
cout<<0<<endl;
}
return 0;
}

发表于 2018-04-19 19:55:48 回复(0)

LiuTaw

动态规划的思想去做，把值保存起来，下次再用，虽然这里限制30，不用也可以

#include<stdio.h>

#include<iostream>

using namespace std;

int tmp[100000]={-1};

int fibonacci(int x)

{

if(x==0) return 0;

if(x==1) return 1;

int a,b;

if(tmp[x-2]!=-1)

a = tmp[x-2];

else

{

a = fibonacci(x-2);

tmp[x-2] = a;

}

if(tmp[x-1]!=-1)

b = tmp[x-1];

else

{

b= fibonacci(x-1);

tmp[x-1] = b;

}

return a+b;

};

int main()

{

for(int i=0;i<100000;i++)

{

tmp[i] = -1;

}

int x;

scanf("%d",&x);

cout<<fibonacci(x)<<endl;

return 0;

}

发表于 2018-02-19 21:18:41 回复(0)

Python

华科平凡

python solution:

while True:
    try:
        a,res=int(input()),[0,1,1,2]
        while len(res)<a+1:
            res.append(res[-1]+res[-2])
        print(res[a])

    except:
        break

发表于 2017-10-06 15:52:55 回复(0)

小陈也只是想要一个实习罢了

非常基础了，使用数组能很好地避免多次递归增大时间复杂度

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

发表于 2019-02-09 21:53:07 回复(0)

kestars

#include <iostream>
using namespace std;
int fibonacci(int n){
    if(n==0)
        return 0;
    if(n==1)
        return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}

int main(){
    int n;
    while(cin>>n){
        cout<<fibonacci(n);
    }
}

发表于 2018-09-15 19:21:37 回复(1)

Edward王

斐波那契数列的非递归实现(for循环)

#include <stdio.h>

long long int Fibonacci(int n){
    if(n == 0) return 0;
    static long long int a = 0;
    static long long int b = 1;
    for(int i = 2; i <= n; ++i){
        long long int t = a + b;
        a = b;
        b = t;
    }
    return b;
}

int main() {
    int n;
    scanf("%d",&n);
    printf("%lld",Fibonacci(n));
    return 0;
}

发表于 2024-04-26 19:45:26 回复(0)

C/C++

猫猫猫1

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

int F(int n){
    if(n==0||n==1){
        return n;
    }
    else{
        return F(n-1)+F(n-2);
    }
}

int main(){
    int n;
    while(cin>>n){
        cout<<F(n)<<endl;
    }
    return 0;
}

发表于 2022-10-08 15:26:12 回复(0)

牛客634638130号

#include <iostream>
using namespace std;
int main() {
    int a, b,k;
    int n;
    while(cin>>n){
        if(n==1||n==0){
            cout<<n<<endl;
            continue;
        }
        a=0;b=1;
        for(int i=2;i<=n;i++){
            k=a+b;
            a=b;
            b=k;
        }
        cout<<k<<endl;
    }
}

发表于 2025-02-20 04:03:31 回复(0)

zbt_123456

#include <iostream>
using namespace std;
int f(int x){
    return x==0||x==1?x:f(x-1)+f(x-2);
}
int main() {
   int n;
   while(cin>>n){
    cout<<f(n)<<endl;
   }
   return 0;
}

发表于 2024-03-27 11:56:32 回复(0)

C++

无问西东gmy

#include <array>
#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        array<int, 31>fib = {0, 1}; //斐波那契数列，以数组表示
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        cout << fib[n] << endl;
    }
    return 0;
}

编辑于 2024-02-02 14:33:21 回复(0)

啵啵超人

#include<iostream>

using namespace std;

long long fia(int n) {
	if (n == 1) {
		return 1;
	}
	else if(n==0){
		return 0;
	}
	else {
		return fia(n - 1) +fia(n-2);
	}
}

int main() {
	int n;
	while (cin >> n && n != EOF) {
		cout << fia(n) << endl;
	}
}

发表于 2023-03-04 14:11:03 回复(0)

吃可爱的莎莎

#include<stdio.h>
int Fi(int n){
    if(0==n){
        return 0;
    }
    else if(1==n){
        return 1;
    }
    else{
        return Fi(n-1)+Fi(n-2);
    }
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        printf("%d\n",Fi(n));
    }
}

发表于 2023-03-02 16:11:49 回复(0)

C++

lyw菌

//采用递归的思想，较为基础

#include "stdio.h"

using namespace std;

int Fibon(int n){

if(n==0)

return 0;

else if(n==1)

return 1;

else

return Fibon(n-1)+ Fibon(n-2);

}

int main(){

int n;

while (scanf("%d",&n)!=EOF){

printf("%d\n", Fibon(n));

}

发表于 2023-02-25 19:16:57 回复(0)

顶呱呱的火龙果很不想上网课

#include <stdio.h>
int Fun(int n){
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return Fun(n-1)+Fun(n-2);
}
int main() {
    int n;
    scanf("%d", &n);
    printf("%d", Fun(n));
    return 0;
}

发表于 2023-02-15 22:17:20 回复(0)