Sposoby zapisu algorytmu

Algorytmy powinny być tak przedstawiane, aby było możliwe ich jednoznaczne odczytanie i zastosowanie. Niektóre algorytmy można opisać słownie korzystając z języka potocznego. Jest to proste zwłaszcza wtedy, gdy wykonawcą algorytmów ma być człowiek. Pamiętajmy jednak, iż informatyka zajmuje się opracowywaniem algorytmów, których wykonanie powierzone zostaje komputerom.

Z czego składa się algorytm? 
Algorytm zawiera opis danych, opis wyników oraz plan działania, czyli przetworzenia danych. Plan ten można przedstawić w postaci ciągu czynności, które muszą być wykonane w określonej kolejności. Opis czynności występujących w algorytmie nazywamy instrukcjami.

Algorytm =  opis danych+- opis wyników+ plan działania, przetworzenia danych

Sposoby zapisu algorytmów:

  • opis słowny
  • lista kroków
  • pseudojęzyk, pseudokod
  • schemat blokowy
  • drzewo (drzewo algorytmu)
  • język programowania 

Opis słowny

Przykład. Algorytm znajdujący średnią arytmetyczną dwóch liczb rzeczywistych
Weź dwie liczby i dodaj je do siebie. Otrzymany wynik  przez 2.

Lista kroków

Lista kroków  to najprostszy i jednocześnie najbardziej naturalny  sposób zapisywania algorytmu. Polega na opisie reguł postępowania za pomocą kolejnych kroków, punktów. Sposób często stosowany chociażby na lekcjach matematyki, na których nauczyciel podaje schemat rozwiązania zadania danego typu.

Elementem charakterystycznym w tym sposobie zapisu jest numeracja poszczególnych kroków (wierszy).
 
Przykład. Algorytm znajdujący średnią arytmetyczną dwóch liczb rzeczywistych

Krok 1. Pobierz pierwszą liczbę.
Krok 2. Pobierz drugą liczbę.
Krok 3. Dodaj liczby do siebie.
Krok 4. Wynik sumowania podziel przez 2.
Krok 5. Wyświetl wynik.
Krok 6. Zakończ

Powyższy algorytm możemy zapisać również za pomocą listy kroków pomijając słowa krok:
1. Pobierz pierwszą liczbę.
2. Pobierz drugą liczbę.
3. Dodaj liczby do siebie.
4. Wynik sumowania podziel przez 2.
5. Wyświetl wynik.
6. Zakończ

Pseudojęzyk, pseudokod

Pseudojęzyk to sposób  pośredni między listą kroków a językiem programowania. Zwykle zapis podobny jest do któregoś z popularnych jezyków programowania, ale jest mniej formalny.

Schemat blokowy

Schematy blokowe algorytmów

Do tej pory do opisu algorytmów używaliśmy języka potocznego. Były to jednak algorytmy proste, które ma wykonywać człowiek. W przypadku algorytmów skomplikowanych ten zapis będzie nieczytelny, nie sprawdzi się.

Dlatego teraz poznamy nowy, bardziej przejrzysty sposób – schematy blokowe.

Schemat blokowy to graficzny zapis sposobu rozwiązania zadania, przedstawiający opis i kolejność wykonywania czynności realizujących dany algorytm.

W schemacie blokowym poszczególne operacje przedstawione są za pomocą odpowiednio połączonych skrzynek (klocków, bloków). Połączenia określają kolejność i sposób wykonywania operacji realizujących dany algorytm.
W literaturze informatycznej przyjęto pewne standardowe oznaczenia poszczególnych działań (są to figury geometryczne), ale można również używać innych oznaczeń (muszą one jednak być takie same dla określonego typu operacji).

Przykłady skrzynek (bloków) do prezentacji algorytmu w postaci graficznej:

Elementy schematu blokowego

