0

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

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

无论如何，话虽如此，我只是尝试了一个 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;
?>

请注意，这不是家庭作业。几百年前我离开了学校。我只是觉得无聊，正在处理 Project Euler 的问题

4

8 回答 8

7

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

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

Code Complete中呈现的经典内容之一是，给定目标的程序员可以使用许多指标之一创建“最佳”计算机程序，但不可能同时针对所有参数进行优化。参数如

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

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

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

于 2010-03-02T18:01:32.803 回答
2

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

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

于 2010-03-02T18:15:59.763 回答
1

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

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

于 2010-03-14T14:01:28.417 回答
0

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

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

您可以为自己设置其他标准​​，但我认为这超出了欧拉问题的意图 - 对我来说，问题的上下文似乎更适合专注于效率和可读性而不是其他任何事情

于 2010-03-02T18:09:18.187 回答
0

这完全是您的选择，您是否对解决方案感到满意或是否想进一步改进它。有许多项目欧拉问题，其中蛮力解决方案需要很长时间，并且您必须寻找一个聪明的算法。

问题 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))。对于少数人来说，任何一种解决方案都可以。

于 2010-03-04T10:12:24.987 回答
0

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

这个问题的答案很难回答，原因有很多：

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

我想底线是，如果您认为它是一个好的解决方案，并且您的客户/购买者/团队/等都同意，那么它在当时是一个很好的解决方案。您将来可能会改变主意，但现在它是一个很好的解决方案。

于 2010-03-02T18:04:19.023 回答
0

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

通过使用 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);
于 2010-03-02T18:07:21.620 回答
0

[耸肩]

解决方案应根据需求进行评估。如果所有要求都得到满足，那么其他一切都是混乱的。如果满足所有要求，并且您个人对解决方案不满意，那么可能需要重新评估要求。这就是你可以回答这个形而上学问题的程度，因为我们开始涉足项目管理和业务之类的事情：S

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

  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，但我相信你可以很好地翻译它。

希望这可以帮助， ：）

干杯

于 2010-03-02T18:52:27.430 回答