Czego się nauczysz
Algorytm Euklidesa znajduje największy wspólny dzielnik dwóch liczb, nie sprawdzając ani jednego kandydata: wystarcza mu kilka reszt z dzielenia. Z NWD policzysz od razu NWW, a z obu skrócisz i dodasz ułamki bez żadnych przybliżeń.
Po co ci to na maturze
NWD i NWW wracają w zadaniach o ułamkach, o liczbach względnie pierwszych i o tym, kiedy dwa autobusy znów odjadą razem. Algorytm Euklidesa zapisany pseudokodem bywa też w zadaniach na analizę algorytmu.
Etapy lekcji
Spis lekcji
Teoria
6 rozdziałówNie zaczęte- 1.1NWD i NWWNajwiększy wspólny dzielnik i najmniejsza wspólna wielokrotność na przykładach z życia.
- 1.2Algorytm EuklidesaOd prostokąta odcinasz kwadraty, aż nic nie zostanie, a bok ostatniego kwadratu to NWD.
- 1.3Euklides w PythoniePętla powtarza jedno cięcie, czyli zamianę pary (a, b) na (b, a % b), dopóki b nie jest zerem.
- 1.4NWW z NWDNWW dostajesz, mnożąc dwie liczby i dzieląc iloczyn przez ich NWD.
- 1.5Ułamki: skracanie i dodawanieUłamek to para liczb całkowitych. NWD go skraca, wspólny mianownik pozwala dodawać.
- 1.6PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.