TEMAT: WYBRANE ALGORYTMY NA TEKSTACH

1. Podstawowe definicje

Algorytm (definicja nieformalna) to sposób postępowania (przepis) umożliwiający

rozwiązanie określonego zadania (klasy zadań), podany w postaci skończonego zestawu
czynności do wykonania, ze wskazaniem ich następstwa.

Algorytmika to dział wiedzy zajmujący się badaniem algorytmów

Sposoby zapisu algorytmu:

 opis słowny,
 lista kroków,
 schemat blokowy,
 drzewo algorytmu,
 pseudokod,
 język programowania

Program - formalnie spisana wersja algorytmu.

1.1. Schemat blokowy

Schemat blokowy (block diagram, flowchart) to diagram, na którym algorytm jest

reprezentowany przez opisane figury geometryczne, połączone liniami zgodnie z kolejnością
wykonywania czynności wynikających z przyjętego algorytmu rozwiązania zadania;
pozwala dostrzec istotne etapy algorytmu i logiczne zależności miedzy nimi.

Na schemacie blokowym poszczególne operacje są opisane za pomocą skrzynek (klocków,

bloków) połączonych ze sobą strzałkami.

Przykład schematu blokowego:

 Elementy schematu blokowego:

Symbol graficzny Nazwa Funkcja Opis

Owalny kształt, wychodzi z niego

tylko
Oznacza początek jedna strzałka, żadna nie może do
Start Blok graniczny niego
algorytmu
prowadzić

Owalny kształt, prowadzi do niego

Oznacza zakończenie jedna
Koniec Blok graniczny
algorytmu strzałka, żadna z niego nie wychodzi

Służy do zapisania
wykonywanych operacji
na
Prostokąt, w jego wnętrzu zapisujemy

Blok operacyjny przykład działań

wykonywane operacje.
x:= i+1 algebraicznych, operacji

podstawienia itp.

Podaj i Służy do wprowadzenia Równoległobok, wchodzi do niego i

Blok wejścia
danych wychodzi jedna strzałka

Wypisz Służy do
wyprowadzenia Równoległobok, wchodzi do niego i
wynik Blok wyjścia
wyniku operacji wychodzi jedna strzałka

Romb, zapisujemy w jego wnętrzu

warunek do sprawdzenia. Wychodzą
z
Blok Służy do sprawdzenia niego dwie strzałki: pierwsza określa
warunkowy
i<n warunku operacje wykonywaną w przypadku
spełnienia warunku, druga w
przypadku
nie spełnienia warunku.

1.2. Pseudokod
Pseudokod jest to połączenie języka naturalnego z elementami języka programowania.

Przykład 1:
Algorytm wczytuje dwie liczby i sprawdza, która jest większa.

Pseudokod:
Start
Wczytaj(a,b)
Jeżeli a>b to
Wypisz(a)
W przeciwnym razie
Wypisz(b)
Koniec
Przykład 2:
Algorytm wczytuje i sumuje n liczb.

Start
Suma:=0
Podaj(n)
i:=0
Dopóki i<n wykonuj:
Wczytaj(a)
Suma := Suma + a
i := i + 1
Wypisz(Suma)
Koniec

Przykład 3:
Algorytm wczytuje i dodaje 10 liczb.

Start
i := 0
Dopóki i<10
Wczytaj(a)
Suma := Suma + a
i := i + 1
Koniec

2. Rodzaje algorytmów:
2.1.Algorytmy liniowe
Algorytm liniowy to taki, w którym nie określono żadnych warunków. Jest też
nazywany sekwencyjnym, gdyż każdy z kroków w tym algorytmie następuje
sekwencyjnie, czyli wykonanie jednej sekwencji powoduje przejście bezpośrednio do
następnej.
Przykład
Obliczanie obwodu prostokąta

Algorytm liniowy w postaci listy kroków

Dane: bok a i b
Lista kroków:
1.Początek algorytmu
2.Podaj bok a
3.Podaj bok b
4. oblicz obwód: ob:=2*a+2*b
5.Wyprowadź wartość ob
6.Koniec algorytmu

Proszę narysować schemat blokowy do przykładu

 Przykład 2. Obliczanie średniej arytmetycznej:
Algorytm liniowy w postaci kroku:
1. Początek algorytmu
2. Podaj a, podaj b
3. Średnia wynosi (a+b)/2
4. Wypisz średnią
5. Koniec algorytmu

Proszę narysować schemat blokowy do przykładu

2.2. Algorytmy warunkowe

Algorytm warunkowy to taki, w którym wykonanie instrukcji uzależnione jest od
spełnienia lub niespełnienia warunku.
Przykład
Obliczanie obwodu prostokąta

Algorytm liniowy w postaci listy kroków

Dane: bok a i b
Lista kroków:
1.Początek algorytmu
2.Podaj bok a
3.Podaj bok b
4.Czy bok a>0?
jeśli tak idź do kroku 5,
jeśli nie podaj komunikat wyjściowy:
"nie można obliczyć obwodu" i zakończ
algorytm.
5. Czy bok b>0?
jeśli tak idź do kroku 6
jeśli nie podaj komunikat wyjściowy:
"nie można obliczyć obwodu" i zakończ
algorytm.
6. Oblicz obwód Ob:=2*a+2*b
7. Wyprowadź wartość Ob
6. Koniec algorytmu
Narysuj algorytm liniowy w postaci schematu blokowego
 2.3. Algorytmy iteracyjne
Iteracją nazywamy instrukcję powtarzania danego ciągu operacji. Liczba powtórzeń może
być ustalona przed wykonaniem instrukcji lub może zależeć od spełnienia pewnego
warunku, który jest sprawdzany w każdej iteracji. Iteracja inaczej zwana jest pętlą.

