3

特定の活動が発生する月のすべての日を見つける必要があります。アクティビティが発生する日は連続します。日のシーケンスは1か月から1か月全体の範囲であり、シーケンスは1か月に1回だけ発生します。

特定の日にアクティビティが発生するかどうかをテストすることは、費用のかかる計算ではありませんが、この問題を使用して新しいことを学ぶと思いました。テストする必要のある日数を最小化するアルゴリズムはどれですか？

4

3 に答える 3

5

シーケンスを繰り返して最初の一致を見つけてから、最初の不一致まで繰り返すよりも、はるかに優れた方法はありません。あなたはitertoolsそれを素晴らしくて読みやすくするために使うことができます：

itertools.takewhile(mytest, 
                    itertools.dropwhile(lambda x: not mytest(x), mysequence))
于 2012-11-14T18:39:01.020 に答える
2

最適な方法は、入力データ構造に少し依存します。入力データ構造がその月の各日のブール値のリストである場合は、次のコードを使用できます。

start = activity.find(True)
end = activity.rfind(True)
于 2012-11-14T19:40:50.810 に答える
2

@isbadawiによって提案された線形プローブは、サブシーケンスの開始を見つけるための最良の方法だと思います。これは、サブシーケンスが非常に短く、より大きなシーケンス内のどこかにある可能性があるためです。

ただし、サブシーケンスの開始が見つかったら、バイナリ検索を使用してサブシーケンスの終了を見つけることができます。これは、2番目の線形プローブを実行するよりも必要なテストが少ないため、より良いソリューションです。

他の人が指摘しているように、これを行う実際的な理由はあまりありません。これは2つの理由で当てはまります。大きなシーケンスは非常に短く（約31要素のみ）、とにかく少なくとも1つの線形プローブを実行する必要があるため、big-Oランタイムは大きなシーケンスの長さで線形のままです。アルゴリズムの一部を線形から対数に減らしたとしても、シーケンス。

于 2012-11-14T19:56:42.980 に答える