N algorithms for Fibonacci sequence in PHP

Preface

Some time ago, I encountered the conventional recursive method of optimizing the calculation of the Fibonacci sequence, but once Time did not come up with a good method in time, so I searched for relevant information later and summarized a variety of calculation solutions, so I shared it with everyone to communicate and learn together.

Recommended: "PHP Video Tutorial"

What are Fibonacci numbers

Fibonacci The Fibonacci sequence, also known as the golden section sequence, was introduced by the mathematician Leonardoda Fibonacci using rabbit breeding as an example, so it is also called the "rabbit sequence". It refers to this A sequence of numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34,... Mathematically, the Fibonacci sequence is defined recursively as follows: F(1)=1, F (2)=1, F(n)=F(n - 1) F(n - 2) (n ≥ 3, n ∈ N*).

Now that we knowFibonacci numbers, then we will use a variety of different methods to calculate and obtain the Nth Fibonacci number.

Ordinary recursion

This method is the most conventional, directly based on the definitionF(n)=F(n - 1) F(n - 2 )Recursive calculation is enough, but the performance is the lowest.

/**
 * 普通递归
 * @param int $n
 * @return int
 */function fib($n = 1){    // 低位处理
    if ($n < 3) {        return 1;
    }    // 递归计算前两位
    return fib($n - 1) + fib($n - 2);
}

Recursive optimization

As you can see from the above recursive method, a lot of repeated calculations are performed, and the performance is extremely poor. If N is larger, the number of calculations will be too many. It's terrible. Well, since repeated calculations affect performance, optimization starts with reducing repeated calculations, that is, storing previously calculated calculations, thus avoiding too many repeated calculations and optimizing the recursive algorithm.

/**
 * 递归优化
 * @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;
}

Memory bottom-up

Bottom-up calculates the sub-problem of Fibonacci numbers iteratively and stores the calculated value, passing the calculated value Calculation. Use for loops to reduce double calculation problems caused by recursion.

/**
 * 记忆化自底向上
 * @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];
}

Iterate from the bottom up

The lowest bit is initialized and assigned, use for to iterate from the low bit to the high bit to obtain the Nth number .

/**
 * 自底向上进行迭代
 * @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;
}

Formula method

By understanding the relationship between the Fibonacci sequence and the golden ratio, use the golden ratio to calculate the N Fibonacci numbers.

/**
 * 公式法
 * @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;
}

Invincible Beating Method

I won’t go into detail about this method. Everyone knows it, but don’t try it easily...

/**
 * 无敌欠揍法
 * @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];
}

Finally

Okay, I just wrote a few solutions. If there is something wrong, Please point it out and I will revise it in time. If you have other calculation methods, you are welcome to share them to communicate and learn together. Thank you!

The above is the detailed content of N algorithms for Fibonacci sequence in PHP. For more information, please follow other related articles on the PHP Chinese website!