Zajęcia opisane niżej wymagają dodatkowo oprogramowania: Logo Komeniusz lub Logomocja, Eli. Na zajęciach zostanie wykorzystana także prezentacja multimedialna wykonana przez nauczyciela w programie PowerPoint Pt „Algorytm Euklidesa”.
ALGORYTM NWD / NAJWIĘKSZEGO WSPÓLNEGO DZIELNIKA /SPOSOBEM EUKLIDESA
Przygotowanie uczniów:
• uczen umie wyjasnic pojecia: algorytm, algorytmika;
• zna krótki rys historyczny budowania algorytmów na przestrzeni wieków;
• umie podac kilka przykladów prostych algorytmów (z zycia) w postaci opisu slownego /lista kroków/;
• umie wyróznic podstawowe etapy na drodze „ od problemu do wyniku”;
• systematycznie i dokladnie prowadzic dzialania w prezentowaniu algorytmów za pomoca schematów blokowych .
Przebieg zajec:
I. Czesc wstepna:
• Powitanie z uczniami.
• Sprawdzenie listy obecnosci.
• Nawiazanie do tematu zajec / uczniowie otrzymuja polecenie od nauczyciela, aby wyszukali w Internecie informacje na temat „Kim byl Euklides ?” i zrobili notatke z tych informacji w edytorze tekstu Word, a nastepnie ja zaprezentowali slownie (mozna tu zaproponowac uczniom strony, na których maja szukac informacji np.www.szkoly.edu.pl/gim.margonin/starozyt/euklid.htm, www.matematyka.prx.pl/strona/biografie/euklides.htm )/.
II. Czesc wlasciwa:
• Nauczyciel podaje pewna pare liczb;
• Uczniowie odpowiadaja na pytania: - jaki jest ich najwiekszy dzielnik? - jakie liczby otrzymalismy w wyniku rozkladu liczby na czynniki? - skad wiadomo, ze te liczby sa liczbami pierwszymi?
• Uczniowie wchodza na strone internetowa (www.szkoly.edu.pl/gim.margonin) i wyszukuja informacje na temat liczb pierwszych: - co to jest sito Eratostenesa? - jaka liczbe nazywamy liczba Mersenne'a ?; - ciekawostki na temat liczb pierwszych.
• Nauczyciel tlumaczy sposób wyznaczania NWD z zastosowaniem odejmowania:
| Algorytm Euklidesa znajdowania NWD - wersja z odejmowaniem |
| Jesli chcesz znalezc Najwiekszy Wspólny Dzielnik dwóch liczb, to od wiekszej z nich odejmuj mniejsza dotad, az obie liczby beda sobie równe. Wynik jest ich najwiekszym wspólnym podzielnikiem. |
Przyklad
Obliczmy tym sposobem NWD liczb 24 i 15.
| 24-15=9 |
Od wiekszej liczby odejmujemy mniejsza. Liczby 24 i 15 przechodza w 15 i 9. Poniewaz nie sa one równe, wykonujemy dalej odejmowanie |
| 15-9=6 |
Teraz otrzymujemy pare 9 i 6, która dalej nie sklada sie z liczb sobie równych, wiec kontynuujemy odejmowanie. |
| 9-6=3 |
Para 6 i 3 - odejmujemy dalej |
| 6-3=3 |
Para 3 i 3 - otrzymalismy równosc, wiec liczba 3 jest najwiekszym wspólnym podzielnikiem liczb 24 i 15. |
• Przypomnienie podstawowych wiadomosci o algorytmach:
Budowa algorytmu
- Algorytm musi byc przedstawiony w taki sposób aby mógl byc jednoznacznie odczytany i mozna go bylo odpowiednio zastosowac.
- Kazdy algorytm zawiera:
- opis danych
- opis wyników
- plan dzialania czyli przetworzenia danych.
- Plan dzialania - przedstawiany jest w postaci ciagu czynnosci, które to musza byc wykonane w okreslonej kolejnosci;
- Opis czynnosci wystepujacych w algorytmie nazywamy - instrukcjami procedury.
Cechy dobrego algorytmu
Algorytm musi byc:
- poprawny, tzn. dla kazdego poprawnego zestawu danych, po wykonaniu skonczonej liczby czynnosci, prowadzi do poprawnych wyników
- szczególowy, aby wykonawca algorytmu rozumial opisane czynnosci i potrafil je wykonac
- jednoznaczny, tzn. w kazdym przypadku jego zastosowania, dla tych samych danych uzyskamy ten sam wynik
- uniwersalny, aby sluzyl do rozwiazywania pewnej grupy zadan, a nie tylko jednego zadania: np. algorytm jest przepisem na rozwiazanie równania postaci ax+b=0 dla dowolnych wspólczynników a i b, a nie – jednego konkretnego równania, np. 2x+3=0.
• Nauczyciel dzieli grupe na zespoly 2 osobowe. Uczniowie zapisuja algorytm wyznaczania NWD w postaci listy kroków.
• Nauczyciel kontroluje prace uczniów w razie potrzeby ukierunkowuje dzialania uczniów.
Przykladowe rozwiazanie zadania:
wyznaczanie NWD:
- dane sa dwie liczby a i b,
- dopóki liczby a i b nie sa sobie równe, powtarzaj krok trzeci w przeciwnym wypadku przejdz do kroku czwartego,
- od wiekszej liczby odejmij mniejsza i te wieksza zastap otrzymana róznica,
- wyprowadz wynik NWD.
Uczniowie porównuja swoje prace.
• Uczniowie zamieniaja liste kroków na schemat blokowy /wczesniej przypominamy co to jest „schemat blokowy:” /
Pojecie schematu blokowego:
- Schemat blokowy - jest to graficzny zapis algorytmu rozwiazania zadania, problemu przedstawiajacy opis i kolejnosc wykonywania czynnosci realizujacych dany algorytm.
Opis symboli graficznych stosowanych w schematach blokowych:
| Skrzynki START i STOP wskazuja poczatek i koniec kazdego algorytmu. Ze skrzynki START wychodzi tylko jedna droga, do skrzynki STOP wchodzi co najmniej jedno polaczenie. |
| W skrzynce instrukcyjnej umieszcza sie polecenia do wykonania ( instrukcje ) - podstawienie, obliczenie, wprowadzenie wartosci. |
| W skrzynce warunkowej umieszcza sie warunek, który decyduje o wyborze dalszej drogi postepowania. Ze skrzynki wychodza dwa polaczenia: TAK ( wybierane, gdy warunek jest spelniony ), NIE ( gdy warunek nie jest spelniony ). |
| W skrzynce wejscia / wyjscia umieszcza sie wprowadzane dane lub wyprowadzane wyniki. Ze skrzynki wychodzi tylko jedno polaczenie. |
Pojecie – instrukcji algorytmicznej
INSTRUKCJA - nazywamy opis czynnosci wystepujacych w algorytmie ( przyklady z ksiazki - zadzwonienie na numer 999 i wezwanie lekarza do chorego ) - omówienie przykladów .
Rodzaje instrukcji algorytmicznych (prezentacja w PowerPoincie przygotowana przez nauczyciela np.: „Algorytm Euklidesa”)
a). Instrukcje sekwencyjne (liniowe) - kolejnosc instrukcji jedna po drugiej, a wiec instrukcja wykonana w kolejnosci wynikajacej z ich nastepstwa – sekwencji
b). Instrukcje interacyjne (zw. petlami) - sa to instrukcje wielokrotnego powtarzania. Nie zawsze liczbe powtórzen mozna okreslic dokladnie, czesto uzaleznione jest to od spelnienia pewnych warunków.
Schemat blokowy do algorytmu Euklidesa opracowany przez uczniów:
Na schemacie blokowym stosujemy nastepujace symbole:
a, b : liczby, dla których poszukujemy NWD
Po odczytaniu wartosci liczb a i b rozpoczynamy petle, która przerwie sie, gdy w wyniku dzialania algorytmu liczba a bedzie równa liczbie b. W takim przypadku dowolna z tych liczb jest NWD.
W przeciwnym wypadku jedna z liczb a lub b jest wieksza od drugiej. Odejmujemy wiec liczbe mniejsza od wiekszej i kontynuujemy petle, az do zrównania wartosci a i b.
• Badanie efektywnosci algorytmów wyznaczania NWD z zastosowaniem odejmowania – wnioski.
• Nauczyciel dzieli grupe na czteroosobowe zespoly.
• Zastosowania algorytmu Euklidesa.
Znana jest nastepujaca lamiglówka:
Dysponujesz:
dwoma czerpakami o pojemnosciach 4 i 6 litrów, pustym pojemnikiem o nieograniczonej pojemnosci i nieograniczona iloscia wody. Podaj sposób napelnienia pojemnika 15 litrami wody, przy czym wode z kranu mozesz wlewac do pojemnika lub wylewac z niego tylko pelnymi czerpakami.
• Uczniowie pracuja nad rozwiazaniem zadania.
• Prezentacja rozwiazan grup – porównanie z prawidlowym rozwiazaniem.
III. Czesc koncowa:
1. Ocena wkladu pracy.
2. Podsumowanie zajec.
Zdobyte umiejetnosci i kompetencje ucznia:
• Umiejetnosc wykorzystania komputera do wielokrotnego wykonywania ciagu instrukcji;
• Umiejetnosci przedstawiania algorytmów w postaci schematów blokowych i jednego z jezyków programowania;
• Umiejetnosc stosowania powtórzen z warunkiem;
• Umiejetnosc pracy w grupie, prezentowania swoich rozwiazan;
• Umiejetnosc abstrakcyjnego myslenia, myslenia logicznego i wyciagania wniosków;
• Umiejetnosc stosowania metody prób i bledów i kolejnych ulepszen.
Literatura:
1. Syslo M.M., Algorytmy, WSiP, Warszawa 1997;
2. Zdzislaw Nowakowski, Witold Sikorski „Informatyka bez tajemnic czesc III programowanie mikrokomputerów”, MIKOM, Warszawa 1997.
3. Strony internetowe:
www.szkoly.edu.pl/gim.margonin
www.szkoly.edu.pl/gim.margonin/starozyt/euklid.htm,
www.matematyka.prx.pl/strona/biografie/euklides.htm
Scenariusz opracował mgr Grzegorz Weber
|
