任何解决方案都是正确的解决方案吗？

Question

在解决了我已经困扰了一段时间的编程挑战后，我总是对自己说：“它有效，这就足够了”。

在我看来，我认为这并不是真正正确的心态，并且我认为我应该始终尝试以最佳性能进行编码。

不管怎样，话虽如此，我只是尝试了一个ProjectEuler问题。具体来说就是问题#2。

我该如何改进这个解决方案。我觉得它真的很冗长。就像我在递归中传递前一个数字一样。

<?php
  /* Each new term in the Fibonacci sequence is generated by adding the previous two
     terms. By starting with 1 and 2, the first 10 terms will be:

     1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

     Find the sum of all the even-valued terms in the sequence which do not exceed
     four million.
   */
   function fibonacci ( $number, $previous = 1 ) {
     global $answer;
     $fibonacci = $number + $previous;
     if($fibonacci > 4000000) return;
     if($fibonacci % 2 == 0) {
       $answer = is_numeric($answer) ? $answer + $fibonacci : $fibonacci;
     }
     return fibonacci($fibonacci, $number);
   }
   fibonacci(1);
   echo $answer;
?>

请注意，这不是家庭作业。我几百年前就离开了学校。我只是觉得无聊，正在研究欧拉计划的问题

Answer 1

解决之后我总是在心里想
我面临的编程挑战
被束缚有一段时间了，“它
有效，这就足够了”。

我不认为这真的是
正确的心态，在我看来，我
我认为我应该一直努力
具有最佳性能的代码。

Code Complete 中介绍的经典内容之一是，程序员在给定目标的情况下，可以创建“最佳”计算机程序使用许多指标之一，但不可能同时优化所有参数。代码

• 可读性 代码
• 输出的可理解性
• 代码长度（行）
• 代码执行速度（性能）
• 编写代码的速度

随意优化这些参数中的任何一个，但请记住同时优化所有参数时间可能会让人沮丧，或者导致系统设计过度。

你应该问自己：你的目标是什么？在这种情况下什么是“足够好”？如果您只是在学习并想让事情变得更加优化，请务必去做，只是要注意，一个完美的程序需要无限的时间来构建，而时间本身就是有价值的。

Answer 2

您可以通过执行三次操作（每三个元素是偶数）来避免 mod 2 部分，因此它显示为：
$斐波那契 = 3*$数字 + 2*$前一个；
斐波那契的新输入是 ($fibonnacci,2*$number+$previous)
我对 php 不熟悉，所以这只是一般算法建议，我不知道这是否是正确的语法。这实际上是相同的运算，只是用一些乘法代替了模数和加法。

另外，请确保以 $number 为偶数开始，将 $previous 作为序列中位于其前面的奇数开始（您可以以 $number 为 2 开始，$previous 为 1，并且总和也从 2 开始） 。

Answer 3

忘记斐波那契（问题2），我说的是欧拉的前进。不要浪费时间寻找每个问题的最佳代码。

如果您的答案达到一分钟规则，那么您就可以尝试下一个。在出现几个问题之后，事情会变得更加困难，您将在编写代码时优化代码以实现该目标

Answer 4

这里的其他人也说过“这是示例问题与实际业务问题的问题的一部分”

由于多种原因，这个问题的答案很难回答：

• 语言起着巨大的作用角色。有些语言更适合某些问题，所以如果你遇到不匹配的情况，你会发现你的解决方案“不够雄辩”，
• 这取决于你有多少时间来解决问题，解决问题的时间越多您越有可能找到您喜欢的解决方案（尽管有时情况相反，而且太多的时间会让您过度思考），
• 这取决于您的总体满意度。我参与过几个项目，我认为有些部分很棒并且编码很漂亮，而其他部分则完全是垃圾，但它们超出了我有时间解决的范围。

我想最重要的是，如果您认为这是一个好的解决方案，并且您的客户/采购商/团队等同意，那么它目前是一个好的解决方案。您将来可能会改变主意，但目前这是一个很好的解决方案。

Answer 5

使用解决问题的代码执行时间不应超过一分钟的准则。在我看来，这是欧拉问题中最重要的事情。

除此之外，只需确保它是可读的 - 确保您可以轻松地看到代码是如何工作的。这样，如果您遇到像您解决的欧拉问题之一这样的问题，您可以更轻松地了解事情是如何运作的，这反过来又可以让您更快地解决该问题 - 因为您已经知道应该如何解决它。

