Algorytmy i schematy blokowe

Szczegóły

Odsłony: 251

Rozwiązując jakikolwiek problem (zadanie) stosujemy zazwyczaj określoną metodę (przepis), która ma pozwolić na uzyskanie wyniku (rozwiązania). Warunkiem przystąpienia do rozwiązywania jakiegokolwiek problemu jest posiadanie niezbędnych wiadomości i doświadczenia.

Algorytmem nazywamy skończony ciąg instrukcji prowadzących do rozwiązania danego problemu lub zadania. Jest to przepis postępowania prowadzący do osiągnięcia jakiegoś celu.

Implementacja to zapis algorytmu w języku programowania.Nazwa algorytm wywodzi się od nazwiska perskiego matematyka Muhamed ibn Musy al-Chorezmi (z Chorezmu), który ok. 820 r n.e. opisał pozycyjny system kodowania dziesiętnego liczb i sztukę liczenia w tym systemie. W XII w. Europie przetłumaczono jego książkę i rozpoczęto wykonywanie obliczeń metodą "pisemną".

Algorytmika, podstawowy dział informatyki poświęcony poszukiwaniom, konstruowaniu i badaniom algorytmów, zwłaszcza w kontekście ich przydatności do rozwiązywania problemów za pomocą komputerów. Autorem nazwy dziedziny jest D. Haral (Spirit of Computing).

Cechy algorytmu:

1. Skończoność - realizowany ciąg instrukcji powinien mieć swój koniec;
2. Określoność - operacje i ich porządek muszą być ściśle określone;
3. Ogólność - stosowanie danego algorytmu nie powinno się ograniczać do pojedynczego problemu, ale do całej klasy problemów tego samego typu;
4. Efektywność - algorytm prowadzić do rozwiązania najkrótszą drogą;

Algorytmy zapisujemy w różny sposób:

- w języku naturalnym;
- w pewnej konwencji notacyjnej;
- za pomocą schematów blokowych;- w języku formalnym;
- w języku programowania;

TWORZENIE ALGORYTMÓW ZA POMOCĄ SCHEMATÓW BLOKOWYCH 

1. Pogram do tworzenia schematów blokowych online - Program online do tworzenia algorytmów blokowych - Draw.io 

2. SCHEMAT BLOKOWY

Przed napisaniem jakiegokolwiek programu, powinniśmy najpierw przygotować schemat jego działania czyli algorytm. Jednym ze sposobów przedstawiania algorytmów są schematy blokowe.

Schemat blokowy jest to układ figur geometrycznych (nazywanych skrzynkami lub blokami) połączonych ze sobą odcinkami prostymi lub łamanymi (ścieżki sterujące). Bloki służą do przedstawiania rodzaju działań zaprojektowanych w algorytmie, natomiast strzałki wskazują kolejność wykonywania tych działań.

Każda figura w schemacie blokowym prezentuje określony rodzaj operacji. Zasadnicza zaleta schematów blokowych jest to, ze graficznie prezentują one algorytm zarówno od strony występujących w nim działań, jak i ich kolejności.

3. ZASADY BUDOWANIA SCHEMATÓW BLOKOWYCH

• każda operacja, relacja lub informacja jest umieszczana w skrzynce
• kolejność wykonywania operacji wyznaczają połączenia między skrzynkami
• każde połączenie jest zaczepione początkiem do skrzynki, a końcem do innej skrzynki lub innego połączenia, żadne połączenie nie rozdziela się
• rozgałęzienie sieci działań możliwe jest tylko dzięki skrzynkom warunkowym
• schemat posiada jedną skrzynkę START i co najmniej jedną skrzynkę STOP
• ze skrzynki START można przejść do skrzynki STOP poruszając się po sieci działań
• ze skrzynki START można dotrzeć wzdłuż połączeń do dowolnej innej skrzynki schematu
• z każdej skrzynki istnieje przejście wzdłuż połączeń do jednej ze skrzynek STOP

Skrzynki przybierają kształty: prostokąta, rombu (lub sześcianu), równoległoboku, okręgu lub owalu

