Różne typy algorytmów

Utrwalmy podstawowe informacje na temat algorytmów liniowych i rozgałęzionych.

Wspomnieliśmy o prostym algorytmie słodzenia herbaty. Przypomnijmy sobie jego budowę przedstawioną za pomocą schematu blokowego.

R1O7DetiiPUaq

Ilustracja przedstawia schemat blokowy.
1 Zielony okrąg Start.
2 Błękitny prostokąt Nabierz cukier na łyżeczkę.
3 Błękitny prostokąt Wysyp cukier z łyżeczki do herbaty.
4 Błękitny prostokąt Nabierz cukier na łyżeczkę.
5 Błękitny prostokąt Wysyp cukier z łyżeczki do herbaty.
6 Błękitny prostokąt Nabierz cukier na łyżeczkę.
7 Błękitny prostokąt Wysyp cukier z łyżeczki do herbaty.
8 Czerwony okrąg Stop.

Ten sam ciąg instrukcji powtarzany jest kilkakrotnie. Wielokrotne powtarzanie tych samych czynności nazywamy iteracjąiteracjaiteracją.

Problem słodzenia herbaty jest mało skomplikowany, zastosowanie iteracji nie wpływa znacząco na jego czytelność. Może natomiast skrócić zapis (tak w przypadku pseudokodu, schematu blokowego, jak i języków programowania).

Schemat blokowy algorytmu iteracyjnego

R3i7txAlacLco

Ilustracja przedstawia schemat blokowy.
1 Błękitny prostokąt wartość początkowa iterowanej zmiennej.
2 Niebieski romb warunek. Jeśli 2 to prawda
3 Błękitny prostokąt instrukcja1, instrukcja2.
Powrót do bloku 2
Jeśli 2 to fałsz
Strzałka kieruje poza schemat

W pierwszym bloku operacyjnym zainicjowana zostaje wartość początkowa iterowanej zmiennej (np. posłodzenie herbaty pierwszą łyżeczką cukru). Dzięki temu możemy zliczać liczbę iteracji. Następnie sprawdzany jest warunek. Jeżeli jest on fałszywy, wychodzimy z pętli i nie powtarzamy więcej operacji w niej zawartych. Natomiast jeżeli warunek będzie spełniony, wykonujemy ciąg odpowiednich instrukcji. Po wykonaniu ciągu instrukcji wracamy do sprawdzenia warunku. Jeżeli jest spełniony, ponownie wykonujemy te same instrukcje itd.

Rq3wa9098y99s

Ilustracja przedstawia schemat blokowy.
1 Zielony okrąg Start.
2 Błękitny prostokąt łyżeczka := 1.
3 Niebieski romb łyżeczka mniejsze równe 3.
Dla fałsz w kroku 3,
4 Czerwony okrąg Stop.
Dla prawda w kroku 3,
4 Błękitny prostokąt Nabierz cukier na łyżeczkę.
5 Błękitny prostokąt wysyp cukier z łyżeczki do herbaty.
6 Błękitny prostokąt łyżeczka := łyżeczka + 1.
Powrót do bloku 3.

Algorytm iteracyjny wypisujący liczby z podanego przedziału

Za pomocą pseudokodu zapiszemy algorytm iteracyjnyalgorytm iteracyjnyalgorytm iteracyjny wyświetlający na ekranie liczby całkowite z zakresu $\langle$10, 25$\rangle$.

Pseudokod algorytmu iteracyjnego możemy zrealizować za pomocą instrukcji iteracyjnych. Pętlę utworzymy z wykorzystaniem słów dopóki .. wykonuj. Jeżeli wyrażenie zawarte między dopóki i wykonuj będzie prawdziwe, będą wykonywane instrukcje wymienione bezpośrednio pod nimi. Instrukcje te zapiszemy z użyciem wcięcia. Ma to na celu wskazanie, które instrukcje znajdują się w pętli.

dopóki wyrażenie wykonuj:
	instrukcja1
    instrukcja2

Zapiszmy w postaci pseudokodu algorytm wyświetlający na ekranie liczby całkowite z zakresu $\langle$10, 25$\rangle$.

i := 10
dopóki i <= 25 wykonuj:
	wypisz i
    i := i + 1

W pierwszym wierszu pseudokodu inicjujemy wartość początkową i := $10$. To będzie pierwsza liczba wypisana przez algorytm. Następnie tworzymy pętlę, w której sprawdzane jest to, czy i jest mniejsze lub równe $25$. Jeżeli warunek jest spełniony, wypisujemy wartość i, a następnie zwiększamy ją o $1$, w celu wypisania kolejnej liczby całkowitej. Instrukcje będą wykonywane, dopóki i nie przekroczy wartości $25$.

Słownik