【斐波那契】原来困扰多年的生兔子问题竟然能够轻松拿捏...万能公式法...

本文主要是介绍【斐波那契】原来困扰多年的生兔子问题竟然能够轻松拿捏...万能公式法...,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

上篇文章我们讲解了「矩阵快速幂」技巧,通过快速幂极大的优化了 斐波那契数列 的求解问题。并且通过分析知道了 系数矩阵 是解决问题的关键。

本文我们继续深化对于 系数矩阵 的求解,介绍一种通用方法,一举解决所有 斐波那契及变种类型 的问题。

提示: 先看 上篇文章 效果更佳哦~

生兔子问题

有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不会死,问第 N 月有多少对兔子?

这道题不是典型的斐波那契数列么,递推公式为:

这和上道题目一模一样,根本不需要讲解。但是,我们对于本题进行一定的改编,增加点儿难度


假设,现有一对成熟的兔子,新出生的兔子从出生的 第 4 个月 开始每月生一对兔子,问第 N 月有多少对兔子呢?

注意:

  1. 第一月已经有成熟的兔子了,所以从第二月开始就有新的兔子诞生了。
  2. 新出生的兔子三个月后才会生新的兔子。

通过分析不难发现:

因此,递推表达式为:

(如果这样不容易想出来,也可以自己动手列举列举,多写几项就能观察出规律啦)

关系推导

按照 上篇文章 的思路,我们做如下推导:

温馨提示:先看上篇文章更好理解哦~

三个相邻项 写成矩阵形式,由此可以得到关系式:

因此系数矩阵就得到了,后续的求解和上篇文章的简直一模一样了~

-----------------------桥豆麻袋---------------------

有小伙伴说了,这个系数矩阵不太会搞出来啊,那怎么办呢?有什么无脑办法么…哎,还真有!

这就要拿出我们初中就学过的万能的 待定系数法 了。

不就是一个系数矩阵嘛,我直接全设成未知数,一个一个解出来不就行了~

九个未知数,需要九个式子:

虽然看着麻烦,其实解起来也还行吧~哈哈哈,这样我们依然能够得到系数矩阵。

有了系数矩阵之后,就可以将第 n 项化简成只与前 3 项有关的式子。

即系数矩阵的 n-3 次方的第一行与 F3, F2, F1 的内积和。

代码

public static int f(int n) {if (n < 1) {return 0;}if (n == 1 || n == 2 || n == 3) {return n;}int[][] base = { { 1, 0, 1 }, { 1, 0, 0 }, { 0, 1, 0 } };int[][] res = matrixPower(base, n - 3);return 3 * res[0][0] + 2 * res[0][1] + res[0][2];
}private static int[][] matrixPower(int[][] m, int p) {int[][] res = new int[m.length][m[0].length];for (int i = 0; i < res.length; i++) {res[i][i] = 1;}int[][] t = m;for (; p != 0; p >>= 1) {if ((p & 1) != 0) {res = produce(res, t);}t = produce(t, t);}return res;
}private static int[][] produce(int[][] a, int[][] b) {int n = a.length;int m = b[0].length;int k = a[0].length;int[][] ans = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int c = 0; c < k; c++) {ans[i][j] += a[i][c] * b[c][j];}}}return ans;
}

只需在上篇文章代码中,将 f() 函数中初始边界条件、系数矩阵 以及 次方数和返回结果进行修改即可,另外两个函数无需做任何改变(具体细节可以参考 上篇文章 哦~)。

总结

通过本文的探讨,再次验证了 求解系数矩阵 就是解决此类斐波那契递推的关键。我们可以将结论进行适当推广:

当递推式是关于 F(n) 直到 F(n-i) 的,那么就可以将 i 项组合成一个矩阵,进行求解,此时需要构造一个 i*i 的系数矩阵,最终答案与 n-i 次方i 项已知项的内积 有关。


学习到这里,我们就得到了 斐波那契类型题万能解法 了,稍微有点难度哦 ~~~ 点赞、转发让你的小伙伴们一起来学吧!!!

~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~!!!

关注回复「ACM紫书」获取 ACM 算法书籍~

这篇关于【斐波那契】原来困扰多年的生兔子问题竟然能够轻松拿捏...万能公式法...的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/938652

相关文章

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》:本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件:2、死锁示例代码3、如何检测死锁?3.1 使用 jstack3.2

解决JSONField、JsonProperty不生效的问题

《解决JSONField、JsonProperty不生效的问题》:本文主要介绍解决JSONField、JsonProperty不生效的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录jsONField、JsonProperty不生效javascript问题排查总结JSONField

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》:本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socket read timed out的问题

《如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socketreadtimedout的问题》:本文主要介绍解决Druid线程... 目录异常信息触发场景找到版本发布更新的说明从版本更新信息可以看到该默认逻辑已经去除总结异常信息触发场景复