WI-damian-kaminski/Jupyter/ZadanieJupiter1.ipynb

Algorytm Euklidesa

Algorytm Euklidesa służy do obliczania NWD (największego wspólnego dzielnika) dwóch liczb całkowitych. Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy”, około trzysetnego roku przed naszą erą, co sprawia, że jest jednym z najstarszych, wciąż używanych algorytmów numerycznych.

Algorytm

Aby obliczyć NWD(a,b), wykonujemy kolejno następujące kroki:

• Dzielimy z resztą liczbę a przez liczbę b

  • jeżeli reszta jest równa 0, to NWD(a,b)=b

  • jeżeli reszta jest różna od 0, to przypisujemy liczbie a wartość liczby b, liczbie b wartość otrzymanej reszty, a następnie wykonujemy ponownie punkt 1.

    Przykład

Wyznacz największy wspólny dzielnik liczb

Program ilustrujący działanie algorytmu Eukldesa.

def NWD(a, b):
    while a != b:
        a, b = max(a, b), min(a, b)
        print("a = {a}; b = {b}".format(a = a, b = b))
        a = a - b
    print("a = {a}; b = {b}".format(a = a, b = b))
    return a

def main(args):
    a = int(input("Podaj pierwszą liczbę całkowitą dodatnią: "))
    b = int(input("Podaj drugą liczbę całkowitą dodatnią: "))
    print("nNajwiększy wspólny dzielnik liczb {a} i {b} jest równy: {NWD}".format(a = a, b = b, NWD = NWD(a, b)))
    50
    
    
    return 0

if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))

Podaj pierwszą liczbę całkowitą dodatnią: 55
Podaj drugą liczbę całkowitą dodatnią: 20
a = 55; b = 20
a = 35; b = 20
a = 20; b = 15
a = 15; b = 5
a = 10; b = 5
a = 5; b = 5
nNajwiększy wspólny dzielnik liczb 55 i 20 jest równy: 5

An exception has occurred, use %tb to see the full traceback.

SystemExit: 0

Strony z których kożystałem

Obliczeniowo

Matemaks.

Wikipedia.