2019-09-27 17:16 四川省绵阳中学 C++

关注

浅谈用矩阵求斐波那契数列

导语

求斐波那契数列数列有多种方法，比如用递推公式，或是用生成函数求出其通项公式，可惜这两种方法在遇到数据规模较大时会超时，下面介绍一种方法我们将用到矩阵，用矩阵快速幂的方法可以求得斐波那契数列的第i项。

证明

我们首先证明这样一个结论

${gcd(F_{n},F_{m})=F_{gcd(n,m)}}$

证明1

设 $F_{n}=a,F_{n+1}=b$

所以 $F_{n+2}=a+b,F_{n+3}=a+2b,F_{n+4}=2a+3b,F_(n+5)=3a+5b$

得到

$F_{m}=F_{m-n-1}*a+F_{m-n}*b=F_{m-n-1}*F_{n}+F_{m-n}*F_{n+1}$

假设 $m>n$ ,需求 ${gcd(F_{n},F_{m})}$

又因为 $F_{n}|F_{n}*F_{m-n-1}$

所以

${gcd(F_{n},F_{m})}{\Longleftrightarrow{gcd(F_{n},F_{m-n}F_{n+1})}}$

这里再证明一个结论

$gcd(F_{n},F_{n+1})=1$

证明2

$gcd(F_{n},F_{n+1})$
$=$
$gcd(F_{n},F_{n+1}-F_{n})$
$=$
$gcd(F_{n},F_{n-1})$
$=$
$gcd(F_{n-2},F_{n-1})$
$=$
$...$
$=$
$gcd(F_{1},F_{2}=1)$

故

$gcd(F_{n},F_{n+1})=1$

回到证明1

因为 $gcd(F_{n},F_{n+1})=1$

所以

$gcd(F_{n},F_{m-n}F_{n+1})=gcd(F_{n},F_{m-n})$

$gcd(F_{n},F_{m})=gcd(F_{n},F_{m-n})$

$gcd(F_{n},F_{m-n})=gcd(F_{n},F_{m-2n})$

...

$gcd(F_{n},F_{m})=gcd(F_{n},F_{m-(m/n)*n})$

然后 $m1=n,n1=m-(m/n)n$

再来

直到出现 $F_{0}$ ,此时 $F_{n1}$ 即我们要求的答案， $n1==gcd(n,m)$

证毕

证明2

对于斐波那契数列，我们可以这样理解

$\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1} \end{bmatrix} \quad$

即

$\begin{bmatrix}F_{n}+F_{n-1}&F_{n}+F_{n-1}\cdot0 \\ F_{n}+F_{n-1}\cdot0 & F_{n-1}+F_{n}\cdot0 \end{bmatrix} \quad$

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \quad\times\begin{bmatrix} F_{n} & F_{n-1} \\ F_{n-1} & F_{n-2} \end{bmatrix} \quad$

如此持续操作，直到出现

$\begin{bmatrix} F_{2} & F_{1} \\ F_{1} & F_{0} \end{bmatrix} \quad$

即

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \quad$

此间有 $n$ 个 $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \quad$ 相乘，即 $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \quad^{n}$

因此用矩阵乘法求快速幂即可

证毕

全部评论

推荐最新楼层

03-16 09:48

吉林农业大学算法工程师

顺丰大模型开发一面

1、LoRA 微调的原理LoRA 的核心思想是不直接更新预训练模型里的原始大权重，而是在某些线性层旁边增加一个低秩更新分支，用低秩矩阵去近似权重增量。假设原始权重是 W∈Rd×k，全量微调时直接学习ΔW，LoRA 则把它写成：ΔW=BA其中A∈Rr×k，B∈Rd×r ,，(r) 是远小于 (d) 和 (k) 的秩。这样前向计算就变成：h=Wx+ΔWx=Wx+BAx实际里通常还会加缩放项：这样做的本质是认为很多下游任务对大模型权重的更新其实存在低秩结构，不需要真的去学习一个完整的大矩阵。LoRA 的优点是可训练参数少、显存占用低、训练快，而且原模型参数冻结，方便多任务切换和权重管理。2、LoRA...

查看11道真题和解析

点赞评论收藏

03-19 15:50

已编辑

门头沟学院 C++

“白天打工，晚上谋反”

“白天打工，晚上谋反”的状态，大概是每个在职求职者最真实的写照。09:00 - 09:20 (通勤)： 刷刷各个公司的招聘更新了没？看看邮箱，收集下信息。10:00 - 12:00 (工位)： 假装忙碌。12:00 - 14:00 (吃饭+午休)：吃饭的时候可以看看八股。14:00 - 15:00 (开会)： 开会时偷偷浏览职位详情。15:00 - 18:00 (工位)： 干活。18:00 - 19:00 (吃饭+通勤)：利用空闲排一下今晚的测试和笔试时间。19:00 - 23:00 (高强度)：笔试，笔试，还是笔试。最高峰一晚上三个笔试，直接榨干了。“骑驴找马”不仅是体力的考验，更是心理的博...

如何一边实习一边找下家？

点赞评论收藏

02-24 13:27

百度_acg_千帆agent开发(实习员工)

组长说这是百度十年来第一次，我没绷住

不过还是挺开心的hhh

哈哈哈，你是老六：百度去年裁员分评不好，赶紧弄点红包

点赞评论收藏

03-14 09:36

南京信息工程大学产品经理

怎么找日常实习暑期实习

27届找实习为什么0回复0面试，是不是因为双非而且没什么项目啊啊啊，真的很需要一个实习，我已经投了很多家了，需要怎么再改改简历么？ 我投的都是数分、运营、用户类，或者有没有推荐的中小厂呀

今天你投了哪些公司？

点赞评论收藏

03-14 15:02

门头沟学院 Web前端

腾讯新闻-软件开发一面

📍面试公司：腾讯🕐面试时间：2026.3💻面试岗位：前端❓面试问题：自我介绍后针对简历上的项目一个一个的问，省略掉若干具体项目问题agents如何实现打印机的效果问我日常开发中AI的使用情况有没有用过skills或者MCP的功能有没有开发过具体的skills问性能优化，CSS如何进行压缩的，背后实现的规则和原理是什么如果让你设计vue3这样的框架需要考虑哪些东西diff算法的原理代码题（时间控制15min）：给一个整数数组num和整数k，统计并返回数组中和为k的子数组的个数🙌面试感想：就面了30min，手写代码还没共享屏幕，不会是kpi面吧

查看9道真题和解析

点赞评论收藏

全站热榜

创作者周榜

正在热议

# 把自己当AI，现在最消耗你token的问题是什么？ #

# 面试官最爱问的 AI 问题是...... #

# 正在春招的你，也参与了去年秋招吗？ #