Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Wstęp

SPIS TREŚCI
Podrozdziały

Algorytmy i struktury danych

Informacja jest przechowywana przez komputer w różnych strukturach danych. Niniejszy artykuł opisuje podstawowe algorytmy operujące na różnych strukturach danych, z którymi najczęściej spotyka się programista we współczesnej informatyce. Lista algorytmów i struktur danych w żadnym wypadku nie jest kompletna ( jest to technicznie i czasowo niemożliwe do zrealizowania z uwagi na obszerność problemu ), starałem się jedynie wybrać dla każdej z opisywanych tutaj struktur danych typowe algorytmy wykorzystujące daną strukturę. Dobór właściwej struktury danych dla określonego algorytmu jest jedną z podstawowych umiejętności, które musi opanować każdy informatyk, który poważnie pragnie zajmować się swoją dziedziną. Od tego doboru zależy wiele rzeczy, np. efektywność algorytmu, a zatem czas jego wykonania na określonym komputerze, wymagania pamięciowe, złożoność operacji itp.

Mam nadzieję, że podane tutaj informacje pomogą w takim doborze.

Na początek:  podrozdziału   strony 

Języki programowania

Omawiane w artykule algorytmy są zawsze przedstawione w postaci listy kroków wraz ze specyfikacją danych wejściowych i wyjściowych. Przykładowe implementacje algorytmów zrealizowaliśmy w trzech wybranych środowiskach programowania:

Wszystkie trzy są darmowe, pracują w środowisku Windows/Linux ( w Linuxie instaluje się tylko same kompilatory Free Pascala oraz Free Basica ( kompilator C++ jest zawsze dostępny w Linuxie )  a jako IDE używać można Geany lub Code Blocks ) i można je legalnie pobrać w sieci z witryny producenta, co polecamy niezwłocznie uczynić. Przykłady programów w tych językach nie są celem tego opracowania ( jak sądzą niektórzy czytelnicy ). Są nim algorytmy i na nich głównie skupiamy uwagę. Znając działanie algorytmu można go zaimplementować w dowolnym języku programowania. Dlatego nie żądajcie od nas przesyłania przykładów w dialektach powyższych języków, czy też w innych językach programowania – tym nie zajmujemy się z braku czasu oraz wszechwiedzy.

Niekiedy dodaliśmy również przykład w języku skryptowym JavaScript, który pozwala czytelnikowi interaktywnie sprawdzić omawiane zagadnienia. Jednakże w przypadku JavaScript nie bawimy się w prezentację kodu w artykule. Dostęp do kodu JavaScript można w prosty sposób uzyskać przeglądając źródło strony WWW, co potrafi wykonać praktycznie każda współczesna przeglądarka.

Na początek:  podrozdziału   strony 

Aplikacja konsoli

Wszystkie przykłady programów będą uruchomione w trybie konsoli. Cechą charakterystyczną tego trybu jest okno tekstowe ( w Linuxie jest to okno terminala ), które służy zarówno do wprowadzania jak i do wyprowadzania danych. Zaletą jest prostota komunikacji z użytkownikiem. W języku Pascal wykorzystuje się polecenia writeln i write do zapisu oraz readln i read do odczytu danych. W języku C++ można w tym charakterze wykorzystywać obiekty biblioteki STL cout oraz cin. W języku Basic stosowane są polecenia print i input.