Elementy schematu blokowego
Symbol graficzny Nazwa skrzynki (bloku) Funkcja Opis
Skrzynki graniczne Skrzynka graniczna Początek algorytmu lub koniec mają kształt owalu. Ze skrzynki START wychodzi tylko jedno połączenie, skrzynka STOP nie ma połączenia wychodzącego
Skrzynka graniczna
Skrzynka operacyjna Skrzynka operacyjna Wykonywanie różnych działań, np. sumowania ma kształt prostokąta
Skrzynka wejścia / wyjścia Skrzynka wejścia / wyjścia Wprowadzanie (czytanie) danych lub wyprowadzanie (drukowanie, pisanie) wyników jest równoległobokiem, wchodzi i wychodzi z niej jedno połączenie
Skrzynka graniczna
Skrzynka warunkowa
Skrzynka warunkowa
Skrzynka warunkowa Sprawdzanie warunku, np. czy N > 0 mają kształt rombu. Ze skrzynki wychodzą tylko dwa połączenia: jedno oznaczone TAK, a drugie NIE


ZASADY BUDOWANIA SCHEMATU BLOKOWEGO

Każda operacja powinna być umieszczona w skrzynce (bloku).

Schemat powinien posiadać tylko jedną skrzynkę „Start” i przynajmniej jedną skrzynkę „Stop”.

Skrzynki powinny być ze sobą połączone.

Ze skrzynki powinno wychodzić jedno połączenie; wyjątek stanowią skrzynki „Stop” (z której nie wychodzą już żadne połączenia) oraz „warunkowa” (z której wychodzą dwa połączenia opisane Tak i Nie – w zależności od tego czy warunek jest spełniony czy też nie; można wyjść jedną z dwóch dróg).

ALGORYTMY WARUNKOWE

Przypomnij: co to jest instrukcja warunkowa ?
Z sytuacjami warunkowymi stykamy się w każdej dziedzinie życia codziennego. Na pytanie „Czy pada deszcz ?” odpowiedź może brzmieć „tak” lub „nie”. W zależności od tego, czy warunek jest spełniony, czy nie, wybieramy inne rozwiązanie.

Przykład sytuacji warunkowej:

Algorytm warunkowy

Przykład 1. Schemat algorytmu warunkowego
Podaj przykłady sytuacji warunkowych. Przedstaw je graficznie.

Wiesz już, że z sytuacją warunkową mamy do czynienia wówczas, gdy wynik lub dalsze działanie zależy od spełnienia warunku. Na schemacie blokowym sytuacje warunkowe realizujemy przez skrzynkę (blok) warunkową. Jak dotąd rozważane przez nas algorytmy przedstawiały problemy z życia. Teraz zajmiemy się rozwiązywaniem prostych zadań obliczeniowych, przy czym algorytm opracowany dla każdego z nich będzie miał postać schematu blokowego.
W skrzynce wpisujemy warunek logiczny, stosując znaki „=” równy,”<>” różny, „<” mniejszy, „>” większy,”<=” mniejszy lub równy, „>=” większy lub równy, np: (a > 5) lub (a <= 20), (a < 5)OR (a <= 20)
Z systemami warunkowymi spotykamy się m.in. w matematyce i fizyce, wtedy gdy wykonywanie działań jest uzależnione od warunku, jakie muszą spełniać liczby, np. mają być nieujemne albo parzyste.

Przykład 2. Schemat algorytmu warunkowego
Przestaw schemat blokowy algorytmu obliczania wartości bezwzględnej.

Najpierw oczywiście musimy wiedzieć co to jest wartość bezwzględna. Bez tej informacji nie jesteśmy w stanie napisać żadnego algorytmu (narysować schematu blokowego, czy też napisać programu).

Wartością bezwzględną liczby nieujemnej jest ta sama liczba, a wartością bezwzględną liczby ujemnej jest liczba do niej przeciwna.

Np wartość bezwzględna liczby 5, to liczba 5.
Wartość bezględna liczby -5, to liczba 5.
Wartość bezwzględna liczby 0, to 0.
W schemacie więc musimy użyć jakiejś skrzynki, która pozwoli nam na sprawdzenie tego warunku. Potrzebna jest więc nam skrzynka warunkowa. Umieścimy w niej napis „czy liczba >=0?”. Oznacza on: „czy liczba jest większa lub równa zero”.

Algorytm – schemat blokowy, wartość bezwzględna
Zadanie do samodzielnego wykonania
Wprowadź dwie liczby a i b. Przedstaw w postaci ciągu kroków i graficznie algorytm porównania tych liczb i wyprowadzania na wyjściu większej z nich. W przypadku liczb równych wyprowadź napis „liczby równe”.

ALGORYTMY ITERACYJNE

