寻找下一个斐波那契数

Question

我需要找到一个（下一个）斐波那契数，给定一个整数N。假设我有n = 13，我需要输出下一个斐波那契数，也就是21，但是我该怎么做？我如何找到前一个数字，将它们相加形成它？

我的意思是，我可以很容易地想出一个for / while循环，返回斐波那契序列，但是如何通过给定上一个数字来找到下一个数字呢？

<?php

$n = 13;

while($n < 1000) {

    $n = $x + $y; 
    echo($n."<br />"); 
    $x = $y;
    $y = $n;
}
?>

- Mike Fonder

---

为什么不创建一个循环，它比输入的总和多进行一次迭代呢？这可能不是最有效的方法，但它是一种方法。 - Brandon White

可能是关于进入给定项的两个数字的比率吗？这些数字的比率趋向于1.618。那么很容易算出这两个整数是什么吗？将给定术语除以1.618以了解其中一个数字的大致值？ - Ryan Vincent

Answer 1

您可以使用 Binet's Formula（比奈公式）来计算斐波那契数列：

          n          -n
F(n) = phi   - (-phi)
       ---------------
          sqrt(5)

其中 phi 是黄金比例(( 1 + sqrt(5) ) / 2) ~= 1.61803...

这可以帮助您精确确定数列的第 n 项。

- Marc B

---

我该如何在PHP中实现这个呢？ - Mike Fonder

但这并不能帮助找到最接近给定数字的斐波那契数。 - hindmost

@hindmost 你可以使用公式找到 F(n) = 13 的 n 值，然后再使用该公式计算 n-1。 - Jim

@hindmost：当然可以。开始填写n值并使用二进制搜索来缩小可能的值范围。甚至一个简单的循环也是可行的$i = 0; while(F($i) <= $search_value) { $i++; }。 - Marc B

@MikeFonder：这只是数学问题。PHP可以通过pow()进行指数运算，在v5.6+版本中，甚至还有**运算符。 - Marc B

Answer 2

使用循环，您可以将值存储在数组中，并在找到前一个键的值中选择的数字后立即停止一次。

function getFib($n) {

   $fib = array($n+1);       // array to num + 1
   $fib[0] = 0; $fib[1] = 1; // set initial array keys
   $i;

   for ($i=2;$i<=$n+1;$i++) {
      $fib[$i] = $fib[$i-1]+$fib[$i-2];
        if ($fib[$i] > $n) { // check if key > num 
            return $fib[$i];
            }
        }
    if ($fib[$i-1] < $n) {   // check if key < num
        return $fib[$i-1] + $n;
    }
    if ($fib[$i] = $n-1) {   // check if key = num
        return $fib[$i-1] + $fib[$i-2];
    } 
    if ($fib[$i-1] = 1) {    // check if num = 1
        return $n + $n;
    }
}

$num = 13;
echo "next fibonacci number = " . getFib($num);

请注意，我没有测试过这个代码，所以它可能需要优化。在投票之前，请考虑这只是回答问题的一个概念。

- l'L'l

---

这个完美无缺。感谢您的时间 :) - Mike Fonder

不客气，很高兴能帮到你。如果你想更进一步，你可以让它识别$num是否为斐波那契数。这是一个可行的例子：http://ideone.com/vr5bJH - l'L'l

是的，之后我写了类似的东西。不管怎样，我有另一个快速问题。如何获取序列的前N个成员？到目前为止，我只想到了这个：http://pastebin.com/qHvjUzdC但是以这种方式，我只输出从3开始的数字，而我还需要0、1、1和2作为斐波那契数列的开头。 - Mike Fonder

Answer 3

你可以在一步中完成它：

phi = (1+sqrt(5))/2

next = round(current*phi)

（其中round是一个返回最接近整数的函数；基本上等同于floor(x+0.5)）

例如，如果您当前的数字为13：13 * phi = 21.034441853748632，四舍五入为21。

- 12Me21

---

这个方法只适用于N已经是斐波那契数列中的数字，但对于例如N=4的情况则不适用。 - Simon