Wstęp


Podrozdziały
Algorytmy i struktury danych
Języki programowania
Aplikacja konsoli
Prezentacja algorytmu

 

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. Dobór właściwej struktury danych dla określonego algorytmu jest jedną z podstawowych umiejętności, które musi opanować informatyk. Od tego doboru zależy wiele rzeczy – 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.

 

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ć Geany) 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.

 

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 batcha – pliku skryptowego z rozszerzeniem bat lub cmd, w którym po prostu umieszcza się kolejne polecenia do wykonania. 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 z pliku !.cmd. Proste i wygodne. Przykładowy 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

 

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 operacja 2 (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 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:

– 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.

 

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

 

+ - × :   podstawowe operacje arytmetyczne
     pierwiastek kwadratowy
mod   reszta z dzielenia całkowitoliczbowego
div   dzielenie całkowite
  operacja logiczna alternatywy
  operacja logiczna koniunkcji
  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
w   zaokrąglenie w dół do najbliższej liczby całkowitej
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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.