Przypomnij : co to są instrukcje iteracyjne ?
Czasami trzeba wykonać te same operacje na wielu liczbach. W takich przypadkach nie jest konieczne wielokrotne opisywanie działań lub rysowanie takich samych skrzynek. Stosujemy wówczas iterację. Mówimy także, że działania te wykonywane są w pętli. Liczba powtórzeń tych działań może być z góry określona lub zależeć od spełnienia warunku. Iteracja to najczęściej spotykana technika algorytmiczna.

Iteracja to technika algorytmiczna polegająca na wykonaniu tej samej instrukcji dla n zmiennych.
Iteracja oszczędza czas programisty, który ten musiałby spędzić wpisując instrukcję n razy, zależnie od liczby zmiennych. Liczba powtórzeń w iteracji jest zwykle z góry określona lub zależy od spełnienia określonego warunku.

Przykład Analiza schematu algorytmu.
Przeanalizuj poniższy schemat blokowy i odpowiedz na pytania:

Jakie są dane wejściowe do zadania i jakich użyto zmiennych pomocniczych?
Jaki cel chcesz osiągnąć (wynik)?
Jaki algorytm zastosowano w operacji dodawania liczb ?
W którym miejscu wykonywane są dzivałania w pętli ?
Które operacje powtarzają się wielokrotnie ?
Co określa liczbę powtórzeń ?
Kiedy kończy się działanie w pętli ?
Iteracja

W analizowanym algorytmie występuje przypisanie typu S:=S + L. Oznacza ono przypisanie zmiennej „s” (sumie) poprzedniej wartości pamiętanej w zmiennej „s” (poprzedniej sumie) zwiększonej o wartość pamiętaną w zmiennej „l” (kolejną liczbę) – w ten sposób powtarzanie operacji przypisania, realizowane jest dodawanie kolejnych liczb naturalnych. Przypisania l:=l-1 ma tu bardzo istotne znaczenie. Jest to tzw. licznik, w którym następuje obliczanie, ile zostało jeszcze powtórzeń do wykonania. W tym algorytmie liczba powtórzeń została określona na początku instrukcją l:=n.

Gdyby nie umieszczono tego działania nastąpiło by tzw. zapętlenie algorytmu, czyli po sprawdzeniu warunku l>0 działanie w schemacie przebiegałoby zawsze drogą TAK. W realizacji algorytmów iteracyjnych ważne jest prawidłowe określenie sposobu zakończenia działań. Można to zrobić za pomocą licznika, który odlicza kolejne kroki iteracji (liczbę powtórzeń).


Przykład Schemat blokowy, algorytm z życia codziennego
Narysuj schemat blokowy algorytmu telefonicznego zaproszenia koleżanki w wersji pierwszej

Aplet Java. Schemat blokowy algorytmu z życia codziennego. Algorytm liniowy
Przykład Schemat blokowy, algorytm z życia codziennego
Narysuj schemat blokowy algorytmu telefonicznego zaproszenia koleżanki w wersji drugiej

Aplet Java. Schemat blokowy algorytmu z życia codziennego. Algorytm warunkowy
Przykład Schemat blokowy, algorytm z życia codziennego
Narysuj schemat blokowy algorytmu telefonicznego zaproszenia koleżanki w wersji piątej

Schemat blokowy, algorytm warunkowy iteracyjny (technika algorytmiczna. z życia codziennego).

Podsumujmy:
Sposób rozwiązania zadania, czyli algorytm, można podać w kilku punktach. Mówimy wówczas, że algorytm jest opisany za pomocą listy kroków (ciągu kroków). Zapis taki polega na podaniu kolejnych wykonywanych operacji, składających się na całe rozwiązanie.

Algorytm można przedstawić również w postaci graficznej, za pomocą schematu blokowego. Schemat blokowy to graficzne przedstawienie ciągu kroków algorytmu, często stosowane jako ideowy rysunek poprzedzający tworzenie programu. Sposób i kolejność działań programu określane są przez wzajemny układ i sposób łączenia bloków (skrzynek) ze sobą. Każde działanie (krok) ma w schemacie blokowym swoje standardowe oznaczenie (patrz tabela wyżej).

Algorytmy: ciągi liczb. Schematy blokowe algorytmów

Ciągi w algorytmach. Przykłady schematów blokowych

Przykład 1
Dany jest ciąg liczb o nieznanej długości. Ostatnia liczba w ciągu równa się zero. Oblicz sumę elementów tego ciągu.

