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

Od 01.01.2015 odwiedzono tę wizytówkę 2792 razy.
Chcesz zwiększyć zainteresowanie Twoją jednostką?
Zadzwoń do Nas!* - tel. 606-...-... ->>>
* szkolnictwo.pl - najpopularniejszy informator edukacyjny - 1,5 mln użytkowników miesięcznie



Platforma Edukacyjna - gotowe opracowania lekcji oraz testów.



 

 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

 

Umieść poniższy link na swojej stronie aby wzmocnić promocję tej jednostki oraz jej pozycjonowanie w wyszukiwarkach internetowych:

X


Zarejestruj się lub zaloguj,
aby mieć pełny dostęp
do serwisu edukacyjnego.




www.szkolnictwo.pl

e-mail: zmiany@szkolnictwo.pl
- największy w Polsce katalog szkół
- ponad 1 mln użytkowników miesięcznie




Nauczycielu! Bezpłatne, interaktywne lekcje i testy oraz prezentacje w PowerPoint`cie --> www.szkolnictwo.pl (w zakładce "Nauka").

Zaloguj się aby mieć dostęp do platformy edukacyjnej




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