a) Skrzynka operacyjna - ma kształt prostokąta,

wewnątrz umieszcza się opis czynności. Ze skrzynki operacyjnej odchodzi tylko jedno połączenie. W systemie schematów blokowych w skrzynce operacyjnej można umieszczać opisy czynności, instrukcje przypisania, definicje. W przypadku występowania kilku opisów należy je oddzielać przecinkami .

b) Skrzynka warunkowa - ma kształt sześcianu lub rombu.

Wewnątrz umieszczony jest warunek, który decyduje o dalszej kolejności wykonywania działań. Zazwyczaj dąży się do tego aby skrzynka warunkowa miała dokładnie dwa wyjścia. Każdym z dwóch wyjść należy opisać słownie T, Tak, True, Yes, Prawda lub N, Nie, No, Fałsz, False.

c) Skrzynka wejścia/wyjścia - jest równoległobokiem,

wewnątrz którego umieszczone jest okreśłenie rodzaju wykonywanej operacji . W przypadku w(y)prowadzania wartości zmiennych należy ująć w nawiasy okrągłe ich nazwy a w przypadku w(y)prowadzania tekstu umieszcza się go w cudzysłowy. Dla odróżnienia skrzynki wejścia od wyjścia umieszcza się znak "?" dla pierwszej z nich.

d) Skrzynki graniczne START STOP - mają kształt owalu.

Oznaczają one początek i koniec schematu. Skrzynka START ma tylko jedno połączenie wychodzące a skrzynka STOP tylko jedno połączenie dochodzące. Wewnątrz skrzynki umieszcza się napis START,BEGIN, POCZĄTEK, KONIEC,STOP,END. Schemat może mieć tylko jedną skrzynkę START oraz co najmniej jedną skrzynkę STOP. Ponadto ze skrzynki START można dotrzeć wzdłuż połączeń do dowolnej skrzynki schematu oraz z każdej skrzynki schematu istnieje droga do skrzyni STOP.

e) Skrzynka łącznikowa - ma kształt okręgu

i może być używana do oznaczenia miejsc w schemacie, które mają być traktowane jako jedne i te same. Wewnątrz umieszcza się numer od 1 do 9999. Każda ze skrzynek łącznikowych ma tylko jedno połączenie. Skrzynka o tym samym numerze musi występować co najmniej dwukrotnie, przy czym skrzynka łącznikowa o ustalonym numerze z połączeniem wychodzącym może występować co najwyżej raz.

f) Skrzynka komentarza - ma kształt prostokąta bez krótszego, prawego boku. Wewnątrz umieszcza się pomocnicze informacje objaśniające połączenia lub wykonywane operacje . Skrzynka informacyjna połączona jest ze schematem za pomocą poziomej linii przerywanej.

4. SCHEMAT BLOKOWY LINIOWY

Schemat blokowy liniowy występuje w zadaniach, w których każda z operacji elementarnych nie zawiera relacji (warunku) i powtórzeń (iteracji).

Realizacja poszczególnych sąsiednich operacji następuje według ustalonej kolejności od operacji początkowej do końcowej.

Przykłady: liczenie pola powierzchni, obwodu figur płaskich.

5. SCHEMAT BLOKOWY Z ROZGAŁĘZIENIAMI.

Schematy blokowe z rozgałęzieniami spotyka się w zadaniach dla których kolejność poszczególnych etapów w rozwiązaniu może się zmieniać w zależności od warunków określonych w sformułowaniu problemu. Cechą tych algorytmów jest to, iż w trakcie realizacji przechodzi się tylko po jednej z możliwych dróg, przy czym każdy oddzielny etap realizacji algorytmu wykonywany jest dokładnie jeden raz. W rozwiązaniach wykorzystywane są drzewa logiczne.
Przykłady: znajdowanie liczby najmniejszej, rozwiązanie równania liniowego i kwadratowego.

6. Schemat blokowy cykliczny - z pętlą

Algorytmy dla problemów wymagających powtarzania poszczególnych etapów procesu obliczeniowego nazywamy cyklicznymi (czyli z pętlą).

