N Algorithmen für die Fibonacci-Sequenz in PHP

Vorwort

Vor einiger Zeit bin ich auf die herkömmliche rekursive Methode zur Optimierung der Berechnung von Fibonacci-Zahlen gestoßen, aber mir fiel nicht rechtzeitig eine gute Methode ein, also suchte ich später nach relevanten Informationen und Vieles zusammengefasst Es gibt eine Berechnungslösung, also teilen Sie sie und kommunizieren und lernen Sie mit allen.

Empfohlen: „PHP Video Tutorial“

Was sind Fibonacci-Zahlen? daher wird sie auch „Kaninchenfolge“ genannt, was sich auf eine solche Folge bezieht: 1, 1, 2, 3, 5, 8, 13, 21, 34,… …Mathematisch ist die Fibonacci-Folge rekursiv wie folgt definiert: F (1)=1, F(2)=1, F(n)=F(n - 1)+F(n - 2) (n ≥ 3, n ∈ N*).

Da wir nun die Fibonacci-Zahlen kennen, werden wir verschiedene Methoden verwenden, um die N-te Fibonacci-Zahl zu berechnen und zu erhalten.

Gewöhnliche Rekursion

斐波那契数，那么下面我们就用多种不同的方法来计算获取第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

Diese Methode ist die konventionellste. Sie kann rekursiv gemäß der Definition F(n)=F(n - 1)+F(n - 2) berechnet werden. aber die Leistung ist minimal.

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

Rekursive Optimierung

Wie Sie der obigen rekursiven Methode entnehmen können, werden viele Berechnungen wiederholt und die Leistung ist extrem schlecht. Wenn N größer ist, ist die Anzahl der Berechnungen zu schrecklich Da sich wiederholte Berechnungen auf die Leistung auswirken, beginnt die Optimierung mit der Reduzierung wiederholter Berechnungen, d. h. dem Speichern der vorherigen Berechnungen, wodurch zu viele wiederholte Berechnungen vermieden und der rekursive Algorithmus optimiert werden.

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

Speicher von unten nach oben

Bottom-up berechnet das Teilproblem der Fibonacci-Zahlen iterativ, speichert die berechneten Werte und führt Berechnungen basierend auf den berechneten Werten durch. Verwenden Sie for-Schleifen, um durch Rekursion verursachte Doppelberechnungsprobleme zu reduzieren. rrreee

Iterieren Sie von unten nach oben

Initialisieren Sie die Zuweisung des niedrigsten Bits, verwenden Sie for, um iterativ vom niedrigen Bit zum hohen Bit zu berechnen und so die N-te Zahl zu erhalten.
rrreee

🎜Formelmethode🎜🎜🎜Wenn Sie die Beziehung zwischen der Fibonacci-Folge und dem Goldenen Schnitt verstehen, verwenden Sie den Goldenen Schnitt, um die N-te Fibonacci-Zahl zu berechnen. 🎜rrreee🎜🎜Die unbesiegbare Methode🎜🎜🎜Ich werde nicht näher auf diese Methode eingehen, jeder kennt sie, aber probieren Sie sie nicht einfach aus ...🎜🎜🎜🎜🎜🎜rrreee🎜🎜Endlich🎜🎜🎜Okay, Ich habe mehrere Lösungen grob geschrieben, bitte weisen Sie darauf hin und ich werde es rechtzeitig ändern. Wenn Sie andere Berechnungsmethoden haben, können Sie diese gerne teilen, um gemeinsam zu kommunizieren und zu lernen. 🎜🎜🎜🎜

Das obige ist der detaillierte Inhalt vonN Algorithmen für die Fibonacci-Sequenz in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!