外贸站外推广,凡科网的网站建设好用吗,成都微信小程序商城,上海手工活外发加工网前言前段时间#xff0c;遇到优化计算斐波那契数列的常规递归方法#xff0c;但是一时间并没有及时想到很好的方法#xff0c;所以后面查找了相关资料#xff0c;总结了多种计算解法#xff0c;所以分享出来#xff0c;和大家一起交流学习。斐波那契数是什么斐波那契数列…前言前段时间遇到优化计算斐波那契数列的常规递归方法但是一时间并没有及时想到很好的方法所以后面查找了相关资料总结了多种计算解法所以分享出来和大家一起交流学习。斐波那契数是什么斐波那契数列(Fibonacci sequence)又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入故又称为“兔子数列”指的是这样一个数列1、1、2、3、5、8、13、21、34、……在数学上斐波那契数列以如下被以递推的方法定义F(1)1F(2)1, F(n)F(n - 1)F(n - 2)(n ≥ 3n ∈ N*)。知道了斐波那契数那么下面我们就用多种不同的方法来计算获取第N位斐波那契数。普通递归这种方法是最常规的直接根据定义F(n)F(n - 1)F(n - 2)递归计算即可但是性能是最低的。/*** 普通递归* param int $n* return int*/function fib($n 1){// 低位处理if ($n 3) {return 1;}// 递归计算前两位return fib($n - 1) fib($n - 2);}递归优化从上面的递归方法可以看到进行了很多的重复计算性能极差如果N越大计算的次数太可怕了那么既然因为重复计算影响了性能那么优化就从减少重复计算入手即把之前计算的存储起来这样就避免了过多的重复计算优化了递归算法。/*** 递归优化* param int $n* param int $a* param int $b* return int*/function fib_2($n 1, $a 1, $b 1){if ($n 2) {// 存储前一位优化递归计算return fib_2($n - 1, $a $b, $a);}return $a;}记忆化自底向上自底向上通过迭代计算斐波那契数的子问题并存储已计算的值通过已计算的值进行计算。使用for循环减少递归带来的重复计算问题。/*** 记忆化自底向上* param int $n* return int*/function fib_3($n 1){$list [];for ($i 0; $i $n; $i) {// 从低到高位数依次存入数组中if ($i 2) {$list[] $i;} else {$list[] $list[$i - 1] $list[$i - 2];}}// 返回最后一个数即第N个数return $list[$n];}自底向上进行迭代最低位初始化赋值使用for从低位到高位迭代计算从而得到第N个数。/*** 自底向上进行迭代* param int $n* return int*/function fib_4($n 1){// 低位处理if ($n 0) {return 0;}if ($n 3) {return 1;}$a 0;$b 1;// 循环计算for ($i 2; $i $n; $i) {$b $a $b;$a $b - $a;}return $b;}公式法通过了解斐波那契序列和黄金分割比之间的关系使用黄金分割率计算第N个斐波那契数。/*** 公式法* param int $n* return int*/function fib_5($n 1){// 黄金分割比$radio (1 sqrt(5)) / 2;// 斐波那契序列和黄金分割比之间的关系计算$num intval(round(pow($radio, $n) / sqrt(5)));return $num;}无敌欠揍法这个方法我就不多说了吧大家都懂的但是千万别轻易尝试……/*** 无敌欠揍法* param int $n* return int*/function fib_6($n 1){// 列举了30个数$list [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269];return $list[$n];}最后好了我就大概写了几种解法如果有不对的地方请大家指出我会及时修改大家有其他计算方法欢迎分享出来一起交流和学习谢谢
