Zapisywanie algorytmów za pomocą pseudokodu

Poznaliśmy metodę zapisywania algorytmów za pomocą schematów blokowychPqfiWgaRoschematów blokowych oraz listy krokówP1F9R2YOQlisty kroków. Pseudokod, czyli kolejny sposób zapisu, ma podobną strukturę, jednak pomijane są w nim kwestie semantycznesemantykasemantyczne oraz składnioweskładniaskładniowe na rzecz prostoty i czytelności.

Pseudokod przypomina języki programowania – można go więc konwertować na kod. Należy przy tym pamiętać, że pseudokod powinien być pisany bez wskazania na konkretny język. Można w nim stosować formuły matematyczne lub zdania w języku naturalnym, jeśli nie zaburza to czytelności.

Pseudokod nie ma jednego standardu zapisu – zazwyczaj korzysta się ze składni, która opiera się na składni istniejących języków programowania. W tym e‑materiale posłużymy się zapisem, który pojawia się w arkuszach maturalnych.

Wprowadzanie zmiennych

W pseudokodzie nie deklaruje się zmiennych i nie alokuje się jawnie żadnej pamięci, dlatego nowe zmienne mogą pojawiać się bez wcześniejszych zapowiedzi.

W arkuszach maturalnych przypisanie oznaczone jest odwróconą strzałką. Zdarza się też zapis przypisania za pomocą dwukropka i znaku równości.

wprowadź a
b ← 2 - a

Operatory arytmetyczne, relacyjne, logiczne, wartości logiczne

W pseudokodzie możliwe jest zapisywanie operacji arytmetycznych. W tym celu stosuje się następujące operatory arytmetyczne:

• $+$ operator dodawania,

• $-$ operator odejmowania,

• $*$ operator mnożenia,

• $/$ operator dzielenia,

• div dzielenie liczb całkowitych,

• mod dzielenie modulo (reszta z dzielenia), wyłącznie dla liczb całkowitych.

Operatorami porównania (relacyjnymi) używanymi przy zapisie pseudokodu są:

• $<$ logiczny operator relacji między dwoma wyrażeniami, zwraca wartość prawdziwą, gdy wartość wyrażenia po lewej stronie operatora jest mniejsza od wartości wyrażenia po jego prawej stronie,

• $>$ logiczny operator relacji między dwoma wartościami, zwraca wartość prawdziwą, gdy wartość po lewej stronie operatora jest większa od wartości po jego prawej stronie,

• $\le$ logiczny operator relacji między dwoma wartościami, zwraca wartość prawdziwą, gdy wartość wyrażenia po lewej stronie operatora jest mniejsza lub równa wartości wyrażenia po jego prawej stronie,

• $\ge$ logiczny operator relacji między dwoma wartościami, zwraca wartość prawdziwą, gdy wartość wyrażenia po lewej stronie operatora jest większa lub równa wartości wyrażenia po jego prawej stronie,

• $=$ logiczny operator relacji między dwoma wartościami, zwraca wartość prawdziwą, gdy wartości wyrażeń po obu jego stronach są sobie równe,

• $\ne$ logiczny operator relacji między dwoma wartościami, zwraca wartość prawdziwą, gdy wartości wyrażeń po obu jego stronach są różne od siebie.

Operatory logiczne używane są przy zapisie pseudokodu w formie słów:

• i – iloczyn logiczny, zwraca wartość prawdziwą, gdy wyrażenia po obu stronach tego operatora są prawdziwe,

• lub – suma logiczna, zwraca wartość prawdziwą, gdy prawdziwe jest co najmniej jedno z wyrażeń, na których użyto operatora,

• jest/nie jest – operatory pozwalające na tworzenie wyrażenia, często wykorzystywane są do określenia stanu wyrażenia razem z wartościami logicznymi lub do tworzenia warunków opartych na stanie obiektu.

Wartości logiczne używane w pseudokodzie:

• prawda – wartość logiczna określająca prawdziwość zdania logicznego,

• fałsz – wartość logiczna określająca fałszywość zdania logicznego.

