Minimum i maksimum przez podział

Minimum i maksimum metodą dziel i zwyciężaj - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Dziel i zwyciężaj dla minimum i maksimum: podziel ciąg na dwie połowy, znajdź minimum i maksimum każdej rekurencyjnie, a potem **połącz**: mniejsze z dwóch minimów i większe z dwóch maksimów (2 porównania). Przypadki bazowe: jeden element (0 porównań) i dwa elementy (1 porównanie). Dla `n` będącego potęgą dwójki wychodzi `3n/2 - 2` porównań, tyle co w metodzie par.

def min_max_dc(values, left, right):
    if left == right:
        return values[left], values[left]
    if right == left + 1:
        if values[left] < values[right]:
            return values[left], values[right]
        return values[right], values[left]
    middle = (left + right) // 2
    min1, max1 = min_max_dc(values, left, middle)
    min2, max2 = min_max_dc(values, middle + 1, right)
    return (min1 if min1 < min2 else min2), (max1 if max1 > max2 else max2)

data = [7, 3, 9, 1, 8, 4, 6, 2]
print(min_max_dc(data, 0, len(data) - 1))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 2, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.