对于斐波拉契经典问题，我们都非常熟悉，通过递推公式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(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)
更多回答
参考大佬的代码！
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)
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)
来个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)
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)
我这样做哪里错了啊？？？
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)
参考的程云老师的课程（第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)
#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)
为什么这样不行？
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;
}
};
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)
import java.util.*;
public class Fibonacci {
public static final int mod = 1000000007;
public int getNthNumber(int n ){
long[][] res = {{1, 1}, {1, 0}};
long[][] surplus = {{1,0},{0,1}};
while(n>1){
if(n % 2 == 1){
surplus = mutiply(surplus, res);
}
res = mutiply(res, res);
n = n/2;
}
res = mutiply(res, surplus);
return res[0][0] % 1000000007;
}
public int[][] mutiply(int[][] a, int[][] b) {
long[][] temp = {{0,0},{0,0}};
for(int i = 0; i < 2; i++ ){
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++){
temp[i][j]+=a[i][k]*b[k][j]%1000000007;
}
}
}
return temp;
}
}
快要疯掉啦，弄了一个下午还是错的，完全是按照第一个答案的思路改编的，为啥结果会这样，宝宝很不开心
答案错误:您提交的程序没有通过所有的测试用例
case通过率为21.05%
测试用例:
88488994
对应输出应该为:
360975877
你的输出为:
9193121
case通过率为21.05%
测试用例:
88488994
对应输出应该为:
360975877
你的输出为:
9193121
发表于 2016-08-31 15:55:57
回复(2)
问题信息
通过挑战的用户
查看代码-
2022-08-29 08:42:05 -
2022-08-26 10:39:57
-
2022-08-08 15:29:18 -
2022-07-15 11:20:30
-
2022-07-02 09:09:12
相关试题
-
评论(15)
-
评论(32) 来自面试常考算法题(八)-斐...
-
评论(67) 来自面试常考算法题(八)-斐...
-
评论(26) 来自面试常考算法题(八)-斐...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
