Książka - klasa 8

 Informatyka - Lubię to! 8 (Nowa Era.pl) - wersja elektroniczna

Algorytmy i schematy blokowe

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.

Zmienne - instrukcja warunkowa i pętla - strona 8 - 12

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. 

Pętla powtarzaj aż

Co "co robi" ten program?

Algorytm Euklidesa z odejmowaniem - strona 16

 SCHEMAT ALGORYTMU

PRZYKŁADY OBLICZEŃ 

KOD ZRÓDŁOWY

Operator mod - strona 17

 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

Algorytm Euklidesa z dzieleniem - strona 19

SCHEMAT ALGORYTMU

PRZYKŁADY OBLICZEŃ 

KOD ZRÓDŁOWY

Wyodrębnianie cyfr z danej liczby - strona 21

SCHEMAT ALGORYTMU

PRZYKŁADY OBLICZEŃ 

KOD ZRÓDŁOWY

Wyszukiwanie elementu maksymalnego  w zbiorze nieuporządkowanym - strona 27

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

Porządkowanie zbioru metodą przez wybieranie - strona 31

OPIS ALGORYTMU

PRZYKŁAD

FILM 

KOD ZRÓDŁOWY

Gra - zgadywanie liczb - strona 34

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)