Algorytm Euklidesa opiera się na fakcie, że jeśli od większej liczby odejmiemy mniejszą, to ta mniejsza i różnica liczb daje nam taki sam największy wspólny dzielnik jak pierwotne liczby. Gdy przy następnym odejmowaniu otrzymamy parę takich samych liczb, to znaleźliśmy NWD.
(przykład) liczby 12 i 8
| większa liczba | mniejsza liczba |
| 12 | 8 |
| 8 | 12-8=4 |
| 4 | 8-4=4 |
Jak by to wyglądało w scratchu? Zobacz przykładowy skrypt.
Brak komentarzy:
Prześlij komentarz
Uwaga: tylko uczestnik tego bloga może przesyłać komentarze.