Schemat blokowy algorytmu suma ciągu liczb
Schemat blokowy algorytmu

Przykład 2
Oblicz sumę n – kolejnych liczb naturalnych. Pierwsza z liczb wprowadzona z klawiatury i równa się b.

Przykład 3
Dany jest ciąg n-elementowy. Elementy tego ciągu są różne. Wskaż największy element ciągu.

Zadanie
Dany jest ciąg liczb o nieznanej długości. Ostatnia liczba w ciągu równa się zero. Oblicz średnią arytmetyczną elementów ciągu.

Rozwiązanie: schemat blokowy algorytmu

   

Algorytmy sortowania

ALGORYTMY SORTOWANIA (PORZĄDKOWANIA)

Sortowanie (porządkowanie) – proces ustawienia zbioru obiektów w określonym porządku

Metody sortowania:
przez zamianę (sortowanie bąbelkowe)
przez wybieranie
przez wstawianie
ALGORYTM SORTOWANIA BĄBELKOWEGO
Jedną z popularnych metod sortowania jest sortowanie przez prostą zamianę (sortowanie bąbelkowe). W metodzie tej porównujemy sąsiednie elementy. W celu uporządkowania elementów od najmniejszego do największego, jeśli drugi element jest mniejszy od poprzedniego, to zamieniamy go miejscami. Następnie element, który stał się drugim, porównujemy z trzecim i przestawiamy, jeśli jest mniejszy itd.

Sortowanie bąbelkowe polega na porównywaniu parami kolejnych liczb i przestawianiu, jeśli są ustawione w niewłaściwej kolejności.

Zadanie. Sortowanie bąbelkowe

Uporządkuj liczby: 7 6 1 9 5 w kolejności od najmniejszej do największej.

                    Przebieg pierwszy:
                        7 6 1 9 5    – porównujemy 7 i 6  ( przestawiamy, bo 6 < 7) 
                        6 7 1 9 5    – porównujemy 7 i 1  ( przestawiamy, bo 1 < 7)  
                        6 1 7 9 5    – porównujemy 7 i 9 ( nie przestawiamy, bo 10 > 7) 
                        6 1 7 9 5    – porównujemy 9 i 5 ( przestawiamy, bo 5 < 10)  
                        6 1 7 5 9         – 9 na właściwym miejscu
                   
                    Przebieg drugi:
                        6 1 7 5 9    – porównujemy 6 i 1 ( przestawiamy, bo 1 < 6)  
                        1 6 7 5 9    – porównujemy 6 i 7 ( nie przestawiamy, bo 7 > 6)  
                        1 6 7 5 9   – porównujemy 7 i 5 ( przestawiamy, bo 5 < 7) 
                        1 6 7 5 9    – porównujemy 7 i 5 ( przestawiamy, bo 5 < 7)
                        1 6 5 7 9         – 7 i 9 na właściwym miejscu    

                    Przebieg trzeci:
                        1 6 5 7 9    – porównujemy 1 i 6 ( nie przestawiamy, bo 6 > 1)
                        1 6 5 7 9    – porównujemy 6 i 5 ( przestawiamy, bo 5 < 6)
                        1 5 6 7 9         –  6, 7, 9 na właściwym miejscu
       
                    Przebieg czwarty:
                        1 5 6 7 9    – porównujemy 1 i 5 nie przestawiamy, bo 5 > 1
                        …       
                   
Spójrz wyżej. Czy ciąg po pierwszym przebiegu jest już uporządkowany? Ponieważ nie jest, należy wykonywać kolejne przebiegi. Powinniśmy to robić, aż liczby zostaną uporządkowane, a więc do momentu, aż nie trzeba będzie przestawiać miejscami żadnego elementu.

w czwartym przebiegu nie są zamieniane żadne elementy, czyli nie ma potrzeby dalszego porównywania. Można zakończyć algorytm, liczby są uporządkowane w żądanej kolejności

Zadanie do samodzielnego wykonania
Ułóż 5 książek w przypadkowej kolejności na stole. Uporządkuj je według wysokości (od najwyższej do najniższej), stosując algorytm sortowania bąbelkowego.

