Python-data-structure-python-divide-and-conquer
Python-分割して征服する
分割統治アプローチでは、手元の問題は小さな副問題に分割され、各問題は個別に解決されます。 サブ問題をさらに小さなサブ問題に分割し続けると、最終的には、それ以上分割できない段階に達する可能性があります。 それらの「アトミックな」最小のサブ問題（分数）は解決されます。 元の問題の解決策を得るために、すべての副問題の解決策が最終的にマージされます。
概して、3段階のプロセスで「分割統治」アプローチを理解できます。
分割/分割
このステップでは、問題をより小さなサブ問題に分割します。 サブ問題は、元の問題の一部を表す必要があります。 このステップでは、一般に再帰的なアプローチを使用して、問題をさらに分割できるサブ問題がなくなるまで問題を分割します。 この段階では、サブ問題は本質的にアトミックになりますが、実際の問題の一部を表します。
征服/解決
このステップには、解決すべき小さな副次的な問題がたくさんあります。 一般に、このレベルでは、問題はそれ自体で「解決」されたと見なされます。
結合/結合
小さなサブ問題が解決されると、この段階では元の問題の解決策が定式化されるまで再帰的に結合されます。 このアルゴリズムのアプローチは再帰的に機能し、征服とマージのステップは非常に近いため、1つのように見えます。
例
次のプログラムは、Pythonを使用してバイナリ検索を実装する divide-and-conquer プログラミングアプローチの例です。
バイナリ検索の実装
バイナリ検索では、要素の並べ替えられたリストを取得し、リストの中央で要素の検索を開始します。 検索値がリストの中央の値と一致する場合、検索を完了します。 それ以外の場合は、検索される項目の値に応じてリストの右半分と左半分のどちらで処理するかを選択することにより、要素のリストの半分を削除します。 これはリストが並べ替えられ、線形検索よりもはるかに高速であるため可能です。 ここで、与えられたリストを分割し、リストの適切な半分を選択して征服します。 このapprocahを繰り返して、要素が見つかるか、リストに要素がないことを確認します。
def bsearch(list, val):
list_size = len(list) - 1
idx0 = 0
idxn = list_size
# Find the middle most value
while idx0 <= idxn:
midval = (idx0 + idxn)//2
if list[midval] == val:
return midval
# Compare the value the middle most value
if val > list[midval]:
idx0 = midval + 1
else:
idxn = midval - 1
if idx0 > idxn:
return None
# Initialize the sorted list
list = [2,7,19,34,53,72]
# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))上記のコードが実行されると、次の結果が生成されます。
5
None
