斐波那契数列 优化矩阵求法实例

　　在做编程题目的时候经常会遇到“斐波那契数列”相关的题目，尤其在做OJ中。下面说一些方法：

　　(一)递归

　　递归是最慢的会发生重复计算，时间复杂度成指数级。

代码如下:

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

　(二)循环

　　利用临时变量来保存中间的计算过程，加快运算。

代码如下:

long long fac(int n)
{
    long long a=1,b=2,c;
    if(n==1)    return 1;
    else if(n==2)   return 2;
    else
    {
        for(int i=3;i<=n;i++)
        {
            c=a+b; 　　a=b; 　　b=c;
        }
    }
    return b;
}

　　(三)矩阵乘法+空间换时间(减少乘法，取模运算)

　　数列的递推公式为：f(1)=1，f(2)=2，f(n)=f(n-1)+f(n-2)(n>=3)

　　 用矩阵表示为：

进一步，可以得出直接推导公式：

　　由于矩阵乘法满足结合律，在程序中可以事先给定矩阵的64，32，16，8，4，2，1次方，加快程序的执行时间。（有些题目需要取模运算，也可以事先进行一下）。给定的矩阵次幂，与二进制有关是因为，如下的公式存在解，满足Xi={0或1}：

为了保证解满足 Xi={0或1}，对上述公式的求解从右向左，即求解顺序为Xn，Xn-1,Xn-2,....,X1,X0。

　　完整代码实现如下：

代码如下:

///求解fac(n)%100000，其中n为大于等于3的正整数
#include<stdio.h>
#include<math.h>
long long fac_tmp[6][4]={   ///存放矩阵次幂
                    ///位置：00 01 10 11
                   {24578,78309,78309,46269},   ///32次幂%100000
                   {1597,987,987,610},  ///16次幂%100000
                   {34,21,21,13},   ///8次幂%100000
                   {5,3,3,2},   ///4次幂%100000
                   {2,1,1,1},   ///2次幂%100000
                   {1,1,1,0},   ///1次幂%100000
                   };
void fac(int);

int main()
{
    int n;
    scanf("%d",&n);
    fac(n);
    return 1;
}

void fac(int k) ///k>=3
{
    int i;
    long long t00=1,t01=1,t10=1,t11=0;  ///表示矩阵的1次幂
    long long a,b,c,d;
    k=k-3;  ///公式中是n-2次幂，(t00,t01,t10,t11)表示1次幂。所以一共减3次
    for(i=k;i>=32;i=i-32)   ///对于大于等于32的k;
    {
        a=(t00*fac_tmp[0][0]+t01*fac_tmp[0][2])%100000;
        b=(t00*fac_tmp[0][1]+t01*fac_tmp[0][3])%100000;
        c=(t10*fac_tmp[0][0]+t11*fac_tmp[0][2])%100000;
        d=(t10*fac_tmp[0][1]+t11*fac_tmp[0][3])%100000;
        t00=a;  t01=b;  t10=c;t11=d;
    }

i=4;
    while(i>=0)    ///对于小于32的k(16,8,4,2,1);
    {
        if(k>=(long long)pow(2,i))  ///如果k大于某一个2的次幂
        {

a=(t00*fac_tmp[5-i][0]+t01*fac_tmp[5-i][2])%100000; ///(5-i)：矩阵的2的i次幂在数组fac_tmp中的位置为fac_tmp[5-i]
            b=(t00*fac_tmp[5-i][1]+t01*fac_tmp[5-i][3])%100000;
            c=(t10*fac_tmp[5-i][0]+t11*fac_tmp[5-i][2])%100000;
            d=(t10*fac_tmp[5-i][1]+t11*fac_tmp[5-i][3])%100000;
            t00=a;  t01=b;  t10=c;t11=d;
            k=k-(int)pow(2,i);
        }
        i--;
    }

a=(t00*2+t01*1)%100000;
    printf("%lld\n",a);
}

赞 (0)

