【算法】如果玉兔遇到莱昂纳多 · 斐波那契,那明年中秋嫦娥在月亮上会拥有几只玉兔?
马上中秋节就要到了,也不知道我家嫦娥在月亮上过的怎么样,玉兔还陪在她身边吗?
引子
今天我们来探讨一个有趣的问题,如果玉兔遇到莱昂纳多·斐波那契,那明年中秋嫦娥在月亮上会拥有几只玉兔呢?
我们知道意大利数学家莱昂纳多·斐波那契在《算法全书》中提出了 斐波那契兔子问题(Fibonacci rabbit problem) 一道著名数列难题~
注意,我们的玉兔是神兽,可以直接独立繁衍,而且我们的玉兔永远不会去世~
- 第一个月:一只小玉兔1
- 第二个月:小玉兔1长成大玉兔1
- 第三个月:大玉兔1生了一只小玉兔2
- 第四个月:大玉兔1又生了一直小玉兔3,小玉兔2长成了大玉兔2
- ......
我们画个图看看,玉兔是怎么繁衍的,编号相同的玉兔表示是同一只玉兔~
那我们的问题就是第十二个月的时候,嫦娥拥有多少只玉兔呢?
斐波那契兔子数列问题建模
对上述的斐波那契“玉兔”问题进行建模可以得到斐波那契数列:
1,1,2,3,5,8,...1,1,2,3,5,8,...1,1,2,3,5,8,...
数列从第三项开始,每一项等于前两项之和,我们要求明年中秋嫦娥在月亮上拥有多少玉兔,也就是数列的第121212项~
我们将数学问题转换成计算机编程问题:
写一个函数,输入 nnn ,求斐波那契(Fibonacci)数列的第 nnn 项(即 F(N)F(N)F(N))。
斐波那契数列的定义如下: F(0)=0,F(1)=1F(0) = 0, F(1) = 1F(0)=0,F(1)=1 F(N)=F(N−1)+F(N−2)F(N) = F(N - 1) + F(N - 2)F(N)=F(N−1)+F(N−2), 其中 N>1N > 1N>1.
斐波那契数列由 000 和 111 开始,之后的斐波那契数就是由之前的两数相加而得出。
解析
暴力递归
就直接暴力递归,就可以算出我们需要的答案
function fib(n) {
if( n === 0) return 0
if(n === 1) return 1
return fib(n-1) + fib(n-2)
};
let result = fib(12)
console.log(result) // 144
所以,如果玉兔遇到莱昂纳多 · 斐波那契,那明年中秋嫦娥在月亮上会拥有144只玉兔!!!
这种无脑解法可以初步解决问题,如果我们要求十年后的情况呢?
这样暴力起来效率实在太低,我们仔细思考一下,它的可优化空间还是很大!
首先一个问题就是这里重复递归的次数实在是太多了,比如说我要求fib(5),
如图可视,我们重复求解了多次fib(2)和fib(3)其实这是没有必要的,我们可以用一个缓存cache,来将我们求过了的fib(n)保存在缓存中,下次用到他的时候直接读取他的值就可以了,而不是再重新递归求值,
递归 + 缓存
// 首先定义一个缓存数组,用来存放求出来的Fib(k)的值 k = 2, ... , n
let cache = [];
function fib(n) {
// 如果缓存中已经有这个值了,就直接返回,不要再递归求值了
if (cache[n] !== undefined) {
return cache[n];
}
// 两个初始值
if (n === 0) return 0;
if (n === 1) return 1;
// 递归求得fib(n)
let v = fib(n - 1) + fib(n - 2);
// 将fib(n)保存在cache[n]的位置
cache[n] = v;
// 返回fib(n)
return v;
}
这样我们就甚至可以计算十年后的情况了
动态规划
我们可以创建一个dp数组,也就是我们的斐波那契数列。
function fib(n) {
let dp = [];
// base case
dp[1] = dp[2] = 1;
for (let i = 3; i <= n; i++) {
// 状态转移方程
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
加了缓存的递归以及上面的动态规划数组减少了很多重复计算,提高了效率,但是还是可以继续在空间上进行优化的,我们直接用两个变量接收后面一个计算需要的结果,这样就不需要一个数组了~
function fib(n) {
if (n < 2) return n;
let i = 0;
let j = 1;
let sum = 1;
// 每循环一次,将i和j的值相加得到sum放在j后面,将i和j都后移一位
for (let k = 2; k < n; k++) {
i = j;
j = sum;
sum = i + j;
}
return sum;
}
最后
所以说,如果玉兔遇到莱昂纳多 · 斐波那契,那明年中秋嫦娥在月亮上会拥有144只玉兔!!!
如果是十年后,月球上就有大约5.358359254990968e+24只玉兔~
最后的最后,提前祝大家中秋节快乐~~
转载自:https://juejin.cn/post/7007341127900626957