ALGORYTM SORTOWANIA PRZEZ WYBIERANIE
Jeśli chcemy uporządkować elementy jakiegoś zbioru np. w kolejności od najmniejszego do największego to możemy wybrać najmniejszy element i umieścić go na początku. Następnie wybieramy najmniejszy element z pozostałego zbioru i umieszczamy go po poprzednio wybranym elemencie (czyli jako drugi) itd.Taka metoda porządkowania nazywa się sortowaniem przez wybór. Polega na wyszukaniu największej liczby, przestawieniu jej na początek ciągu elementów (czyli zamienieniu jej z pierwszą liczbą ciągu) i takim samym postępowaniu dalszym z pominięciem pierwszego elementu.

Zadanie. Sortowanie bąbelkowe

Uporządkuj liczby: 7 6 1 9 5 w kolejności od najmniejszej do największej.

                    7 6 1 9 5    – 1 na pierwszą pozycję, 7 w miejsce 1
                    1 6 7 9 5    – 5 na drugą pozycję, 6 w miejsce 5
                    1 5 7 9 6    – 6 na trzecią pozycję, 7 w miejsce 6
                    1 5 6 9 7    – 7 na czwartą pozycję, 9 w miejsce 7
                    1 5 6 7 9    – 9 na właściwym miejscu (piątym)  
                   
Zadanie do samodzielnego wykonania
Wykonaj zadanie z ćwiczenia drugiego, stosując algorytm sortowania przez wstawianie.

ALGORYTM SORTOWANIA PRZEZ WSTAWIANIE
Metoda porządkowania przez wybór polega na wstawianiu elementu we właściwe miejsce, jest ona powszechnie stosowana przez osoby grające w karty.

                    7| 6  1  9  5 
                    6  7| 1  9  5 
                    1  6  7| 9  5 
                    1  6  7  9| 5 
                    1  6  7  5  9|

                   
Na schemacie kreska odziela posortowaną lewą część liczb od nieposortowanej prawej części.

Jeśli pragniemy ustawić liczby w kolejności od najmniejszego do największego, to bierzemy element drugi i jeśli jest on mniejszy od pierwszego to wstawiamy przed nim. Następnie bierzemy element trzeci i wstawiamy również w odpowiednie miejsce, a więc jeśli jest mniejszy od pierwszego to przed pierwszy, jeśli mniejszy od drugiego to przed drugi.

ALGORYTM SORTOWANIA TABLICY
Przykład
Schemat blokowy algorytmu sortowania bąbelkowego elementów tablicy jednowymiarowej

schemat blokowy

Algorytm. Obliczanie pola trójkąta

Stworzymy algorytm obliczający pole trójkąta.

Rozpoczniemy od zapisania specyfikacji problemu.

Specyfikacja algorytmu obliczającego pole trójkąta

Problem: Obliczanie pola trójkąta.
Dane: a, b, c – trzy dowolne liczby
Wynik:
Jeśli liczby a, b, c są długościami boków trójkąta to wyznaczamy – pole tego trójkąta. Jeśli liczby a,b,c nie tworzą trójkąta wyprowadź komunikat, że dane liczby nie są długościami boków żadnego trójkąta.

Metoda obliczania pola trójkąta

Do obliczania pola trójkąta wykorzystamy wzór zwany wzorem Herona.

gdzie p oznacza połowę długości obwodu trójkąta, czyli p=(a+b+c)/2

Zastanowimy się teraz jakie warunki muszą spełnić liczby a, b i c aby były długościami boków trójkąta. Otóż aby a, b, c były długościamy boków trójkąta muszą być spełnione warunki:

p-a>0
p-b>0
p-c>0
gdzie p – obwód trójkąta

Zatem zanim przystąpimy do obliczania pola trójkąta musimy zbadać czy a,b,c tworzą trójkąt. W tym celu najpierw musimy obliczyć obwód trójkąta. Następnie zbadać jak powyżej …….

Posiadamy zatem już wszystkie informacje, niezbędne do stworzenia algorytmu.

Jak przedstawić nasz algorytm? Pamiętamy, iż istnieją różne sposoby zapisywania algorytmów. My przedstawimy teraz nasz algorytm w postaci listy kroków.

Lista kroków

Krok 1. Oblicz wartość wyrażenia p:=(a+b+c)/2
Krok 2. Jeśli p-a>0 i p-b>0 i p-c> 0 to przejdź do Kroku 3. Jeśli warunki nie są spełnione wyprowadź komunikat, że liczby a,b,c nie są długościami boków trójkąta i zakończ wykonywanie algorytmu.
Krok 3. Oblicz i wypisz wartość wyrażenia S= …..

