Autor artykułu: mgr Jerzy Wałaszek, wersja 2.0
©2014 mgr Jerzy Wałaszek
I LO w Tarnowie
|
|
Wyjście Spis treści Następny
Autor artykułu: mgr Jerzy Wałaszek, wersja 2.0 |
©2014 mgr Jerzy Wałaszek
|
| Podrozdziały |
| Algorytmy i struktury danych Języki programowania Aplikacja konsoli Prezentacja algorytmu |
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.
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.
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:
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:\>
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 |
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.
zmienna1 ↔ zmienna2
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
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 |