首页 > 试题广场 >

斐波拉契加强版

[编程题]斐波拉契加强版
  • 热度指数：7599 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

对于斐波拉契经典问题，我们都非常熟悉，通过递推公式F(n) = F(n - 1) + F(n - 2)，我们可以在线性时间内求出第n项F(n)，现在考虑斐波拉契的加强版，我们要求的项数n的范围为int范围内的非负整数，请设计一个高效算法，计算第n项F(n-1)。第一个斐波拉契数为F(0) = 1。

给定一个非负整数，请返回斐波拉契数列的第n项，为了防止溢出，请将结果Mod 1000000007。

测试样例： 
3
返回：2
算法知识视频讲解
添加回答
瑰意骑行头像 瑰意骑行

简洁、高效 的 递归解法，目前没有发现比我这个更简洁的代码了，50 ms，1238K

思路 ：找规律，可用数学归纳法证明；
初始值：f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5...

以f(10)为例子找规律：

f(10)

= f(9)+ f(8)  = f(1)f(9)+f(0)f(8)

=2f(8)+ f(7) = f(2)f(8)+f(1)f(7)

=3f(7)+2f(6)= f(3)f(7)+f(2)f(6)

=5f(6)+3f(5)= f(4)f(6)+f(3)f(5)
...
发现规律：F(n) = F(k)F(n-k) + F(k-1)F(n-k-1), k>=1
推导出如下公式:
F(2n) = F(n) F(n) + F(n-1) F(n-1), n>=1
F(2n+1) = F(n+1) F(n) + F(n) F(n-1), n>=1 
Map<Integer,Integer> mp = new HashMap<Integer, Integer>();
public int getNthNumber(int n) {
    if (n==1||n==0)return 1;
    if (n==2)return 2;
    if (mp.containsKey(n))return mp.get(n);//避免重复计算

    long fn1=getNthNumber(n/2+1); // f(n+1)
    long fn_1=getNthNumber(n/2-1); // f(n-1)    
    long fn=getNthNumber(n/2); // f(n)

    if (n%2==1) // F(2n+1) = F(n+1) F(n) + F(n) F(n-1), n>=1
        mp.put(n,(int)((fn*fn1+fn*fn_1)%1000000007));
    else // F(2n) = F(n) F(n) + F(n-1) F(n-1), n>=1 
        mp.put(n,(int)((fn*fn+fn_1*fn_1)%1000000007));

    return mp.get(n);
}
编辑于 2019-11-06 21:51:25 回复(3)
更多回答
C/C++
蓝魔4头像 蓝魔4 
参考大佬的代码！
class Fibonacci {
public:
    void MultMetri(long long base1[2][2],long long base2[2][2])
    {
        long long tmp[2][2]={0};
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
                tmp[i][j]=(base1[i][0]*base2[0][j]+base1[i][1]*base2[1][j])%1000000007;
        }
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
             	base1[i][j]=tmp[i][j];
        }
    }
    int getNthNumber(int n) {
       long long base[2][2]={{1,1},{1,0}};
       long long ret[2][2]={{1,0},{1,0}};
        while(n)
        {
            if(n%2)
                MultMetri(ret,base);
            MultMetri(base,base);
            n=n/2;
        }
        return (int)(ret[0][0]);
    }
};

发表于 2017-07-17 21:25:04 回复(0)
17歲头像 17歲
题目有误，应该是求F(n)而不是F(n-1)，按F(n-1)做过不了
发表于 2018-05-20 13:55:35 回复(0)
求一个大大的offer头像 求一个大大的offer 
import java.util.*;