Przez pętlę w schemacie blokowym rozumiemy tą część schematu, która opisuje drogę (obwód) zamkniętą zgodnie z kierunkiem połączenia (obiegu).

Pętla stanowi graficzny opis powtarzania czynności. Ciąg wszystkich czynności wykonywanych przy jednokrotnym przebiegu pętli nazywamy cyklem pętli.

TREŚĆ ZADANIA :

Użytkownik wprowadza dwie liczby, algorytm wykonuje dodawanie lub odejmowanie w zależności czy użytkownik naciśnie D - dodawanie, o - odejmowanie. 

Co "co robi" ten program?

 SCHEMAT ALGORYTMU

PRZYKŁADY OBLICZEŃ 

KOD ZRÓDŁOWY

 Wykorzystanie operatora MOD (modulo)

Dzielenie modulo jest powszechnie używane przy obliczaniu cyfry kontrolnej w identyfikatorach. W algorytmie Luhna, numerach PESEL, REGON, NIP, numerach dowodów osobistych, paszportów, numerach towarów EAN, numerach banknotów EURO, numerach kont bankowych IBAN, numerach substancji chemicznych CAS, ISBN, ISMN, ISSN, ISTC, EVN-UIC, numerach recept, prawa wykonywania zawodu lekarza, numerach kontenera i wielu innych.  Podstawowym celem użycia cyfry lub znaku kontrolnego jest wykrywanie pomyłek przy ręcznym wprowadzaniu numeru do systemu informatycznego. Wszystkie te metody zapewniają wykrycie zamiany pojedynczego znaku oraz w znacznej większości zamiany sąsiednich znaków, tzw. czeskiego błędu.

Zadanie - Oblicz resztę z dzielenia – zastosuj  operator mod.

Utwórz w języku Scratch program obliczający resztę z dzielenia liczby naturalnej a przez liczbę naturalną b i wyświetlający wynik (wartość zmiennej reszta) na ekranie. Liczby a i b należy wprowadzić z klawiatury

KOD ZRÓDŁOWY

SCHEMAT ALGORYTMU

PRZYKŁADY OBLICZEŃ 

KOD ZRÓDŁOWY