你可以为自己设定其他标准，但我认为这超出了欧拉问题的意图——对我来说，问题的背景似乎比其他任何东西都更适合关注效率和可读性

Answer 6

我实际上并没有对此进行测试......但在将其称为“完成”之前，我个人会尝试在此解决方案中解决一些问题。

通过使用 sum 参数实现递归来尽可能避免全局变量

编辑：根据 nnythm 的算法推荐进行更新（酷！）

function fibonacci ( $number, $previous, $sum ) {
    if($fibonacci > 4000000) { return $sum; }
    else {
        $fibonacci = 3*$number + 2*$previous;
        return fibonacci($fibonnacci,2*$number+$previous,$sum+$fibonacci); 
    }
}
echo fibonacci(2,1,2);

Answer 7

[耸肩]

解决方案应该根据需求进行评估。如果所有的要求都满足了，那么其他的一切都是moxy的。如果满足所有要求，并且您个人对解决方案不满意，那么也许需要重新评估需求。这就是你能接受这个形而上学问题的最大程度了，因为我们开始讨论项目管理和业务之类的事情：咳咳

，关于你的欧拉项目问题，我只需要两便士：

1. 考虑重构为迭代，而不是迭代递归
2. 注意该系列中的每第三项都是偶数？一旦给出起始术语，就不需要取模

例如

public const ulong TermLimit = 4000000;

public static ulong CalculateSumOfEvenTermsTo (ulong termLimit)
{
    // sum!
    ulong sum = 0;

    // initial conditions
    ulong prevTerm = 1;
    ulong currTerm = 1;
    ulong swapTerm = 0;

    // unroll first even term, [odd + odd = even]
    swapTerm = currTerm + prevTerm;
    prevTerm = currTerm;
    currTerm = swapTerm;

    // begin iterative sum,
    for (; currTerm < termLimit;)
    {
        // we have ensured currTerm is even,
        // and loop condition ensures it is 
        // less than limit
        sum += currTerm;

        // next odd term, [odd + even = odd]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;

        // next odd term, [even + odd = odd]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;

        // next even term, [odd + odd = even]
        swapTerm = currTerm + prevTerm;
        prevTerm = currTerm;
        currTerm = swapTerm;
    }
    return sum;
}

，也许需要更多行代码，但[实际上]保证会更快。迭代方法并不那么“优雅”，但可以节省递归方法调用并节省堆栈空间。其次，展开项生成（即显式扩展循环）减少了必须执行模数运算和测试“偶数”条件的次数。扩展还可以减少结束条件[如果当前项小于限制]的计算次数。

它是“更好”吗？不，这只是“另一种”解决方案。

对于 C# 的歉意，不熟悉 php，但我相信你可以很好地翻译它。

希望这有帮助，:)

干杯

Answer 8

无论您对解决方案感到满意还是想要进一步改进它，这完全是您的选择。有许多项目欧拉问题，其中暴力解决方案将花费太长时间，并且您必须寻找聪明的算法。

问题2不需要任何优化。您的解决方案已经足够快了。
还是让我解释一下什么样的优化是可能的。对这个主题进行一些研究通常会有所帮助。例如 斐波那契数 上的 wiki 页面包含此公式

fib(n) = (phi^n - (1-phi)^n)/sqrt(5)

其中 phi 是黄金比例。 IE

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

如果您使用 fib(n) 大约为 phi^n/sqrt(5) 那么您可以找到小于 M 的最大斐波那契数的索引

n = 楼层(log(M * sqrt(5)) / log(phi))。

例如，对于 M=4000000，我们得到 n=33，因此 fib(33) 是小于 4000000 的最大斐波那契数。可以观察到，即使 n 是 3 的倍数，fib(n) 也是偶数。因此偶数之和斐波那契数列是

fib(0) + fib(3) + fib(6) + ... + fib(3k)

要找到闭合形式，我们使用维基百科页面中的上述公式并注意：
总和本质上只是两个几何级数。数学并不是完全微不足道的，但使用这些想法可以证明：

fib(0) + fib(3) + fib(6) + ... + fib(3k) = (fib(3k + 2) - 1) /2 。

由于 fib(n) 的大小为 O(n)，因此直接解的复杂度为 O(n^2)。
使用上面的封闭公式和快速方法来评估斐波那契数
复杂度为 O(n log(n)^(1+epsilon))。对于数量较少的情况，这两种解决方案当然都可以。