相关推荐

  • java实现斐波那契数列的3种方法

    先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案.去面试的时候,由于面试前天晚上11点钟才到阿里巴巴指定面试城市,找到旅馆住下基本都1点多,加上晚上完全没有睡好,直接导致第二天面试效果很不好(对于那些正在找工作的大虾们不要向小虾一下悲剧,提前做好准备还是很重要滴),面试大概进行了一个多小时(面试结束回去的时候基本走路都快睡着了,悲催!!),面试快结束的时候面试官问的我问题就是关于费波那西数列,当时头脑完全浆糊,只知道要设置三个变量或者用List先初始化,当写到for循环的

  • python求斐波那契数列示例分享

    复制代码 代码如下: def getFibonacci(num): res=[0,1] a=0 b=1 for x in range(0,num):  if x==a+b:   res.append(x)   a,b=b,a+b return res res=getFibonacci(1000)print(res) #递归a=[0,1]qian=0def fibna(num,qian): print(num) he=num+qian if he<1000:  a.append(he)  qian

  • php处理斐波那契数列非递归方法

    我自己构思了下,实际上程序来解决这个事情,就是一个偏移量的问题.首先看数列::1.1.2.3.5.8.13.21.34数列的下一个数是前2个数字之和,以此类推. 程序处理的话,实际上就是一个FOR语句,传统FOR语句是for($i=1;$i;$count,$i++),这里的偏移量是$i=$i+1.如果处理这个数列的话,这个偏移量就不是1了,是前1个数字.那么当你for的时候,一个变量记录上一个数字,另外一个记录当前数字,偏移量为这上一个数字,然后在循环中重新赋值,将上一个数字记录成当然循环值,以

  • 基于使用递归推算指定位数的斐波那契数列值的解决方法

    昨天面试遇到这样的一道题目:1,1,2,3,5,8,13,21...,请问第30位的值是多少? 代码实现如下: 复制代码 代码如下: //1,1,2,3,5,8,13,21.......第30个是多少?     //使用递归计算指定位数的斐波那契数列值     //Fn=F(n-1)+F(n-2)     public static int GetFibonacciNumber(int index)     {         if(index<0||index==0)throw new Exc

  • 递归形式与非递归形式的斐波那契数列的用法分析

    复制代码 代码如下: <SPAN style="FONT-SIZE: 32px">采用递归形式和非递归形式实现斐波那契数列</SPAN> 复制代码 代码如下: #include "stdafx.h"#include <iostream>using namespace std;//递归形式的斐波那契数列int fibonacciRecursion(int n){ if (n == 1 || n ==2) {  return 1; }

  • java实现fibonacci数列学习示例分享(斐波那契数列)

    输出:1  1  2  3  5 复制代码 代码如下: public class FibonaciTest { public static void main(String[] args) {  Fibonaci(5); } public static void Fibonaci (int count) { int[] num = new int[count];  num[0] = num[1] = 1; for (int i = 2; i < count; i++) {   num[i] =

  • C++输出斐波那契数列的两种实现方法

    定义: 斐波那契数列指的是这样一个数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...这个数列从第三项开始,每一项都等于前两项之和. 以输出斐波那契数列的前20项为例: 方法一:比较标准的做法,是借助第三个变量实现的. 复制代码 代码如下: #include<iostream>  using namespace std;int main(){    int f1=0,f2=1,t,n=1;    cout<<"数列第1个

  • 解析分别用递归与循环的方式求斐波那契数列的实现方法

    代码如下: 复制代码 代码如下: public class Fibonacci { public static long recursive(int n) {  if (n <= 0)   return 0;  if (n == 1)   return 1;  return recursive(n - 1) + recursive(n - 2); } public static long loop(int n) {  if (n <= 0)   return 0;  if (n == 1)  

  • c#斐波那契数列(Fibonacci)(递归,非递归)实现代码

    c#斐波那契数列(Fibonacci)(递归,非递归)实现代码

    //Main 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Fibonacci{    class Program    {        static void Main(string[] args)        {            Console.WriteLine("Would you like to know which

  • 斐波那契数列 优化矩阵求法实例

    斐波那契数列 优化矩阵求法实例

    在做编程题目的时候经常会遇到"斐波那契数列"相关的题目,尤其在做OJ中.下面说一些方法: (一)递归 递归是最慢的会发生重复计算,时间复杂度成指数级. 复制代码 代码如下: long long fac(int n){ if(n==1) return 1; else if(n==2)  return 2; else   return fac(n-1)+fac(n-2);} (二)循环 利用临时变量来保存中间的计算过程,加快运算. 复制代码 代码如下: long long fac(int

  • C语言实现斐波那契数列(非递归)的实例讲解

    废话不多说,直接上代码 #include <stdio.h> #include <stdlib.h> void f(int n); int main(void) { f(10); return 0; } void f(int n) { if(n==1) { printf("1\n"); return; } if(n==2) { printf("1 1\n"); return; } printf("1 1 "); int*

  • java编程经典案例之基于斐波那契数列解决兔子问题实例

    java编程经典案例之基于斐波那契数列解决兔子问题实例

    本文实例讲述了java基于斐波那契数列解决兔子问题.分享给大家供大家参考,具体如下: 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? package com.java.recursion; /** * @描述 三种方法实现斐波那契数列 * @项目名称 Java_DataStruct * @包名 com.java.recursion * @类名 Fibonacci * @author chenli

  • JAVA递归与非递归实现斐波那契数列

    斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci[1] )以兔子繁殖为例子而引入,故又称为"兔子数列",指的是这样一个数列:0.1.1.2.3.5.8.13.21.34.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起

  • C语言中斐波那契数列的三种实现方式(递归、循环、矩阵)

    C语言中斐波那契数列的三种实现方式(递归、循环、矩阵)

    目录 一.递归 二.循环 三.矩阵 <剑指offer>里讲到了一种斐波那契数列的 O(logN) 时间复杂度的实现,觉得挺有意思的,三种方法都记录一下. 一.递归 一般来说递归实现的代码都要比循环要简洁,但是效率不高,比如递归计算斐波那契数列第n个元素. long long Fibonacci_Solution1(unsigned int n) { // printf("%d ", n); if (n <= 0) return 0; if (n == 1) retur

  • C语言数据结构递归之斐波那契数列

    C语言数据结构递归之斐波那契数列 因为自己对递归还是不太熟练,于是做POJ1753的时候就很吃力,就是翻棋子直到棋盘上所有棋子的颜色一样为止,求最少翻多少次,方法是枚举递归.然后就打算先做另一道递归的题(从数组中取出n个元素的组合),但是同样在递归的问题上不太理解.好吧,于是复习CPP,在第229页的时候,看到了斐波那契数列,回想起之前做过的一道题目,发现可以用递归的方法来做.于是决定优化一下之前的代码. 以下这段摘自<C primer plus> 斐波那契数列的定义如下:第一个和第二个数字都

  • C语言求Fibonacci斐波那契数列通项问题的解法总结

    C语言求Fibonacci斐波那契数列通项问题的解法总结

    一:递归实现   使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1. 二:数组实现   空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快. 三:vector<int>实现   时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源. 四:queue<int>实现   当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int&g

  • C#实现斐波那契数列的几种方法整理

    什么是斐波那契数列?经典数学问题之一:斐波那契数列,又称黄金分割数列,指的是这样一个数列:1.1.2.3.5.8.13.21.--想必看到这个数列大家很容易的就推算出来后面好几项的值,那么到底有什么规律,简单说,就是前两项的和是第三项的值,用递归算法计第50位多少. 这个数列从第3项开始,每一项都等于前两项之和. 斐波那契数列:{1,1,2,3,5,8,13,21...} 递归算法,耗时最长的算法,效率很低. public static long CalcA(int n) { if (n <=

  • 如何使用Python实现斐波那契数列

    如何使用Python实现斐波那契数列

    斐波那契数列(Fibonacci)最早由印度数学家Gopala提出,而第一个真正研究斐波那契数列的是意大利数学家 Leonardo Fibonacci,斐波那契数列的定义很简单,用数学函数可表示为: 数列从0和1开始,之后的数由前两个数相加而得出,例如斐波那契数列的前10个数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34. 用 Python 实现斐波那契数列常见的写法有三种,各算法的执行效率也有很大差别,在面试中也会偶尔会被问到,通常面试的时候不是让你简单的用递归写写就完了,

  • 详解python使用递归、尾递归、循环三种方式实现斐波那契数列

    在最开始的时候所有的斐波那契代码都是使用递归的方式来写的,递归有很多的缺点,执行效率低下,浪费资源,还有可能会造成栈溢出,而递归的程序的优点也是很明显的,就是结构层次很清晰,易于理解 可以使用循环的方式来取代递归,当然也可以使用尾递归的方式来实现. 尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.尾递归就是把当前的运算结果(或路

随机推荐