Instrukcje warunkowe

Podstawowe słowa kluczowe używane w pseudokodzie przy zapisie instrukcji warunkowych:

• jeżeli – odpowiednik if w językach programowania,

• w przeciwnym wypadku – odpowiednik else w językach programowania.

Słowo kluczowe jeżeli sprawia, że blok kodu, który następuje po tym słowie, będzie wykonany raz, jeżeli warunek występujący po tym słowie będzie spełniony.

...
jeżeli a > b wykonuj
	wypisz "początek bloku"
	wypisz "a większe od b"
    wypisz "koniec bloku"

Zwrot w przeciwnym wypadku oznacza alternatywę dla kodu wykonywanego w przypadku spełnienia warunku zapisanego przy słowie kluczowym jeżeli. Jest wykonywany w przypadku niespełnienia tego warunku. Analogicznie jak instrukcja else jest umieszczana po instrukcji if, tak instrukcja w przeciwnym razie musi być umieszczona w instrukcji jeżeli.

...
jeżeli a > b
	wypisz "początek bloku"
	wypisz "a większe od b"
    wypisz "koniec bloku"
w przeciwnym razie
	wypisz "początek bloku"
	wypisz "a nie większe od b"
    wypisz "koniec bloku"

Instrukcje warunkowe, zgodnie z nazwą, sugerują zawieranie warunku, od którego zależy ich wykonanie. Te warunki to zdania logiczne, wykorzystujące operatory porównania i operatory logiczne.

Pętle

Pętla jest to konstrukcja pozwalająca na cykliczne wykonywanie zawartego w niej fragmentu kodu, tak długo jak długo spełniony jest zawarty w niej warunek. W pseudokodzie podstawowymi słowami występującymi przy zapisie pętli są:

• dopóki – instrukcja powtarzania, odpowiednik polecenia while w językach programowania, w połączeniu z warunkiem i słowem kluczowym wykonaj pozwala na powtarzalne wykonywanie sparowanego z nim kodu, tak długo jak długo spełniony jest warunek,

• wykonuj – instrukcja powtarzania, może być wykorzystana jak polecenie do w językach programowania, wraz ze słowem kluczowym dopóki i warunkiem pozwala na zapisanie pętli odpowiadającej pętli do ... while w językach programowania; instrukcja służy do sygnalizowania, jaki fragment kodu jest zawarty w pętli,

• dla – instrukcja iteracji, słowo kluczowe do stworzenia pętli odpowiadającej pętli for w językach programowania, pozwala na wykonanie zawartego w pętli kodu określoną liczbę razy.

Słowo kluczowe dopóki powoduje, że blok, który po nim następuje, będzie wykonywany, dopóki warunek zapisany po słowie kluczowym pozostaje spełniony.

...
   dopóki a > b wykonuj
       wypisz "początek bloku"
       wypisz "a większe od b"
       wypisz "koniec bloku"

Słowo kluczowe wykonuj może być wykorzystane do stworzenia kolejnego rodzaju pętli, która zawsze wykona się co najmniej raz i będzie powtarzana tak długo, jak długo będzie spełniony warunek (w językach programowania to pętla do ... while). Jej konstrukcja jest podobna do poprzedniej z przedstawianych pętli, jednak blok kodu znajduje się między słowami kluczowymi wykonuj oraz dopóki.

...
   wykonuj
       wypisz "a większe od b"
       a ← a - b
   dopóki a > b

Słowo kluczowe dla pozwala na stworzenie pętli pozwalającej na powtórzenie zawartego w niej kodu określoną liczbę razy (pętla for w językach programowania). Pętla ta zamiast warunku zawiera zmienną, której przypisujemy dozwolony zakres wartości i ustalamy, w jaki sposób ma zmieniać swoje wartości (np. rosnąć o 1, wzrastać dwukrotnie i tak dalej). Warto zwrócić uwagę, że w instrukcji dla wartość przypisujemy znakiem =.

...
   dla n = 1, 2, ..., k wykonuj
       wypisz n