{/sliders

{slider="Wyodrębnianie cyfr z danej liczby - strona 21"}

SCHEMAT ALGORYTMU

PRZYKŁADY OBLICZEŃ 

KOD ZRÓDŁOWY

SCHEMAT ALGORYTMU

Lista kroków:

• Zacznij algorytm.
• Wprowadź liczbę elementów zbioru: n
• Wprowadź wartość pierwszej liczby a.
• Przyjmij, że liczbą największą jest pierwsza liczba ze zbioru – zmiennej max przypisz wartość pierwszej liczby: max=a.
• Wprowadź wartość kolejnej liczby a.
• Porównaj kolejna liczbę ze zbioru z max: czy a >max?.
• Jeśli kolejna liczba jest większa od max, to zmiennej max przypisz wartość tej liczby: max=a.
• Powtarzaj n-1 razy kroki 5, 6 i 7.
• Zakończ algorytm.

PRZYKŁADY OBLICZEŃ 

KOD ZRÓDŁOWY

OPIS ALGORYTMU

PRZYKŁAD

FILM 

KOD ZRÓDŁOWY

Zadanie

Stwórz grę w zgadywanie liczby w programie Scratch wedle własnego pomysłu. (Liczba poszukiwana jest losowana z przedziału liczb od 1 do 100)

 W tym semestrze będziemy pracować w programie w programie Scratch ?

Drodzy Uczniowie – najpierw proszę, abyście zalogowali się na konto: https://scratch.mit.edu

Jeśli nie macie jeszcze swojego konta, utwórzcie je „Dołączając do Scratch”. Instrukcję możecie zobaczyć tutaj: 

Komunikaty w programie Scratch działają jak komendy, po których nadaniu uruchomią się odpowiednie skrypty.

Pierwszym Waszym projektem będzie stworzenie gry „Kulkoklikacz”. Zapraszam do zapoznania się z materiałem i stworzeniem razem z osobą prezentującą film swoją pracę, którą wyślecie do nauczyciela na adres e-mail: Ten adres pocztowy jest chroniony przed spamowaniem. Aby go zobaczyć, konieczne jest włączenie w przeglądarce obsługi JavaScript. z tematem Klasa 6 - Kulkoklikacz 

Opis programu w książce.  

Uff...jak dużo...uff jak ciężko..uff..jak trudno!!!

A teraz prosto i przyjemnie za pomocą filmu - zapraszam do oglądania!

Przechowanie w skrypcie (programie) jakiejś wartości (liczby, wyniku, znaku...) wymaga wykorzystania zmiennej. Jeśli zaś chcemy operować na większej ilości wartości (kilka liczb, lista słów...) - wykorzystać musimy listę. Elementy listy są numerowane (zaczynając od 1), aby móc odwołać się w danym momencie do określonego elementu listy.

TWORZENIE LISTY

Przechodzimy do kategorii ZMIENNE i klikamy w STWÓRZ LISTĘ – w wyświetlonym oknie wpisujemy nazwę listy – np. LICZBY i klikamy OK>

Po utworzeniu listy widać pole z nazwą listy. Jeśli naciśniemy na nim znak „+” pojawi się miejsce do wpisania dowolnego wyrażenia, które ma znaleźć się na liście – np. liczby lub słowa. W podobny sposób dodajemy następne elementy. Kolejne elementy są na liście numerowane – liczby po lewej stronie oznaczają pozycję elementów na liście. Na dole wyświetla się długość listy tzn. ile elementów znajduje się na liście.

W kategorii ZMIENNE pojawiły się nowe bloki, które można wykorzystać do budowania skryptów. Znajdziesz tu np.. bloki, dzięki którym dodasz element do listy, wstawisz element na konkretną pozycję czy odwołasz się do elementu zapisanego na konkretnej pozycji.

Powyżej wybrane bloki z kategorii ZMIENNE, które pojawią się po utworzeniu listy.

Zadanie.

Utwórz listę o nazwie LICZBY i wypełnimy ją losowo liczbami od 1 do 10. Wpisanych licz ma być 8.

PAMIĘTAJ – jeśli na początku skryptu nie wyczyścisz listy, program umieści wylosowane wartości pod tymi, które już są na liście!!!

ZADANIE DODATKOWE

Zbuduj skrypt, który będzie prosił cię o podawanie wartości, które ma dodać do listy.

{/sliders}

{slider=Zadanie 1 - Gra totolotek}

a) Należy podać 3 liczby do listy (MOJE LICZBY). Podane liczby muszą być w przedziale od 1 do 20.
    Program musi sprawdzić warunek czy podne liczby są > 0 i mniejsze od 21 oraz umiemożliwić wpisanie takich samych liczb.

b) Po wpisanu ostatniej liczby, autoamtycznie zostanie uzupełniona lista (LICZBY KOMPUTERA)- losowymi liczbami.

c) Jeśli podasz 3 liczby, które będą znadowały się w liście wylosowanej prze komputer to Wygrałeś 6!!!

Na początku musisz utworzyć:

- zmieną o nazwie liczba

- listę o nazwie MOJE LICZBY

- listę o nazwie LICZBY Z KOMPUTERA

Wpisanie do listy określonej ilości liczb oraz
-  sprawdzenie warunku czy liczby są w przedziale od 1 do 20
- zabezpieczenie przed wpisaniem takiej samej liczby
-  nadanie komunikatu losuj
- wpisanie trzech liczb

Uzupełnienie losowymi liczbami listy o nazwie (LICZBY KOMPUTERA) po otrzymaniu komunikatu - losuj 

Następnie należy zabezpieczyć listę o nazwie LICZBY Z KOMUTERA, tak aby liczby się nie powtarzały. Musimy przebudować skrypt związany z komunikatem losuj

Zobacz film przed wykonaniem pracy!

Zadanie domowe

Dodaj do mapy jeszcze dwa swoje miasta i wyślij pracę przez stronę (jak to zrobić - zobacz film)