PHP 斐波那契数列

 PHP 常用例子

斐波那契项通常表示为F_n。斐波那契项是前两项的总和，以 0 和 1 开头。在数学上，它可以表示为:

F_n = F_n-1 + F_n-2

边界条件:F₀ = 0 和 F₁ = 1

斐波那契数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233.. .

方法一:使用递归函数

在下面的示例中，创建了一个名为 fib() 的递归函数来找出斐波那契数的第 n 项

<?php
function fib($n) {
  if ($n == 0)
    {return 0;}
  elseif ($n == 1)
    {return 1;}
  else
    {return fib($n-1) + fib($n-2);}
}

echo "Fibonacci 5th term: ".fib(5)."\n";
echo "Fibonacci 6th term: ".fib(6)."\n";
echo "Fibonacci 7th term: ".fib(7)."\n";
?> 

上面的代码将给出以下输出:

Fibonacci 5th term: 5
Fibonacci 6th term: 8
Fibonacci 7th term: 13 

方法 2:使用动态编程

斐波那契项也可以是使用动态规划进行估计。与递归函数相比，它只计算一次序列的特定项。

<?php
function fib($n) {
  //创建包含斐波那契项的数组
  //int f[n+1];
  $f = array();
  $f[0] = 0;
  $f[1] = 1;
  for($i = 2; $i <= $n ; $i++) {
    $f[$i] = $f[$i-1] + $f[$i-2];
  }
  return $f[$n];
}

echo "Fibonacci 6th term: ".fib(6)."\n";
echo "Fibonacci 7th term: ".fib(7)."\n";
echo "Fibonacci 8th term: ".fib(8)."\n";
?> 

上面的代码将给出以下输出:

Fibonacci 6th term: 8
Fibonacci 7th term: 13
Fibonacci 8th term: 21 

方法3:使用三元运算符

这也可以使用三元运算符来实现。

<?php
function fib($n) {
  $y = ($n == 0)? 0 : (($n == 1) ? 1 : fib($n-1) + fib($n-2));
  return $y;
}

echo "Fibonacci 8th term: ".fib(8)."\n";
echo "Fibonacci 9th term: ".fib(9)."\n";
echo "Fibonacci 10th term: ".fib(10)."\n"; 
?> 

上面的代码将给出以下输出:

Fibonacci 8th term: 21
Fibonacci 9th term: 34
Fibonacci 10th term: 55 

方法4 :空间优化方法

在该方法中，仅使用三个变量，这些变量在每次迭代中都会发生变化，最终计算出斐波那契数列的第n项。

<?php
function fib($n) {
  $a = 0; $b = 1; $c = 0;
  if ($n == 0)
    {return $a;}
  for($i = 2; $i <= $n; $i++) {
    $c = $a + $b;
    $a = $b;
    $b = $c;    
  }
  return $b;
}

echo "Fibonacci 9th term: ".fib(9)."\n";
echo "Fibonacci 10th term: ".fib(10)."\n";    
echo "Fibonacci 11th term: ".fib(11)."\n";
?> 

上面的代码将给出以下结果输出:

Fibonacci 9th term: 34
Fibonacci 10th term: 55
Fibonacci 11th term: 89 

方法5:使用矩阵的幂

斐波那契数列项也可以计算为矩阵的幂。斐波那契数列具有以下属性:

计算F_n,计算并A₀₁ 将是 F_n。

<?php
function fib($n) {
  $initial = array(array(1,1),array(1,0));
  $Final = array(array(1,1),array(1,0));

  if ($n == 0)
    {return 0;}
  else {      
    for($i = 1; $i < $n ; $i++) {
      $a = $Final[0][0]*$initial[0][0] + $Final[0][1]*$initial[1][0];
      $b = $Final[1][0]*$initial[0][0] + $Final[1][1]*$initial[1][0];
      $c = $Final[0][0]*$initial[0][1] + $Final[0][1]*$initial[1][1];
      $d = $Final[1][0]*$initial[0][1] + $Final[1][1]*$initial[1][1];
      $Final[0][0] = $a;
      $Final[1][0] = $b;
      $Final[0][1] = $c;
      $Final[1][1] = $d;           
    }
  }
  return $Final[0][1];
}

echo "Fibonacci 10th term: ".fib(10)."\n";    
echo "Fibonacci 11th term: ".fib(11)."\n";
echo "Fibonacci 12th term: ".fib(12)."\n";
?> 

上面的代码将给出以下输出:

Fibonacci 10th term: 55
Fibonacci 11th term: 89
Fibonacci 12th term: 144