Dane wprowadzane do programu pracującego w trybie konsoli mogą pochodzić z kilku źródeł. Pierwszym z nich jest oczywiście klawiatura. Jednakże wpisywanie długich ciągów liczb, szczególnie gdy muszą się one powtarzać przy testowaniu działania programu, jest niewygodne. W takiej sytuacji mamy dwa wyjścia:

  1. Dane wklejamy do okna konsoli poprzez schowek Windows. W notatniku przygotowujemy sobie odpowiednie liczby do wprowadzenia do programu, następnie kopiujemy je do schowka Windows i wklejamy do okna konsoli. W tym celu klikamy w okienko konsoli prawym przyciskiem myszki i z menu kontekstowego wybieramy polecenie Wklej. Wybierając polecenie Oznacz, a następnie zaznaczając myszką obszar w oknie konsoli i wciskając na koniec klawisz Enter, można skopiować do schowka treść okna konsoli. Poniższy tekst pochodzi z takiej właśnie operacji:
    C:\>date
    Bieżąca data: 2008-03-05
    Wprowadź nową datę: (rr-mm-dd)
    
    C:\>time
    Bieżąca godzina: 22:10:08, 84
    Wprowadź nową godzinę:
    
    C:\>
  2. Przy uruchamianiu programu przekierowujemy jego standardowe wejście lub wyjście do pliku zamiast na konsolę. W tym celu wystarczy wydać polecenie:
    nazwa_programu < plik_wejścia > plik_wyjścia

    Załóżmy na przykład, iż napisaliśmy program o nazwie szukaj.exe. Jeśli dane wejściowe dla programu przygotowaliśmy w pliku d_we.txt, a dane wyjściowe chcemy otrzymać w pliku d_wy.txt, to wydajemy następujące polecenie:

    szukaj < d_we.txt > d_wy.txt

    Program uruchamiamy w opisany powyżej sposób z okna konsoli. W tym celu należy kliknąć przycisk Start i w opcji uruchom wpisać polecenie cmd. Polecenie to otwiera okno konsoli i umożliwia użytkownikowi wprowadzanie z klawiatury różnych rozkazów systemu operacyjnego. Przy pomocy polecenia cd przechodzimy do katalogu z projektem i wydajemy wyżej opisane polecenia. Program, który ma być uruchamiany w takim trybie nie powinien przy zakończeniu czekać na reakcję użytkownika – po prostu czyta dane, przetwarza je, wyprowadza wyniki i kończy działanie. Tak właśnie pracują nasze przykłady.

Jeśli często wykorzystujesz uruchamianie z przekierowaniem standardowego wejścia/wyjścia do tych samych plików z danymi, to rozważ stworzenie prostego pliku batch – pliku skryptowego z rozszerzeniem bat lub cmd, w którym po prostu umieszcza się kolejne polecenia do wykonania. Plik batch zapisuje się następnie w katalogu projektu pod jakąś krótką nazwą – ja stosuję !.cmd i w konsoli wystarczy wpisać !, aby uruchomić kolejne polecenia zawarte w pliku !.cmd. Proste i wygodne. Przykładowy plik batch !.cmd może wyglądać tak:

@echo off
cls
echo Test aplikacji SZUKAJ.EXE
echo Odczyt danych, przetwarzanie i zapis wynikow, prosze czekac...
echo.
szukaj < s_we.txt > d_wy.txt
echo Koniec przetwarzania.
type d_wy.txt
echo.

Prezentowane w artykule programy są maksymalnie uproszczone – odczytują wymagane dane wejściowe, przetwarzają je i wypisują wyniki beż żadnych dodatkowych upiększeń. Mogą one być materiałem do dopracowania na lekcji lub kole informatycznym – np. uczniowie dopisują do nich odpowiedni interfejs komunikacji z użytkownikiem. Wszystko zależy zatem od nauczyciela. Aplikacje te należy uruchamiać z poziomu okna konsoli ( Start → Uruchom → cmd ), ponieważ nie będą czekały na reakcję użytkownika przy zakończeniu działania – uruchomienie ich z poziomu Windows spowoduje zamknięcie okienka konsoli przy zakończeniu programu, zatem zapewne nie zdążysz nic przeczytać. W takiej postaci programy tworzy się zwykle na wszelkiego rodzaju konkursach, w tym na olimpiadzie informatycznej. Dlatego i my wybieramy ten sposób.

Jeśli jednak chciałbyś pracować w środowisku Windows, to możesz dodać na końcu programu następujące polecenia wstrzymujące zamknięcie okna konsoli, aż do naciśnięcia klawisza Enter:

Pascal : readln;
C++ : system ( "pause" );
Basic : Sleep
Na początek:  podrozdziału   strony 

Prezentacja algorytmu

Wszystkie algorytmy opisane w tym artykule są przedstawione w postaci listy kroków oraz implementacji w trzech językach programowania: FreePascal, Code::Blocks oraz FreeBasic. Lista kroków zawsze jest poprzedzona specyfikacją algorytmu zbudowaną z następujących trzech sekcji:

Na liście kroków używamy następujących konstrukcji algorytmicznych:

zmienna  ← wyrażenie

Operacja przypisania. Wartość wyrażenia zostaje umieszczona w zmiennej.

zmienna1zmienna2

Zamiana zawartości. Po operacji zmienna1  będzie zawierała to co zmienna2, a zmienna2  to co zmienna1.

Jeśli warunek,
to oparacja1,
inaczej operacja2

