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

  1. wybieramy dwie liczby naturalne.
  2. Jeśli liczby są równe, to NWD jest np. pierwszą z nich i to oznacza koniec działań.
  3. 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.

 

 

 

About Post Author

Skip to content