Schemat blokowy algorytmu

Algorytmy. Tablice jednowymiarowe

 

ALGORYTMY OBSŁUGI TABLIC

Tablicą nazywamy złożoną strukturę danych, która zawiera zbiór elementów tego samego typu.Wyróżniamy:
tablice jednowymiarowe
tablice wielowymiarowe

TABLICE JEDNOWYMIAROWE

Tablica jest to zbiór elementów tego samego typu. Każdy element tablicy jest identyfikowany przez jego numer (indeks). Każdy element tablicy posiada swoją wartość.
Oto tablica o nazwie „t” zawierająca 5 elementów, liczby 5, 11, 8, 3, 2:

Do poszczególnych elementów tablicy uzyskujemy dostęp poprzez podanie nazwy tablicy oraz w nawiasach kwadratowych wartość indeksu (numer żądanego elementu). W naszej tablicy o nazwie t:

t[1] = 5
 t[2] = 11
 t[3] = 8
 t[4] = 3
 t[5] = 2
Element t[i] dla i równego 4 wynosi 3, dla i równego 2 wynosi 11.

Przykład

Opracuj algorytm wypełniający tablicę k – elementową.

Ponieważ tablica ma k- elementów, a więc k- razy nastąpi wczytywanie elementu, stąd zastosowanie iteracji.

Schemat blokowy algorytmu wypełniania tablicy elementami podanymi przez użytkownika:

Przykład
Opracuj algorytm wypisujący elementy tablicy k- elementowej.

Przykład
Zbuduj algorytm sumujący elementy tablicy n- elementowej.

Przykład
Zbuduj algorytm liczący średnią arytmetyczną elementów tablicy.

Przykład
Do tablicy wczytano k-elementów. Wydrukuj położenie i wartość elementu najmniejszego (zakładamy, że elementy są różne).
Przykład
Wczytaj elementy do tablicy k- elementowej, a następnie wypisz je w odwrotnej kolejności.

Przykład
Z tablicy zawierającej k-elementów wybierz elementy podzielne przez 3. Oblicz ich ilość, sumę i średnią.

Przykład
Wczytaj elementy do tablicy k- elementowej. Wydrukuj tę tablicę. Zamień pierwszy z ostatnim i wydrukuj tablicę po modyfikacji.

Przykład
Uporządkuj elementy tablicy k- elementowej, w kolejności od najmniejszego do największego.Aby uporządkować tablicę należy posłużyc się jedną z metod sortowania. My wykorzysamy sortowanie bąbelkowe.

ZADANIA DO SAMODZIELNEGO ROZWIĄZANIA:



Ćwiczenie 1
Opracowany w ćwiczeniu 3 algorytm zmodyfikuj tak, by wynikiem była suma elementów większych od 10.


Ćwiczenie 2
Opracuj algorytm liczący średnią arytmetyczną elementów dodatnich tablicy.


Ćwiczenie 3
Zbuduj algorytm wyszukiwania elementu maksymalnego w tablicy.
Ćwiczenie 4
Opracuj algorytm
wczytujący elementy tablicy k-elementowej
wyszukujący element minimalny
wypisujący elementy tablicy i element minimalny

Algorytm Euklidesa

Algorytm Euklidesa czyli algorytm wyznaczania  NWD – największego wspólnego dzielnika dwóch liczb całkowitych.

Zadanie:
Wyznacz największy wspólny dzielnik dwóch liczb naturalnych: a,b.

Przeanalizujmy zadanie. Dane mamy dwie liczby oznaczone jako a i b. Musimy odnaleźć liczbę przez którą dzielą się nasze obie liczby, zarówno a i b. Takich liczb może być wiele – my mamy odszukać największą.

Przykłady
Dane mamy dwie liczby: 4 i 6.
Dla tych liczb wspólnym dzielnikiem będą: 1, 2. Zatem największym wspólnym dzielnikiem obu tych liczb jest liczba 2.

Dane:  12, 9
Wynik: 3

Dane: 304, 304
Wynik: 304

Dane: 700, 21
Wynik:  7

Dane: 11, 76
Wynik: 1

Na tym etapie możemy zastanowić jak wyznaczyliśmy wspólny dzielnik i opracować algorytm. Możemy jednak skorzystać z gotowego rozwiązania, które opracował Euklides.