public class Fibonacci {
    public int getNthNumber(int n) {
        // write code here
        long[][] base={{1,1},{1,0}};
        long[][] ret={{1,0},{0,1}};
        while(n!=0){
            if(n%2==1)
                ret=MultMetri(ret,base);
            base=MultMetri(base,base);
            n=n>>1;
        }
        return (int)(ret[0][0]);
}
     public static long[][] MultMetri(long[][] ret,long[][] base){
        long[][] tmp=new long[2][2];
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                tmp[i][j]=(ret[i][0]*base[0][j]+ret[i][1]*base[1][j])%1000000007;
        for(int k=0;k<2;k++)
            for(int q=0;q<2;q++)
                ret[k][q]=tmp[k][q];
       return ret;
    }
}

是叫矩阵快速幂法吧
发表于 2017-04-19 09:48:40 回复(0)
Madstorm头像 Madstorm 
来个python版本的，代码相当简洁
# -*- coding:utf-8 -*-
class Fibonacci:
    def getNthNumber(self, n):
        res=base=[[1,1],[1,0]]#结果项和基底项
        surplus=[[1,0],[0,1]]#surplus存储剩余项
        while(n>1):
            if n&1:
                surplus=self.mutiply(surplus,res)
            res=self.mutiply(res,res)
            n=n>>1
        res=self.mutiply(res, surplus)
        return res[0][0]%1000000007
    def mutiply(self,a,b):#矩阵乘法
        temp=[[0,0],[0,0]]
        for i in range(len(a)):
            for j in range(len(b)):
                for k in range(len(temp)):
                    temp[i][j]+=a[i][k]*b[k][j]%1000000007
                    
        return temp

发表于 2015-08-25 21:24:25 回复(2)
露西恩缇努维尔头像 露西恩缇努维尔
基于二分的递归，速度应该贼快。不要问我怎么推出来的，自己在纸上写几个就找到规律了。 

#include<bits/stdc++.h>
typedef long long ll;
class Fibonacci {
public:
    int getNthNumber(int n) {
        // write code here
        if(mp.count(n))
             return mp[n];
        if(n==0)
        {
            mp[0]=1;
            return mp[0];
        }
        if(n==1)
        {
            mp[1]=1;
            return mp[1];
        }
        mp[n]=((ll)getNthNumber(n/2)*getNthNumber(n-n/2)%MOD +(ll)getNthNumber(n/2-1)*getNthNumber(n-n/2-1)%MOD)%MOD;
        return mp[n];
    }
private:
    unordered_map<int,int> mp;
    const int MOD=1000000007;
};


发表于 2020-08-24 10:46:27 回复(0)
C/C++
nbgao头像 nbgao 
class Fibonacci {
public:     void Mul(long long a[2][2], long long b[2][2])     {         long long t[2][2] = {0};         for(int i=0;i<2;i++)             for(int j=0;j<2;j++)                 t[i][j] = (a[i][0]*b[0][j] + a[i][1]*b[1][j])%(1000000007);         for(int i=0;i<2;i++)             for(int j=0;j<2;j++)                 a[i][j] = t[i][j];     }
    int getNthNumber(int n) {
        long long base[2][2] = {{1,1},{1,0}};
        long long ret[2][2] = {{1,0},{1,0}};
        while(n)
        {
            if(n&1)
                Mul(ret, base);
            Mul(base, base);
            n>>=1;         }         return ret[0][0];
    }
};

