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

简介:   在做编程题目的时候经常会遇到“斐波那契数列”相关的题目,尤其在做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); }   (二)循环   利用临时变量来保存中间的计算过程,加快运算。

  在做编程题目的时候经常会遇到“斐波那契数列”相关的题目,尤其在做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={01}: 

 

为了保证解满足 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);
}

 

 

相关文章
|
12月前
|
计算机视觉 Python
Opencv学习笔记(一):如何将得到的图片保存在指定目录以及如何将文件夹里所有图片以数组形式输出
这篇博客介绍了如何使用OpenCV库在Python中将图片保存到指定目录,以及如何将文件夹中的所有图片读取并以数组形式输出。
803 0
Opencv学习笔记(一):如何将得到的图片保存在指定目录以及如何将文件夹里所有图片以数组形式输出
|
存储 安全 Linux
OpenSSH之Windows账户访问操作
OpenSSH之Windows账户访问操作
952 0
|
3月前
|
机器学习/深度学习 传感器 监控
基于多模态感知的工业安全行为识别技术突破
本项目通过分层特征增强架构,突破工业安全监控中微小目标检测难、行为理解缺失和响应延迟高等技术瓶颈。采用动态ROI聚焦、时空域建模与联邦学习等创新技术,实现厘米级行为捕捉,准确率提升300%,隐患识别响应速度提高112倍,并已在危化、电力、医疗等行业落地应用,具备广阔推广前景。
129 0
|
SQL 数据可视化 数据管理
人大金仓数据库Kingbase8在CentOS7上的安装与使用
人大金仓数据库Kingbase8在CentOS7上的安装与使用
5810 1
人大金仓数据库Kingbase8在CentOS7上的安装与使用
|
9月前
|
搜索推荐 API 开发者
京东商品视频数据接口(JD.item_video)丨京东 API 接口指南
京东商品视频数据接口(JD.item_video)是京东开放平台提供的API,开发者可通过指定商品ID(num_iid)获取商品视频资源,用于丰富电商平台展示、提升用户体验。该接口适用于电商平台建设、商品推荐系统、市场研究与竞品分析及价格监测平台等场景,帮助用户更直观了解商品,提高购买转化率。示例代码展示了如何使用Python调用此接口并解析返回的JSON数据。
427 16
|
12月前
|
并行计算 开发工具 异构计算
在Windows平台使用源码编译和安装PyTorch3D指定版本
【10月更文挑战第6天】在 Windows 平台上,编译和安装指定版本的 PyTorch3D 需要先安装 Python、Visual Studio Build Tools 和 CUDA(如有需要),然后通过 Git 获取源码。建议创建虚拟环境以隔离依赖,并使用 `pip` 安装所需库。最后,在源码目录下运行 `python setup.py install` 进行编译和安装。完成后即可在 Python 中导入 PyTorch3D 使用。
1117 0
|
人工智能 前端开发 搜索推荐
详解基于百炼平台及函数计算快速上线网页AI助手
通过阿里云百炼平台,企业可在10分钟内为其网站添加智能客服系统,提升用户体验并降低成本。流程包括:创建大模型应用、配置参数(如温度系数以控制回复的随机性)、发布应用获取API密钥;使用函数计算快速搭建示例网站,并通过简单的代码更改启用AI助手功能;还可导入私有知识库增强助手的能力。前端基于NLUX开发,支持定制化需求如样式调整和历史会话管理。服务端代码提供了调用大模型获取答案的接口。借助百炼平台,企业能迅速部署即时且个性化的在线服务,适应数字化转型的需求。
|
JavaScript 开发工具 开发者
vue3【提效】使用 VueUse 高效开发(工具库 @vueuse/core + 新增的组件库 @vueuse/components)
vue3【提效】使用 VueUse 高效开发(工具库 @vueuse/core + 新增的组件库 @vueuse/components)
867 1
|
机器学习/深度学习 自然语言处理 算法
【论文泛读】 知识蒸馏:Distilling the knowledge in a neural network
【论文泛读】 知识蒸馏:Distilling the knowledge in a neural network
【论文泛读】 知识蒸馏:Distilling the knowledge in a neural network
|
存储 关系型数据库 MySQL
【mysql】文本字符串类型
【mysql】文本字符串类型
4242 1
【mysql】文本字符串类型