Fibonacci 斐波那契数列（3种方法）

傷城~ 2022-09-10 03:15 106阅读 0赞

Fibonacci数列的递推公式为：`Fn=Fn-1+Fn-2`，其中`F1=F2=1`。

--------------------

## 输入格式 ##

输入包含一个整数n。

## 输出格式 ##

输出一行，包含一个整数，表示Fn除以10007的余数。

## 样例输入 ##

10

## 样例输出 ##

55

## 样例输入 ##

22

## 样例输出 ##

7704

> 1 <= n <= 1,000,000。

————————————————

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int fib1(int n){ 
    	if(n<1)
    	    return -1;
    	if(n==1 || n==2)
    	    return 1;
    	return fib1(n-1)+fib1(n-2);
    }
    int fib2(int n){ 
    	if(n<1)
    	    return -1;
    	int *a=new int[n];
    	//定义一个数组
    	a[1]=1;
    	a[2]=1;
    	for(int i=3;i<=n;i++)
    	    a[i]=a[i-1]+a[i-2];
    	return a[n];
    }
    int fib3(int n){ 
    	int i,s1,s2;
    	if(n<1)
    	    return -1;
    	if(n==1 || n==2)
    	    return 1;
    	s1=1;
    	s2=1;
    	for(i=3;i<=n;i++){ 
    		s2=s1+s2;
    		//辗转相加法
    		s1=s2-s1;
    		//记录前一项 
    	}
    	    return s2;
    }
    int main(){ 
    	int m;
    	cin>>m;
    	cout<<fib1(m)<<endl;
    	cout<<fib2(m)<<endl;
    	cout<<fib3(m)<<endl;
    	return 0;
    }

--------------------

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关 Fibonacci（斐波纳契）数列的计算

斐波纳契数列的计算是一个很老的话题了，出现在各种算法书中。今天写这篇博文的出发点是在网上看了MIT 6.00的公开课，正好把一些思路理清一些，毕竟有些东西，自己实践过后才有深刻

清疚/ 2023年10月18日 11:05/ 0 赞/ 70 阅读

相关斐波那契数列，兔子繁殖

/ 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子对

梦里梦外;/ 2022年11月29日 13:02/ 0 赞/ 193 阅读

相关 java 斐波那契实现_java实现斐波那契数列的三种方法

![d24aa07c96f0ed7279a2d5a3961e414a.png][] 斐波那契数列(Fibonacci sequence)的定义：斐波那契数列指的是这样一个数列

比眉伴天荒/ 2022年11月08日 11:29/ 0 赞/ 79 阅读

相关 Fibonacci 斐波那契数列（3种方法）

Fibonacci数列的递推公式为：`Fn=Fn-1+Fn-2`，其中`F1=F2=1`。 -------------------- 输入格式输入包含一个整数n。

傷城~/ 2022年09月10日 03:15/ 0 赞/ 107 阅读

相关斐波那契数列的计算

定义Fibonacci数列如下： / 0 n=0 f(n)= 1

迷南。/ 2022年08月05日 21:27/ 0 赞/ 177 阅读

相关实现斐波那契数列的三种方法

斐波那契数列又称黄金分割数列。它的特点是从第3个数开始，每一个数都等于前面两个数相加。例：0 1 1 2 3 5 8 13 21.。。。。。

素颜马尾好姑娘i/ 2022年07月18日 05:20/ 0 赞/ 154 阅读

相关斐波那契数

> 牛客网《剑指offer》时间限制：`1秒` 空间限制：`32768K` 热度指数：`199742` 解题思路一：如果像这样，将会有大量的计算是重复的，时空

╰+哭是因爲堅強的太久メ/ 2022年06月08日 02:46/ 0 赞/ 148 阅读

相关【算法】斐波那契数列的计算方法

题目：计算斐波那契数列。具体什么是斐波那契数列，那就是0，1，1，2，3，5，8，13，21，34，55，89，144，233。要求：时间复杂度尽可能少分析

拼搏现实的明天。/ 2022年06月02日 04:43/ 0 赞/ 126 阅读

相关 java实现斐波那契数列的三种方法

Java实现斐波那契数列的三种方法什么是斐波那契数列这里借用一下度娘的一段话：斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家

约定不等于承诺〃/ 2022年04月16日 01:55/ 1 赞/ 178 阅读

相关 JS实现斐波那契列数的三种方法

JS实现斐波那契列数的三种方法大家是怎么实现斐波那契列数的 1,1,2,3,5,8... f(n)=f(n-1) + f(n-2) 方法一：

红太狼/ 2020年06月06日 17:45/ 0 赞/ 605 阅读