質問プロジェクトオイラー＃8：ブルートフォース計算よりも効率的なアルゴリズムはありますか？
強引な方法よりもFind the greatest product of five consecutive digits in the 1000-digit numberあるプロジェクトオイラーの問題8、の解決策を見つけるための良い方法はあります。
私はすべての可能な製品を計算し、最大のものを選択しました。
より効率的なアルゴリズムはありますか？あるいは、ブルートフォース方法が唯一の方法です。
サイドこれは宿題の問題ではありません
に結果を求めていないです桁数（1000）。番号に何らかのパターンがない限り、nの番号をスキャンするだけのステップが必要なので、これが最速の解決方法です。
最後の4桁の値をキャッシュすることも、同様のトリックを行うこともできますが、確かにO（n）より良くなりません。
サイズ5のスライディングウィンドウを使用して、O(d)でこれを解決できます.dは入力番号の桁数です。
ウィンドウの開始番号のインデックスでウィンドウを表し、ウィンドウiの値はindex [i、i + 4]の要素の積です。今度はすべての反復でウィンドウを右にスライドさせ、効果的に一番左の要素を削除し、新しい要素を右に追加すると、ウィンドウの新しい値はold_value/left_most_ele * new_right_eleになります。すべてのインデックスi（範囲[0,d-5]）でこれを行い、最大ウィンドウ値を見つけます。
内部ループが5回実行されるネストループを持つブルートフォース方法もまた、O(d)ソリューションであることに注意してください。しかし、上記の方法は、各ステップで5回の乗算を行うのではなく、1回の乗算と1回の除算を行うので、わずかに優れています。
はい、いいえ。連続した5桁の各シーケンスを調べなければなりませんが、ループのたびにそのシーケンスのすべてを掛ける必要はありません。あなたが取ることができる処理をスピードアップするショートカットがあります。たとえば、次の数字が0の場合は、先に進むことができます。また、次の桁がシーケンスからドロップした最後の桁よりも小さい場合は、他の4つの共通桁の乗算結果が小さくなるので、乗算をスキップして次の桁に進みます。このようなトリックでは、1000桁しかないときに大きな違いはありませんが、後で問題は同じになります。
1つの最適化は、最初の5桁の積と各反復で次の桁を乗算し、前の（移動ウィンドウ）で除算することです。
もう1つの最適化は、0の周りのすべての数字を直ちに破棄することです。
+1すばらしいすべてのお返事をいただきありがとうございます。 – Lernkurve