Pierwiastek połowieniem

Pierwiastek przez połowienie i porównanie metod - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Pierwiastek z `x >= 0` leży w przedziale `[0, max(1, x)]` (dla `x < 1` pierwiastek jest większy od `x`, dlatego prawy koniec to co najmniej 1). Połowimy przedział, porównując kwadrat środka z `x`. Każdy krok daje mniej więcej jeden bit dokładności.

def bisect_sqrt(x, eps):
    a, b = 0.0, max(1.0, x)
    steps = 0
    while b - a > eps:
        middle = (a + b) / 2
        if middle * middle < x:
            a = middle
        else:
            b = middle
        steps += 1
    return (a + b) / 2, steps

for x in [2, 10, 0.25, 1000000]:
    print(x, bisect_sqrt(x, 1e-9))

Ł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.