5

質問

プロジェクト オイラー問題 8 ( 1000 桁の数字の中で連続する 5 桁の最大の積を見つける) の解を、力ずくの方法よりもよく見つける方法はありますか。

私は考えられるすべての製品を計算し、最も優れたもの、つまりブルート フォース アルゴリズムを選択しました。

より効率的なアルゴリズムはありますか? または、力ずくの方法が唯一の方法ですか。

補足事項

  • これは宿題の質問ではありません。
  • 問題8の結果を求めているわけではありません。
4

4 に答える 4

7

サイズ 5 のスライディング ウィンドウを使用して、これを で解くことができますO(d)。ここで、d は入力数値の桁数です。

ウィンドウの開始番号のインデックスでウィンドウを表し、ウィンドウ i の値はインデックス [i, i+4] を持つ要素の積です。これで、反復ごとにウィンドウを右にスライドさせて、効果的に左端の要素を削除し、新しい要素を右に追加すると、ウィンドウの新しい値は になりますold_value / left_most_ele * new_right_ele。i範囲内のすべてのインデックスに対してこれを続け[0,d-5]、最大ウィンドウ値を見つけます。

内側のループが 5 回実行される入れ子になったループを持つ力ずくの方法もO(d)解決策であることに注意してください。しかし、各ステップで 5 回の乗算を行うのではなく、1 回の乗算と 1 回の除算を行うため、上記の方法の方がわずかに優れています。

于 2012-10-08T19:09:08.583 に答える
6

質問は連続した数字を要求するため、この場合、「ブルート フォース」はO(n)を意味し、 nは桁数 (1000) です。数字に何らかのパターンがない限り、数字をスキャンするだけでnステップが必要になるため、これが最速のソリューションです。

最後の 4 桁の積をキャッシュするか、同様のトリックを実行できますが、間違いなくO(n)よりも優れたものにはなりません。

于 2012-10-08T19:08:57.257 に答える
5

はいといいえ。連続する 5 桁の各シーケンスを確認する必要はありますが、ループのたびにこれらのシーケンスのすべてを乗算する必要はありません。処理を高速化するショートカットがあります。たとえば、次の桁が 0 の場合はスキップできます。また、次の数字がシーケンスから削除した最後の数字よりも小さい場合は、他の 4 つの共通数字を掛けた結果が小さくなることがわかっているため、掛け算をスキップして次の数字に進みます。このようなトリックは、1000 桁しかない場合は大きな違いはありませんが、入力が大きくなっただけで、後の問題は同じになります。

于 2012-10-08T19:10:50.843 に答える
2

最適化の 1 つは、最初の 5 桁の積を計算し、各反復で次の桁を掛け、前の桁で割ります (移動ウィンドウ)。

もう 1 つの最適化は、周囲のすべての数字をすぐに破棄すること0です。

于 2012-10-08T19:14:52.530 に答える