分割統治アルゴリズムの基本的なアイデアは、以下のステップになります:
- 分割(Divide): 大きな問題を複数の小さな部分問題に分割します。
- 統合(Combine): 各部分問題の解を組み合わせて、元の問題の解を得ます。
以下に、分割統治アルゴリズムを使用して原因分析を行う方法と、それに関連するコード例をいくつか示します。
- 二分探索: ソートされたリスト内での要素の検索を効率的に行います。リストを二つに分割し、中央の要素と目的の要素を比較して、検索範囲を半分に絞り込んでいきます。
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1- マージソート: リストを分割してソートし、ソートされた部分リストを統合して全体をソートします。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged- フィボナッチ数列: フィボナッチ数列のn番目の数を再帰的に計算します。
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)