Funkcje

Kolejną istotną notacjąNotacjanotacją jest sposób zapisu funkcji. Funkcje i procedury to wydzielone części programu wykonujące jakieś operacje, które mogą zostać wywołane podczas działania programu. Mogą one przyjmować argumenty i zwracać wartości. W pseudokodzie będziemy je zapisywać następująco:

funkcja nazwa(argument1, argument2...., argumentN)$:$
	....
    zwróc ...

W miejsce elementu nazwa wpisujemy nazwę funkcji, której chcemy użyć. Argumentów może być nieskończenie wiele – taka notacja stanowi alternatywę dla pisania wprowadź a, wprowadź b, wprowadź.... Oto przykładowa funkcja zapisana w pseudokodzie:

funkcja przykład(a, b, c):
	jeźeli a > b
    	zwróć c
    w przeciwnym razie
    	zwróć b

Załóżmy, że jej argumentami są liczby naturalne:

a = 1
b = 2
c = 3

Funkcję wywołamy następująco:

funkcja przykład(a, b, c):
	jeźeli a > b
    	zwróć c
    w przeciwnym razie
    	zwróć b
        
przykład(1, 2, 3)

W pierwszym kroku sprawdzamy, czy 1 jest większe od 2. Nie jest, więc pomijamy instrukcję zawartą w linijce 3.

Od razu przechodzimy do linijek 4 oraz 5, zwracamy zatem liczbę 2.

Tablice

Tablica jest to kontener przechowujący dane tego samego typu, w których dane dostępne są za pomocą indeksów, najczęściej przyjmujące wartości liczbowe. Zapisując pseudokod przy nazwie tablicy w nawiasach kwadratowych, musimy zapisać zakres indeksów, czyli od jakiego indeksu zaczyna się numeracja elementów tablicy i na jakim się kończy. Odczyt elementu z tablicy zapisujemy w postaci nazwy tablicy i wybranego indeksu w nawiasach kwadratowych.

W pseudokodzie indeksy tablicy zazwyczaj zaczynają się od 1, ale coraz częściej numeruje się od 0, co jest zgodne z językami programowania, których wykorzystanie jest dopuszczone na egzaminie maturalnym.

tablica[1..200]
wypisz tablica[8]

W ten sam sposób można też w pseudokodzie zapisać inne struktury o dostępie swobodnym, w razie potrzeby zastępując indeks wybranym kluczem.

Przykłady

Potrafimy już zapisać algorytmy za pomocą listy kroków oraz schematu blokowego, pora więc na przeprowadzenie ich konwersji do pseudokodu.

Algorytm liniowy

Zapoznajmy się ze specyfikacją algorytmuspecyfikacja algorytmuspecyfikacją algorytmu, który oblicza czas potrzebny na pokonanie drogi s2 na podstawie tego, ile czasu (t1) zajęło pokonanie drogi s1.

Zakładamy, że droga pokonywana jest z taką samą prędkością.

Specyfikacja problemu:

Dane:

• t1 – liczba rzeczywista; czas przebycia poprzedniej drogi wyrażony w godzinach

• s1 – liczba rzeczywista; długość wcześniejszej drogi wyrażona w kilometrach

• s2 – liczba rzeczywista; długość drogi wyrażona w kilometrach

Wynik:

• t2 – liczba rzeczywista; czas przebycia drogi wyrażony w godzinach

Gdy podamy niezbędne dane, musimy obliczyć prędkość, z jaką poruszano się przy pokonywaniu drogi s1. Prędkość obliczamy, dzieląc pokonaną drogę przez czas potrzebny na jej pokonanie. Korzystamy tu ze wzoru na prędkość:

$V = \frac{s}{t}$

gdzie:

• $V$ to prędkość wyrażona w kilometrach na godzinę

• $t$ to czas wyrażony w godzinach

• $s$ to długość drogi wyrażona w kilometrach

Przekształcamy ten wzór, aby uzyskać wzór na czas potrzebny na pokonanie danej drogi:

$t= \frac{s}{V}$