发表于 2017-12-23 00:31:15 回复(0)
文武头像 文武 
class Fibonacci {
public:
void multi(long long a[2][2], long long  b[2][2])
{
	long long  r[2][2];
	r[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
	r[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
	r[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
	r[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];

	a[0][0] = r[0][0] % 1000000007;
	a[0][1] = r[0][1] % 1000000007;
	a[1][0] = r[1][0] % 1000000007;
	a[1][1] = r[1][1] % 1000000007;
}

int getNthNumber(int n) {

	long long  tmpA[2][2] = {
		{ 1, 1 },
		{ 1, 0 }
	};
	long long  tmpB[2][2] = {
		{ 1, 0 },
		{ 0, 1 }
	};


	for (; n > 1; n = n / 2)
	{
		if (n & 1 == 1)
		{
			multi(tmpB,tmpA);
		}
		multi(tmpA, tmpA);
	}
	multi(tmpA, tmpB);

	return tmpA[0][0] ;
}
};

发表于 2016-07-20 10:39:56 回复(2)
逍遥小章头像 逍遥小章
用矩阵快速幂就可以搞定
#include <cstdio>
#include <cstring>
#include
#include <cmath>
using namespace std;
 
constintMOD =10000;
 
struct matrix {    //矩阵
    intm[2][2];
}ans;
 
matrix base = {1,1,1,0};
 
matrix multi(matrix a, matrix b) { //矩阵相乘，返回一个矩阵
    matrix tmp;
    for(inti =0; i <2; i++) {
        for(intj =0; j <2; j++) {
            tmp.m[i][j] =0;
            for(intk =0;  k <2; k++)
                tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
        }
    }
    returntmp;
}
 
intmatrix_pow(matrix a,intn) {  //矩阵快速幂，矩阵a的n次幂
    ans.m[0][0] = ans.m[1][1] =1; //初始化为单位矩阵
    ans.m[0][1] = ans.m[1][0] =0;
    while(n) {
        if(n &1) ans = multi(ans, a);
        a = multi(a, a);
        n >>=1;
    }
    returnans.m[0][1];
}
 
intmain() {
    intn;
    while(scanf("%d", &n), n != -1) {
        printf("%d\n", matrix_pow(base, n));
    }
    return0;
}
编辑于 2015-07-25 21:01:20 回复(0)
Baymax头像 Baymax
我这样做哪里错了啊？？？
classFibonacci {
public:
    intgetNthNumber(intn) {
        // write code here
        if(1== n)
            return1;
        elseif(2== n)
            return2;
        else{
            vector<int> v1;
            v1.push_back(1);
            v1.push_back(1);
            v1.resize(n);
            for(inti = 2;i<n; ++i){
                v1[i] = v1[i-1] + v1[i-2];
            }
            returnv1[n-1]%1000000007;
        }
    }
};

发表于 2015-07-30 21:17:53 回复(1)
开始懂了头像 开始懂了 
public class Fibonacci {
    public int getNthNumber(int n) {
        // write code here
        int result=0;
		if(n==1||n==2){
			return 1;
		}else{
			result=getNthNumber(n-1)+getNthNumber(n-2);
		}
		return result%1000000007;
    }
}
这个为什么不可以？

发表于 2015-07-27 15:50:31 回复(4)
//头像 // 
参考的程云老师的课程（第9次课）。
class Fibonacci {
public:
 static const long long MOD =1000000007; 
    int getNthNumber(int n) {
        // write code here
        int a=1,b=1;
        vector< vector<long long> > matrix(2);
        vector< vector<long long> > res(2);
        res[0].resize(2);
        res[1].resize(2);
        const int m[2][2]={{1,1},{1,0}};
        for( int i=0; i<2; ++i )
         for( int j=0; j<2; ++j )
          matrix[i].push_back(m[i][j]);
        res[0][0]=res[1][1]=1;
        res[0][1]=res[1][0]=0;
        while( n )
        {
         if( n&1 )    res=multiply(res,matrix);
         matrix=multiply(matrix,matrix);
         n >>= 1;
        }
  return (res[1][0]%MOD+res[1][1]%MOD)%MOD;
    } 
private:
    vector< vector<long long> > multiply ( vector< vector<long long> >& a, vector< vector<long long> >& b )
    {
  vector< vector<long long> > temp(2);
  for( int i=0; i<2; i++ )
   temp[i].resize(2);
  for( int i=0; i<2; i++ )
     {
      for( int j=0; j<2; j++ )
      {
       temp[i][j] = ((a[i][0]%MOD * b[0][j]%MOD )%MOD + (a[i][1]%MOD * b[1][j]%MOD )%MOD)%MOD;
   }
  }
  return temp; 
 }
};

编辑于 2015-08-09 23:18:21 回复(4)
HappyDeer头像 HappyDeer
这个题f(n)应该是第n+1项吧。。
发表于 2016-05-03 16:28:14 回复(0)
逸劳永逸头像 逸劳永逸
题目中的测试用例说输入3，输出2，但是代码区域的测试用例里输入3输出3，题目有误
发表于 2025-10-28 09:21:34 回复(0)
皮蛋秀柚秋头像 皮蛋秀柚秋 
#define ll long long
class Fibonacci {
public:
    ll mod = 1e9+7;
    vector<vector<ll>> matrixPower(vector<vector<ll>>m,int p)
    {
        vector<vector<ll>>ret(2,vector<ll>(2,0));
        for(int i=0;i<2;++i)
             ret[i][i] = 1;
        while(p)
        {
            if(p%2)
            {
                ret = multiMatrix(ret,m);
            }
            m = multiMatrix(m,m);
            p/=2;
        }
        return ret;
    }
    vector<vector<ll>> multiMatrix(vector<vector<ll>> m1,vector<vector<ll>> m2)
    {
        vector<vector<ll>>ans(2,vector<ll>(2,0));
        for(int i=0;i<2;++i)
            for(int j=0;j<2;++j)
            {
                ans[i][j] = ((m1[i][0]%mod)*(m2[0][j]%mod) + (m1[i][1]%mod)*(m2[1][j]%mod))%mod;
            }
        return ans;
    }
    int getNthNumber(int n) {
        // write code here
        n+=1;
        if(n==1||n==2) return 1;
        long long m[2][2] = {{1,1},{1,0}};
        vector<vector<ll>>base(2,vector<ll>(2,0));
        for(int i=0;i<2;++i)
            for(int j=0;j<2;++j)
                base[i][j] = m[i][j];
        vector<vector<ll>> res = matrixPower(base,n-2);
        return (res[0][0]+res[1][0])%mod;
    }
};

发表于 2020-04-29 11:18:04 回复(0)
名字的响亮的头像 名字的响亮的
拜托牛客题目描述能更严谨点吗？
发表于 2019-07-03 16:37:31 回复(0)
长昼头像 长昼
看你们一阵乱秀，我只能说我真是个菜鸡
发表于 2019-06-09 16:34:08 回复(0)
人才库警告！头像 人才库警告！
为什么这样不行？
import java.util.*;
public class Main{
    public static  int getNthNumber(int n) {
        int[] a=new int[100000000];
        int i=0;
        a[0]=1;
        a[1]=1;
        if(n==0){
            return a[0];
        }
        if(n==1){
            return a[1];
        }
        for(i=2;i<n;i++){
            a[i]=(((a[i-1])%1000000007)+(a[i-2])%1000000007)%1000000007;
        }
        return a[i-1];
    }
}
发表于 2019-03-17 20:46:00 回复(0)
哆啦不爱梦爱美食头像 哆啦不爱梦爱美食
class Fibonacci {
public:
   void f(long a[2][2],long b[2][2]){
        long res[2][2]={0};
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    res[i][j]+=(a[i][k]*b[k][j])%1000000007;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                a[i][j]=res[i][j];

     }
    int getNthNumber(int n) {
        long res[2][2]={2,1,1,1};
        long base[2][2]={1,1,1,0};
        if(n==1||n==0)
            return 1;
        n=n-2;
        while(n){
            if(n&1)
                f(res,base);
            f(base,base);
            n=n>>1;
         }
        return (res[0][0])%1000000007;
    }
};
发表于 2018-08-10 09:25:34 回复(0)
把冰雪披戴在肩膀头像 把冰雪披戴在肩膀
这题动态规划体现在哪？
发表于 2018-03-24 15:22:08 回复(0)
提交观点

问题信息

递归
来自：面试常考算法题(八)-...
难度：
30条回答 18936浏览

热门推荐

通过挑战的用户

查看代码

相关试题

斐波拉契加强版

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号