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}$

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

证毕

全部评论

推荐最新楼层

昨天 15:55

同济大学测试工程师

字节：没有稳定性可言，每天都在拥抱变化

你永远不知道leader和员工谁会突然离职 看似稳如老狗的同事，其实早就失望透顶准备跑路来组里三个月，资历已经是组里第三了

投递字节跳动等公司8个岗位 >

点赞评论收藏

分享

06-20 17:44

已编辑

门头沟学院产品经理

宝宝找不到暑期实习也没关系哒

暑期实习三个月，只是你人生八十年甚至九十年短短的一个moment。暑期实习三个月，转正50-80%不等。宝宝，你真的愿意all in去赌吗？暑期实习三个月，各家都要求至少满60个工作日才能发起转正。如果你现在入职，九月份才能发起转正。你没有办法参加所在公司的八月份甚至七月份的秋招提前批，你可能会为了手里这份概率惴惴不安上好一阵子。所以宝宝，请你不用焦虑。你可以再刷一段舒服的且有成长空间的日常实习你可以现在开始全力准备秋招，好好包装自己的项目，争取秋招面试打一场漂亮的开场战你可以回家陪一陪爸爸妈妈爷爷奶奶外公外婆你可以畅快的去玩上一个月，毕竟未来工作了也没有时间了可以做的事情还有很多，找不到暑期...

点赞评论收藏

分享

05-07 09:53

未填写教育信息嵌入式工程师

找一个多月了0offer，真要进电子厂了吗😭有没有补救方法😭    

重生我想学测开：嵌入式的问题，我准备入行京东外卖了

点赞评论收藏

分享

06-11 12:35

合肥工业大学 Java

27暑期日常太难找了

楼主爆肝五个月，算法八股技术栈项目都达到了现阶段暂时的瓶颈，本来下定决心暑假实习的，可是投出去的简历全都杳无音讯一个面试也没有😭😭😭最后还找不到的话不知道该找小小厂还是回去接着沉淀

牛客刘北：如果暑期实习是27届的话，你要晚一年才会毕业，企业为什么会等你呢？要搞清时间逻辑呀！27届现在实习只能是在暑假实习，这是日常实习，不是暑期实习。所以多去投日常实习吧，暑期实习肯定不会要你的

点赞评论收藏

分享

昨天 18:00

门头沟学院 Java

舍友已经找到实习，是我太菜了吗，好焦虑

本人是双非本科大二在读生，暑假想找实习做项目丰富自己的经历。大一的实习是托关系去的，现在大二自己去海投根本就是石沉大海。家在深圳，在深圳都找不到互联网工作舍友是走前端的，现在就能找到月6k的实习了，是我太菜了吗……计划找不到实习就继续推进手里的项目再在网上学做一些完整的项目，比如苍穹外卖、点评什么的，有没有好的推荐。还是说去找数据标注这种实习，但本人觉得没有什么含金量。求大佬们指导

点赞评论收藏

分享

评论

点赞

收藏

全站热榜

更多

创作者周榜

更多

正在热议

更多

# 为了找工作你花了哪些钱？ #

10171次浏览 102人参与

# 你秋招想去哪些公司 #

2030次浏览 69人参与

# 第一份工作能做外包吗？ #

12644次浏览 138人参与

# 国企/银行/研究所公司爆料 #

138555次浏览 805人参与

# 我的职场心眼子段位 #

21651次浏览 542人参与

# 26届校招投递进展 #

1236次浏览 32人参与

# 打工人的至爽时刻or至暗时刻 #

30394次浏览 201人参与

# 你见过最离谱的招聘要求是什么？ #

194134次浏览 1443人参与

# 如果不考虑收入，你最想做什么工作？ #

22026次浏览 133人参与

# 如何看待应届生身份？ #

118646次浏览 1155人参与

# 大学四年该怎么过，才不算浪费时间？ #

5890次浏览 58人参与

# 金融财会交流会 #

109137次浏览 377人参与

# 2022届毕业生现状 #

823611次浏览 7168人参与

# 商战，最累的是我们 #

17588次浏览 78人参与

# 互联网公司爆料 #

124808次浏览 684人参与

# 计算机专业还有必要去大厂卷吗 #

24969次浏览 151人参与

# 还记得你第一次面试吗？ #

200687次浏览 2943人参与

# 工作一周年分享 #

28260次浏览 153人参与

# 硬件人的简历怎么写 #

280759次浏览 2956人参与

# 你知道哪些职场黑话？ #

47214次浏览 391人参与

牛客网
牛客网在线编程
牛客网题解
牛客企业服务