Jest to typowa instrukcja warunkowa. Jeśli warunek będzie spełniony, to zostanie wykonana operacja1 ( operacja2 nie będzie wykonana ). Jeśli warunek nie będzie spełniony, to zostanie wykonana operacja2 ( teraz operacja1 nie będzie wykonana ). Jeśli brak członu inaczej, to algorytm przechodzi do następnego kroku. Konstrukcja ta umożliwia tworzenie rozgałęzień w algorytmie. Czasami zamiast pojedynczej operacji podajemy ich ciąg rozdzielony przecinkami.

Dla zmienna  = a, b, ..., n:
wykonuj operacja

Dla zmienna  = a, b, ..., n:
wykonuj
kroki Kxx...Kyy

Jest to konstrukcja pętli iteracyjnej. Dla kolejnych wartości zmiennej  równych a, b..., c wykonywana jest wskazana operacja lub wykonywane są kroki w zakresie od Kxx do Kyy. Kroki wykonywane są kolejno od góry do dołu. Gdy pętla się zakończy wykonywany jest krok Kyy + 1 – znajdujący się za ostatnią z powtarzanych instrukcji. Dodatkowo w obrębie pętli stosujemy wcięcia, aby poprawić czytelność tej konstrukcji.

Dopóki warunek,
wykonuj operacja

Dopóki warunek,
wykonuj kroki Kxx...Kyy

Jest to konstrukcja pętli warunkowej. Jeśli warunek jest prawdziwy, to wykonywana jest operacja lub kolejne kroki od Kxx do Kyy. Kroki wykonywane są kolejno od góry do dołu. Po ostatnim kroku Kyy warunek jest ponownie testowany i w przypadku jego spełnienia, kroki Kxx ... Kyy są wykonywane ponownie. Gdy pętla się zakończy wykonywany jest krok Kyy+1 – za ostatnią z powtarzanych instrukcji. W przypadku, gdy warunek jest nieprawdziwy przed wejściem do pętli, nie zostanie wykonany żaden krok od Kxx do Kyy – algorytm przejdzie do kroku Kyy+1.

Idź do kroku Kxx

Następnym krokiem wykonywanym przez algorytm będzie krok Kxx.

Następny obieg pętli Kxx

Algorytm przejdzie do wykonania kolejnego obiegu pętli zdefiniowanej w kroku Kxx. Przed rozpoczęciem obiegu sprawdzane są odpowiednie warunki kontynuacji pętli:

– dla pętli warunkowej warunek kontynuacji musi być prawdziwy
– dla pętli iteracyjnej zmienna sterująca otrzymuje kolejną wartość i, jeśli mieści się ona w zakresie, to pętla wykonuje kolejny obieg.

Pisz wyrażenie

Algorytm wyprowadza na wyjście wartość wyrażenia.

Czytaj zmienna [ , zmienna  ]

Algorytm odczytuje z wejścia dane dla podanej zmiennej. Tam, gdzie dane wejściowe są oczywiste i opisane w specyfikacji, pomijamy ich odczyt w algorytmie.

Zakończ

Kończy działanie algorytmu

Zakończ z wynikiem x

Kończy działanie algorytmu z wynikiem x – ta postać zakończenia jest używana w algorytmach funkcji.

Opis słowny

Niektóre operacje algorytmu muszą być opisane słownie, ponieważ ich wykonanie zależy od specyfiki używanego języka programowania lub też wymaga wielu operacji prostych.

W wyrażeniach stosujemy następujące operatory:

+ - × :   podstawowe operacje arytmetyczne
sqr ( w )   pierwiastek kwadratowy z w
mod   reszta z dzielenia całkowitoliczbowego
div   dzielenie całkowite
obrazek   operacja logiczna alternatywy
obrazek   operacja logiczna koniunkcji
obrazek   operacja logiczna sumy symetrycznej
¬   operacja logiczna negacji
and   bitowa operacja koniunkcji
or   bitowa operacja alternatywy
not   bitowa operacja negacji
xor   bitowa operacja sumy modulo 2
shr   przesunięcie bitowe w prawo
shl   przesunięcie bitowe w lewo
[ w ]   część całkowita z w
floor ( w )   zaokrąglenie w dół do najbliższej liczby całkowitej
ceil ( w )   zaokrąglenie w górę do najbliższej liczby całkowitej
< ≤ = ≠ ≥ >   operatory porównań
  wskazanie pola struktury
.   odwołanie do pola struktury

Zapraszam do lektury
mgr Jerzy Wałaszek

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.