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;
?>

これは宿題ではないことに注意してください。私は数百年前に学校を辞めました。私は退屈していると感じており、プロジェクトオイラーの質問を通過しています

4

8 に答える 8

7

私は、長い間取り組んできたプログラミングの課題を解決した後、「これで十分だ」といつも考えます。

私の意見では、これは本当に正しい考え方ではないと思います。また、常に最高のパフォーマンスでコーディングするように努めるべきだと思います。

Code Completeで提示された古典的なものの 1 つは、プログラマーは、目標が与えられた場合、多くのメトリックの 1 つを使用して「最適な」コンピューター プログラムを作成できますが、すべてのパラメーターを一度に最適化することは不可能であるということです。などのパラメータ

  • コードの可読性
  • コード出力のわかりやすさ
  • コードの長さ (行)
  • コード実行速度 (パフォーマンス)
  • コードを書く速度

これらのパラメーターのいずれか 1 つを自由に最適化してください。ただし、同時にすべてのパラメーターを最適化すると、フラストレーションを感じたり、過度に設計されたシステムになる可能性があることに注意してください。

あなたは自問すべきです：あなたの目標は何ですか？この状況で「十分」とは何ですか？学習していて、物事をより最適化したい場合は、ぜひ実行してください。完璧なプログラムを構築するには無限の時間がかかり、時間自体が価値があることに注意してください。

于 2010-03-02T18:01:32.803 に答える
2

操作を 3 回実行することで mod 2 セクションを回避できます (3 番目の要素はすべて偶数)。次のようになります。フィボナッチへの新しい入力は ($fibonnacci,2*$number+$previous) です。私は PHP に詳しくないので、これは一般的なアルゴリズムのアドバイスにすぎません。正しい構文かどうかはわかりません。これは実質的に同じ操作であり、剰余と加算をいくつかの乗算に置き換えているだけです。

また、順序で $number を偶数として、$previous を奇数として開始するようにしてください ($number を 2 として、$previous を 1 として開始し、合計も 2 から開始することができます)。 .

于 2010-03-02T18:15:59.763 に答える
1

フィボナッチ (問題 2) のことは忘れてください。オイラーを進めるだけです。すべての質問に最適なコードを見つけるのに時間を無駄にしないでください。

答えが1 分間のルールを満たしている場合は、次のルールを試すことができます。いくつかの問題の後、物事は難しくなり、その目標を達成するために書いている間にコードを最適化することになります

于 2010-03-14T14:01:28.417 に答える
0

ここにいる他の人も、「これは、例の質問と実際のビジネスの問題の問題の一部です」と述べています。

その質問への答えは、いくつかの理由で答えるのが非常に困難です。

  • 言語は大きな役割を果たします。一部の言語は一部の問題にはるかに適しているため、不一致に直面した場合、解決策が「雄弁ではない」ことに気付くでしょう。
  • 問題を解決するのにどれくらいの時間が必要かにもよりますが、問題を解決するのに時間がかかるほど、好きな解決策にたどり着く可能性が高くなります (逆の場合もあり、時間がかかりすぎると考えすぎてしまいます)。
  • 全体的な満足度によって異なります。私はいくつかのプロジェクトに取り組んできましたが、素晴らしいと思った部分と美しくコーディングされた部分、そして他の部分は完全にゴミでしたが、それらは私が対処する時間の範囲外でした.

肝心なのは、あなたがそれを良い解決策だと考え、顧客/購入者/チーム/その他が同意すれば、当面は良い解決策になるということだと思います. 将来気が変わるかもしれませんが、今のところは良い解決策です。

于 2010-03-02T18:04:19.023 に答える
0

私は実際にこれをテストしませんでした...しかし、「完了」と呼ぶ前に、このソリューションで個人的に解決しようとしたことがありました。

合計引数を使用して再帰を実装することにより、可能な限りグローバルを回避する

編集: 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

解決策に満足しているか、さらに改善したいかは、完全にあなたの選択です。力ずくで解決するには時間がかかりすぎて、巧妙なアルゴリズムを探さなければならないプロジェクト オイラー問題が数多くあります。

問題 2 は最適化を必要としません。あなたのソリューションはすでに十分に高速です。それでも、どのような最適化が可能かを説明させてください。多くの場合、主題に関する調査を行うことが役立ちます。たとえば、フィボナッチ数に関する wiki ページには、この式が含まれています。

fib(n) = (ファイ^n - (1-ファイ)^n)/sqrt(5)

ここで、ファイは黄金比です。いえ

ファイ = (sqrt(5)+1)/2。

fib(n) がおよそ phi^n/sqrt(5) であることを使用すると、M より小さい最大のフィボナッチ数のインデックスを次のように見つけることができます。

n = フロア (ログ (M * sqrt(5)) / ログ (ファイ))。

たとえば、M=4000000 の場合、n=33 を得るため、fib(33) は 4000000 より小さい最大のフィボナッチ数です。n が 3 の倍数の場合、fib(n) は偶数であることがわかります。したがって、偶数の合計はフィボナッチ数は

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

閉じた形式を見つけるために、ウィキペディアのページから上記の式を使用し、合計が基本的に 2 つの等比級数であることに注意してください。数学は完全に自明ではありませんが、これらのアイデアを使用すると、

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

問題を解決するコードの実行に約 1 分以上かかるべきではないというガイドラインを使用してください。それがオイラー問題にとって最も重要なことです、IMO。

それ以上に、読みやすいことを確認してください。コードがどのように機能するかを簡単に確認できることを確認してください。こうすることで、以前に解いたオイラー問題のような問題が発生した場合に、物事がどのように機能したかをより簡単に確認できます。これにより、その問題をより迅速に解決できるようになります。

自分で他の基準を設定することもできますが、それはオイラー問題の意図を超えていると思います。私にとって、問題のコンテキストは、何よりも効率と読みやすさに焦点を当てるのにはるかに適しているようです。

于 2010-03-02T18:09:18.187 に答える
0

[肩をすくめる]

ソリューションは、要件によって評価する必要があります。すべての要件が満たされている場合、他のすべてはモクシーです。すべての要件が満たされ、ソリューションに個人的に不満がある場合は、おそらく要件を再評価する必要があります。この形而上学的な質問を理解できるのは、これくらいです。プロジェクト管理やビジネスなどに取り掛かるからです :S

エヘム、あなたの Euler-Project の質問に関して、私の 2 ペンスだけ:

  1. 再帰ではなく、反復へのリファクタリングを検討してください
  2. シリーズの第 3 項ごとに偶数であることに注意してください。開始期間が与えられたら、モジュロする必要はありません

例えば

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;
}

したがって、おそらくコード行は増えますが、[実質的に] 高速であることが保証されています。反復アプローチは「エレガント」ではありませんが、再帰的なメソッド呼び出しを節約し、スタック スペースを節約します。第 2 に、項の生成を展開する (つまり、ループを明示的に展開する) ことで、モジュラス演算を実行して「偶数」条件をテストする必要があった回数を減らすことができます。拡張すると、終了条件 [現在の期間が制限未満の場合] が評価される回数も減ります。

それは「より良い」ですか、いいえ、それは単なる「別の」ソリューションです。

PHPに慣れていないC＃で申し訳ありませんが、かなりうまく翻訳できると確信しています。

お役に立てれば、 ：）

乾杯

于 2010-03-02T18:52:27.430 に答える