Algorytmy i schematy
Na dzisiejszych zajęciach dowiemy się:
- co oznacza pojęcie algorytmu;
- co oznacza pojęcie schemat blokowy;
- jakie są sposoby wyznaczenia największego wspólnego dzielnika (NWD) dwóch liczb całkowitych.
Algorytm to sposób rozwiązania problemu krok po kroku. Opis powinien być dokładny i nie powinien pozostawiać cienia wątpliwości w jakiej kolejności należy wykonać kolejne działania. Z algorytmami mamy najczęściej do czynienia na zajęciach z matematyki.
JEDNYM Z PRZYKŁADÓW ALGORYTMU jest sposób wyznaczenia największego wspólnego dzielnika dwóch liczb całkowitych. NWD jest wykorzystywany m.in. do skracania ułamków.
Przykład:
NWD dla liczb A i B wynosi 2x3x1=6
Lepszym i szybszym rozwiązaniem problemu szukania największego wspólnego dzielnika dwóch liczb całkowitych jest algorytm Euklidesa. Algorytm ten został opisany w 300 r. p.n.e. Opiera się na spostrzeżeniu, że różnica dwóch liczb ma taki sam największy podzielnik jak dwie pierwotne liczby (42, 24).
Algorytm Euklidesa kolejne etapy działania
- wybieramy dwie liczby naturalne.
- Jeśli liczby są równe, to NWD jest np. pierwszą z nich i to oznacza koniec działań.
- Jeśli liczby nie są sobie równe, to trzeba:
- zbadać, która jest większa;
- odjąć od niej mniejszą i zastąpić większą przez otrzymaną różnicę;
- wrócić do sprawdzenia warunku w punkcie 2.
Zadanie:
Wykonaj ten algorytm dla następujących par liczb: 152 i 57, 1025 i 725, 132 i 44.
Zbuduj w scratchu program z wykorzystaniem algorytmu Euklidesa – pomocna będzie pętla powtarzaj aż.
Utwórz w Scratchu projekt Euklides 2 i zbuduj w nim skrypt obliczeniowy NWD według skryptu Euklidesa. Można w pisaniu skryptu wykorzystać blok mod zwracający resztę z dzielenia oraz operator logiczny i. Operator ten znajdziesz w grupie Wyrażenia.
