Euklides na rysunku

Algorytm Euklidesa iteracyjnie: odejmowanie i reszta z dzielenia - Informatyka - liceum klasa 1, zakres rozszerzony (Python)

Algorytm Euklidesa ma piękną interpretację geometryczną. Prostokąt o bokach `a` i `b` tniemy na **kwadraty**: od dłuższego boku odcinamy kwadrat o boku równym krótszemu. To dokładnie jedno odejmowanie! Zostaje mniejszy prostokąt i powtarzamy to samo. Gdy reszta prostokąta jest kwadratem, jego bok to NWD(a, b): kwadratami o tym boku da się wypełnić cały prostokąt bez przerw. Strzałka rysuje prostokąt 150 × 60, a potem kolejne kwadraty. Ostatni (czerwony) ma bok 30, czyli NWD(150, 60) = 30. Kliknij **Krok** i obserwuj, jak maleją `width` i `height`.

arrow = Sprite()
arrow.image = 16
arrow.size = 10
world.add(arrow)
def jump(x, y):
    arrow.pen.on = False
    arrow.position = (x, y)
    arrow.angle = 0
    arrow.pen.on = True

def rectangle(x, y, width, height):
    jump(x, y)
    for _ in range(2):
        arrow.move(height)
        arrow.turn(90)
        arrow.move(width)
        arrow.turn(90)

def square(x, y, side):
    rectangle(x, y, side, side)

width, height = 150, 60
x, y = -80, -40
rectangle(x, y, width, height)
while width != height:
    if width > height:
        square(x, y, height)
        x += height
        width -= height
    else:
        square(x, y, width)
        y += width
        height -= width
arrow.pen.color = (220, 38, 38)
square(x, y, width)
print("NWD =", width)

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

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