Przykład 1.

Wyznacz największy wspólny dzielnik liczb 282 i 78.

Rozwiązanie:

Zaczynamy od podzielenia liczby 282 przez liczbę 78 z resztą:

282 : 78 = 3, reszty 48

Otrzymaliśmy resztę różną od zera, zatem teraz podzielimy liczbę 78 przez resztę 48. Ten schemat będziemy powtarzać do momentu otrzymania reszty równej 0.

78 : 48 = 1, reszty 30 48 : 30 = 1, reszty 18 30 : 18 = 1, reszty 12 18 : 12 = 1, reszty 6 12 : 6 = 2, reszty 0

Otrzymaliśmy resztę równą zero, zatem szukany NWD będzie równy ostatniej niezerowej reszcie:

NWD (282, 78) = 6

Istnieje wiele teoretycznych i praktycznych zastosowań algorytmu. Może on zostać wykorzystany do generowania rytmów muzycznych, stosowanych jako ostatnio w muzyce. Jest wykorzystywany w algorytmie RSA. Algorytm Euklidesa używany jest też do rozwiązywania równań diofantycznych, na przykład do znajdowania liczb spełniających zadany układ kongruencji (chińskie twierdzenei o resztach) czy znajdowania liczb odwrotnych w ciele skończonym. Może być także stosowany do generowania ułamków łańcuchowych w metodzie Sturma do obliczania pierwiastków rzeczywistych wielomianu. Wykorzystywany jest również w kilku współczesnych algorytmach do faktoryzacji liczb całkowitych.

schemat

Algorytm Euklidesa

Algorytm Euklidesa jest szybkim sposobem obliczania największego wspólnego dzielnika dwóch (zwłaszcza dużych) liczb całkowitych.

AlgorytmAby obliczyć NWD(a,b), wykonujemy kolejno następujące kroki: Dzielimy z resztą liczbę a przez liczbę b jeżeli reszta =0, to NWD(a,b)=b jeżeli reszta ?0, to przypisujemy liczbie a wartość liczby b, liczbie b wartość otrzymanej reszty, a następnie wykonujemy ponownie punkt 1.

Algorytm Euklidesa

Kategorie postów

Strony

Kategoria

Informatyka

Przykład 1

Zastosowanie

Wszystko o algorytmie Euklidesa

Algorytm Euklidesa