Podstawiamy odpowiednie wartości do wzoru i obliczamy wynik.

Lista kroków

1. Podaj t1.

2. Podaj s1.

3. Podaj s2.

4. Przypisz zmiennej V wynik dzielenia s1 przez t1.

5. Przypisz zmiennej t2 wynik dzielenia s2 przez V.

6. Wyświetl wartość zmiennej t2.

7. Zakończ działanie algorytmu.

Pseudokod

wprowadź t1
wprowadź s1
wprowadź s2
V ← s1 / t1
t2 ← s2 / V
wypisz t2

Algorytm rozgałęziony

Zapoznajmy się ze specyfikacją algorytmu sprawdzającego, czy dana liczba jest liczbą dodatnią.

Specyfikacja problemu:

Dane:

• liczba – liczba rzeczywista

Wynik:

• komunikat Liczba nie jest dodatnia lub Liczba jest dodatnia

Schemat blokowy

R1doNdda8bkZ2

Schematu blokowy. 1 Zielony okrąg. Start., 2 Fioletowy romb. Wczytaj liczbę., 3 Granatowy romb. Czy podana liczba jest dodatnia?, Jeśli Czy podana liczba jest dodatnia? fałsz, to 4 Fioletowy romb. Wypisz na ekranie: "Liczba nie jest dodatnia"., 5 Czerwony okrąg. Stop., Jeśli Czy podana liczba jest dodatnia? prawda, to 4 Wypisz na ekranie: "Liczba jest dodatnia"., 5 Czerwony okrąg. Stop.

Pseudokod

wprowadź liczba
jeżeli liczba > 0
	wypisz "Liczba jest dodatnia"
w przeciwnym razie
	wypisz "Liczba nie jest dodatnia"

Algorytm z pętlą

Zapoznajmy się z przykładowym algorytmem obliczania sumy liczb naturalnych w danym przedziale. Zakładamy, że liczba1 jest mniejsza od liczba2.

Specyfikacja problemu:

Dane:

• liczba1 – liczba naturalna; początek przedziału; liczba1 < liczba2

• liczba2 – liczba naturalna; koniec przedziału; liczba2 > liczba1

Wynik:

• suma – liczba naturalna; suma liczb naturalnych w danym przedziale

Lista kroków

1. Podaj liczba1.

2. Podaj liczba2.

3. Przypisz zmiennej i wartość liczba1.

4. Przypisz zmiennej suma wartość liczba1.

5. Zwiększ wartość zmiennej i o 1.

6. Dodaj do zmiennej suma wartość zmiennej i.

7. Jeżeli:

   • i jest równa liczba2

     • przejdź do kroku 8.

   • i jest różna od liczba2

     • wróć do kroku 5.

8. Wyświetl wartość zmiennej suma.

9. Zakończ działanie algorytmu.

Pseudokod

wprowadź liczba1
wprowadź liczba2
i ← liczba1
suma ← liczba1

dopóki i != liczba2
	i ← i + 1
	suma ← suma + i

wypisz suma

Algorytm z tablicą

Zapoznajmy się z przykładowym algorytmem sortującym liczby przechowywane w tablicy niemalejąco. Algorytm wykorzystuje również pętle i instrukcje warunkowe. Więcej o tym algorytmie możesz przeczytać w materiale dotyczącym sortowania bąbelkowegoPCfvfjgLkbąbelkowego.

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba elementów tablicy tablica

• tablica – n-elementowa tablica nieposortowanych liczb rzeczywistych

Wynik:

• tablica – n-elementowa tablica posortowanych niemalejąco liczb rzeczywistych

Pseudokod

n ← 200
tablica[1..n]

dla i = 1, 2, ..., n - 1 wykonuj
	dla j = 2, 3, ..., n - (i - 1) wykonuj
    	jeżeli tablica[j - 1] > tablica[j]
        	tymczasowy ← tablica[j - 1]
            tablica[j - 1] ← tablica[j]
            tablica[j] ← tymczasowy
            
wypisz tablica

Słownik