Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie
PrezentacjaForumPrezentacja nieoficjalnaZmiana prezentacji
Algorytm NWD największego wspólnego dzielnia sposobem Euklidesa

 

 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 Mersennea ?; - 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

 

Jeżeli zauważyłeś jakieś nadużycia w prezentacji napisz o tym poniżej i wyślij je do nas:
INFORMACJE O PREZENTACJI

Ostatnią zmianę prezentacji wykonał: Szkolnictwo.pl.
IP autora: 83.21.195.174
Data utworzenia: 2008-09-01 23:09:30
Edycja: Edytuj prezentację.

HISTORIA PREZENTACJI

Szkolnictwo.pl (83.21.195.174) - Prezentacja (2008-09-01 23:09:30) - Edytuj prezentację.





Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie