Na dzisiejszych zajęciach z informatyki w klasie VII zastanawialiśmy się nad pojęciami algorytmu. Mówiliśmy na temat schematów blokowych. Rozwiązywaliśmy problem matematyczny związany z znalezieniem największego wspólnego dzielnika (NWD) dla 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.
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.
Cały problem uczniowie mieli za zadanie rozwiązać w Scratchu. Scratch czyli program służący do kodowania.
Więcej na www.informatykatechnika.cba.pl