2.3.1. Pętla z licznikiem

Pętla, w której ilość powtórzeń n jest ustalona z góry. Ilość ta jest "kontrolowana" przez tzw.
zmienną sterującą, która z kolei jest inkrementowana, czyli zwiększana o jeden.
Zwiększenie tej wartości powoduje odpowiednie wyrażenie (licznik), dla zmiennej sterującej
k będzie to k:=k+1. Jeżeli np. zmiennej k nadamy wartość początkową 0 to będzie to
wyglądało następująco:
k:=0 i k:=k+1
0:=0+1(zmienna k przyjmuje wartość 1)- pierwsze przejście
1:=1+1(zmienna k przyjmuje wartość 2)- drugie przejście
2:=2+1(zmienna k przyjmuje wartość 3)- trzecie
przejście itp.

Jeżeli k osiągnie odpowiednią wartość np.k<n to wówczas pętla zostaje opuszczona i

wykonywana jest dalsza część instrukcji.
Przykład
Poniżej znajdują się przykłady, które wypiszą szlaczek z n gwiazdek:

Pętla jest wykonywana tak długo, aż k osiągnieWarunek jest sprawdzany przed wykonaniem
wartość n instrukcji

2.3.2. Pętle warunkowe

Oprócz pętli z licznikiem istnieją jeszcze inne dwa rodzaje pętli, których działanie jest
uzależnione od warunków. Poniżej znajdują się schematy blokowy tych pętli.
Przykład
Najpierw jest wykonywana instrukcja, a Warunek jest sprawdzany na początku, a
następnie jest sprawdzany warunek. Pętla dopiero później jest wykonywana instrukcja.
jest wykonywana, aż do spełnienia Pętla jest wykonywana tak długo, jak
spełniony jest warunek.
warunku.
Instrukcja zostanie wykonana przynajmniej
jeden
raz bez względu na to, czy warunek
jest spełniony czy nie
 Zadanie:
Przykład
Daną wejściową niech będzie dowolna liczba rzeczywista. Na wyjściu chcemy otrzymać informację, czy
liczba ta jest dodatnia czy nie.
Zapiszmy algorytm rozwiązujący to zadanie za pomocą listy kroków:
1. Wczytaj x.
2. Jeśli x > 0, to wypisz: ,x jest liczbą dodatnią" i zakończ.
3. Jeśli x < 0, to wypisz: ,x nie jest liczbą dodatnią" i zakończ.
Możemy ten zapis zredukować do dwóch kroków, przy czym obie li sty kroków będą poprawne:
1. Wczytaj x.
2. Jeśli x > 0, to wypisz: ,x jest liczbą dodatnią", w przeciwnym
wypadku
wypisz: ,x nie jest liczbą dodatnią" i zakończ.

Przykład

Zapisywanie algorytmu z warunkami zagnieżdżonymi w postaci listy kroków

Dane: liczba punktów: p.
Wynik: zależnie od wprowadzonej liczby – jeden z komunikatów: „grupa podstawowa”,
„grupa zaawansowana” lub „wprowadzono liczbę spoza zakresu”.
Lista kroków:
1. Zacznij algorytm.
2. Wprowadź wynik w punktach: p.
3. Jeśli p >= 0 i p <= 60,
o jeśli p < 30, wyprowadź napis „grupa podstawowa”;
o w przeciwnym wypadku wyprowadź napis „grupa zaawansowana”;
w przeciwnym wypadku wyprowadź napis „wprowadzono liczbę spoza zakresu”.
4. Zakończ algorytm.

Przykład
Jest to przykład z pozoru łatwy, a schemat postępowania wydaje się bar dzo prosty:
1. Wczytaj dzielną a.
1 Wczytaj dzielnik b.
3. Wypisz wartość ilorazu: a / b.
4. Zakończ.
Nie przewidzieliśmy jednak, że użytkownik jako wartość dzielnika może podać zero, a wówczas
dzielenie staje się niewykonalne. Powinni śmy więc albo założyć w specyfikacji problemu, że
zmienna b jest różna od zera, albo określić w algorytmie sposób dalszego postępowania w wy padku
wprowadzenia zera dla zmiennej b. Powyższy zapis algorytmu nie jest więc zupełny.
Klasyfikacja operatorów
C/C+
Pascal + Znaczenie

+ + dodawanie

- - odejmowanie

* * mnożenie

/ / dzielenie

dzielenie całkowite, czyli zaokrąglające wynik dzielenia do licz-

div /
by całkowitej, np. 7/5 = 1

mod % reszta z dzielenia liczb całkowitych

Tab. 1.3. Operatory arytmetyczne obowiązujące w językach Pascal i C/C+ +

Kolejna grupa operatorów to operatory relacji, czyli operatory bada jące relacje pomiędzy wyrażeniami
(tab. 1.4).
Pascal C/C+ + Znaczenie

= == równy

> > większy

>= >= większy lub równy

< < mniejszy

<= <= mniejszy lub równy

<> 1 = różny, czyli nieprawda, że równy

Pascal C/C+ + Znaczenie

:= = operator przypisania

Kolejną ważną grupą operatorów, za pomocą których budujemy złożone

wyrażenia logiczne, są operatory logiczne (tab. 1.6):
Pascal C/C+ + Znaczenie zapis matematyczny

and && koniunkcja (iloczyn zdań) A

or II alternatywa (suma zdań) V

not ! negacja (zaprzeczenie zdania) ~

Tab. 1.6. operatory logiczne stosowane w językach Pascal i C/C++

oraz zapis matematycz ny tych operatorów