Algorytm Euklidesa

Wyznaczanie NWD, a więc największego wspólnego podzielnika dwóch liczb naturalnych
zrealizujemy za pomocą algorytmu Euklidesa. Opiera się on na
spostrzeżeniu, że jeśli odejmiemy od większej liczby mniejszą, to ta
mniejsza liczba i otrzymana różnica będą miały taki sam największy
wspólny dzielnik jak pierwotne liczby. Jeśli w wyniku kolejnego
odejmowania otrzymamy parę równych liczb, oznacza to, że znaleźliśmy NWD.

 

Algorytm Euklidesa: schemat blokowy

Przedstawimy teraz algorytm w postaci schematu blokowego. Na początku następuje wczytanie dwóch liczb. Następnie sprawdzamy czy są to takie same liczby. Jeśli bowiem liczby są równe to od razu wiemy iż ich wspólnym dzielnikiem jest ta sama liczba (przykład 3).
Jeśli liczby są różne sprawdzamy która z nich jest większa, by od większej liczby odjąć mniejszą.

 

Schemat blokowy algorytmu Euklidesa
Algorytm Euklidesa. Schemat blokowy

—————–
Powyższy materiał pochodzi z pracy „Algorytmika w gimnazjum”, którą wykonałam podczas studiów. Materiały te przez długi czas były dostępne na stronie kasia315.republika.pl. Strona ta obecnie nie istnieje, a cała jej zawartość została przeniesiona tutaj, czyli pod adres kaluska.pl.

 

Algorytmy. Przykłady i zadania

Poznałeś już kilka przykładów algorytmów. Przeanalizuj je ponownie, a następnie przejdź do wykonywania poniższych zadań.

Zachęcam Cię, abyś po przeczytaniu treści zadania zastanowił się nad rozwiązaniem, a następnie przedstawił algorytm w postaci listy (ciągu) kroków oraz zbudował schemat blokowy. Dopiero po samodzielnej pracy porównaj i dokonaj analizy gotowego schematu przedstawionego na stronie.

Zadanie

Opracuj algorytm obliczający sumę 3 wprowadzonych z klawiatury liczb.Przedstawmy najpierw algorytm w postaci ciągu kroków do wykonania:

  1. Podaj pierwszą liczbę
  2. Podaj drugą liczbę
  3. Podaj trzecią liczbę
  4. Dodaj do siebie liczby i wynik zapamiętaj
  5. Wypisz otrzymany wynik


Algorytm dodawania liczb 1


Czy zwróciłeś uwagę na operację Suma := a+b+c ?
Przypomnijmy, iż jest to znak przypisania i oznacza nadanie zmiennej znajdującej się po jego lewej stronie wartości określonej po prawej stronie.


Algorytm dodawania liczb 2



Działanie algorytmu dodawania liczb

Zadanie
Dane są dwie liczby. Opracuj algorytm wybierający większą z nich, w przypadku gdy są równe wypisz stosowny komunikat.Algorytm wyboru większej liczby



ZadanieZbuduj algorytm obliczający sumę 5 kolejnych liczb naturalnych.Algorytm sumujący 5 kolejnych liczb naturalnych

Zadanie:

Wyznacz NWD- największy wspólny podzielnik dwóch liczb naturalnych a,b. Algorytm EuklidesaWyznaczanie największego wspólnego podzielnika dwóch liczb naturalnych zrealizujemy za pomocą algorytmu Euklidesa. Opiera się on na spostrzeżeniu, że jeśli odejmiemy od większej liczby mniejszą, to ta mniejsza liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Jeśli w wyniku kolejnego odejmowania otrzymamy parę równych liczb, oznacza to, że znalazłeś NWD.Algorytm Euklidesa. Wyznaczanie NWD- największego wspólnego podzielnika dwóch liczb naturalnych

Algorytm Euklidesa: NWD

Zadanie
Narysuj algorytm sumujący liczby większe od 5 spośród 10 wprowadzonych.


Algorytm sumujący liczby


Zadania

Więcej przykładów i zadań do wykonania znajdziesz tu:

Zadania do samodzielnego wykonania:

  • Opracuj algorytm obliczający kwadrat i sześcian wprowadzonej liczby.
  • Opracuj schemat obliczania średniej n liczb naturalnych.