初心者向けのPythonのプログラミング問題です。入門編としてチャレンジしてください。Pythonの正答例は以下になります。
問題727
def quick_sort(lst):
if len(lst) ≤ 1:
return lst
pivot = lst[0]
left = [x for x in lst[1:] if x ≤ pivot]
right = [x for x in lst[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
＃ 呼び出し例
lst = [8, 3, 5, 2, 9]
print(quick_sort(lst)) ＃ 出力: [2, 3, 5, 8, 9]
問題728
def merge_sort(lst):
if len(lst) ≤ 1:
return lst
mid = len(lst)//2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
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
＃ 呼び出し例
lst = [9, 2, 6, 1, 5]
print(merge_sort(lst)) ＃ 出力: [1, 2, 5, 6, 9]
問題729
def binary_search_recursive(lst, target, low=0, high=None):
if high is None:
high = len(lst) – 1
if low > high:
return -1
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] > target:
return binary_search_recursive(lst, target, low, mid – 1)
else:
return binary_search_recursive(lst, target, mid + 1, high)
＃ 呼び出し例
lst = [1, 3, 5, 7, 9]
print(binary_search_recursive(lst, 7)) ＃ 出力: 3
コメント