Odpowiedzi

2010-03-10T19:40:54+01:00
Jest to jeden z najstarszych algorytmów. Jest pomysłowy i szybko daje wynik. Opiera się na fakcie, że jeśli od większej liczby odejmiemy mniejszą to ta liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Gdy przy kolejnym odejmowaniu otrzymamy parę takich samych liczb, to ta liczba jest najwiekszym wspólnym dzielnikiem liczb wyjściowych

Przykład.

liczba 1 liczba 2 NWD
42 24 ?
42 - 24 = 18 24 ?
18 24- 18 = 6 ?
18 - 6 = 12 6 ?
12 - 6 = 6 6 6

Niestety nie można wstawiać wielu spacji między kolumnami tabelki. więc ustwię je poziomo poniżej. Posklejane jedna obok drugiej dadza nam to co chcialem osiągnąć ;]

liczba 1
42
42 - 24 = 18
18
18 - 6 = 12
12 - 6 = 6

liczba 2
24
24
24- 18 = 6
6
6

NWD
?
?
?
?
6