IDZ DO
IDZ DO
PRZYKŁADOWY ROZDZIAŁ
PRZYKŁADOWY ROZDZIAŁ
Turbo Pascal.
SPIS TRER
CI
SPIS TRER
CI
Ćwiczenia praktyczne
KATALOG KSIĄŻEK
KATALOG KSIĄŻEK
Autor: Andrzej Kierzkowski
KATALOG ONLINE
KATALOG ONLINE
ISBN: 83-7197-219-9
Format: B5, stron: 144
Zawiera dyskietkę
ZAMÓW DRUKOWANY KATALOG
ZAMÓW DRUKOWANY KATALOG
Przykłady na ftp: 73 kB
TWÓJ KOSZYK
TWÓJ KOSZYK
Niniejsza pozycja przeznaczona jest dla uczniów, studentów i wszystkich tych, którzy
DODAJ DO KOSZYKA
DODAJ DO KOSZYKA
pragną zaznajomić się z tajnikami programowania. Z pewnoS
cią przyda się również
nauczycielom, stanowiąc dla nich cenną pomoc w przygotowywaniu się do zajęć
z uczniami.
CENNIK I INFORMACJE
CENNIK I INFORMACJE
Ćwiczenia zawarte w tej książce zapoznają z podstawami programowania, a także
 co stanowi jej niewątpliwą zaletę - uczą  algorytmicznego myS
lenia i sprawnej
ZAMÓW INFORMACJE
ZAMÓW INFORMACJE
analizy sposobów rozwiązania problemu.
O NOWOR
CIACH
O NOWOR
CIACH
ZAMÓW CENNIK
ZAMÓW CENNIK
CZYTELNIA
CZYTELNIA
FRAGMENTY KSIĄŻEK ONLINE
FRAGMENTY KSIĄŻEK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Wstęp .................................................................................................................................... 5
ROZDZIAA
1. Ćwiczenia z myślenia algorytmicznego ......................................................................... 7
1.1. �a dobry początek  jednak prosty program...................................................................................7
1.2. Wróćmy do metod ...........................................................................................................................8
1.3. Co powinieneś zapamiątać z tego cyklu ćwiczeń..........................................................................17
1.4. Ćwiczenia do samodzielnego rozwiązania ....................................................................................18
ROZDZIAA
2. Schematy blokowe ......................................................................................................... 21
2.1.Podstawowe informacje i proste ćwiczenia...................................................................................21
2.2. Co powinieneś zapamiątać z tego cyklu ćwiczeń..........................................................................26
2.3. Ćwiczenia do samodzielnego rozwiązania ....................................................................................27
ROZDZIAA
3. Podstawy Turbo Pascala............................................................................................... 29
3.1. Krótki kurs obsługi środowiska zintegrowanego ..........................................................................30
3.2. Struktura programu w Turbo Pascalu............................................................................................32
3.3. Instrukcje wyjścia (write i writeln)................................................................................................33
3.4. Stałe i zmienne, najcząściej stosowane typy .................................................................................39
3.5. Predefiniowane funkcje .................................................................................................................45
3.6. Instrukcje wejścia (read i readln)...................................................................................................47
3.7. Instrukcja warunkowa....................................................................................................................49
3.8. Pątla for ........................................................................................................................................54
3.9. Inne rodzaje pątli ..........................................................................................................................61
3.10. Funkcje i procedury.....................................................................................................................67
3.11. Co powinieneś zapamiątać z tego cyklu ćwiczeń........................................................................77
3.12. Ćwiczenia do samodzielnego rozwiązania ..................................................................................78
ROZDZIAA
4. Zagadnienia trudniejsze ............................................................................................... 83
4.1. Tablice ...........................................................................................................................................83
4.2. Definiowanie własnych typów ......................................................................................................89
4.3. Moduły standardowe .....................................................................................................................97
4.4. Instrukcja wyboru (case) .............................................................................................................106
4.5. Zbiory ..........................................................................................................................................109
4.6. Typ rekordowy ............................................................................................................................113
4.7. Obsługa plików............................................................................................................................118
4.8. Wskaz
niki ....................................................................................................................................126
4.9. Co powinieneś zapamiątać z tego cyklu ćwiczeń........................................................................136
4.10. Ćwiczenia do samodzielnego rozwiązania ................................................................................137
Pewnie oczekujesz wstąpu do Pascala, wyjaśnienia, czym jest, ćwiczenia  programu, które
pozwoli wypisać coś na ekranie, opisu budowy programów albo informacji o obsłudze samego
programu. Tymczasem w najbliższym czasie nie bądziemy sią zajmować Pascalem. Zajmiemy
sią czymś, co jest trzonem programowania  czyli algorytmami. Aby nie zaczynać jednak
całkiem na sucho, pierwsze ćwiczenie niech jednak bądzie działającym programem. Nie bądzie-
my sią na razie wgłąbiać w jego budową. Spróbujmy go na razie wpisać, uruchomić i zobaczyć
efekt jego działania.
Ćwiczenie 1.1
Napisz i uruchom program, który przywita Cię Twoim imieniem.
Uruchom program Turbo Pascal, wpisując polecenie turbo. Z menu File wybierz �ew (lub
wciśnij kombinacją klawiszy Alt-F-N). W otwarte okienko edycyjne wpisz poniższy program:
program cw1_1;
{ Program wypisuje powitanie osoby, ktora }
{ wlasciwie wpisze swoje imie w odpowiednie miejsce. }
{ dyskietka: 1_01.pas }
const
imie = 'Andrzej'; { Tu wpisz wlasne imie }
begin
writeln ('Witaj, ' + imie + '!');
end.
Przepisz go dokładnie i bez błądów  każda pomyłka może spowodować kłopoty z urucho-
mieniem. Nawet kropka na końcu jest istotna! Jedyną zmianą, którą możesz wprowadzić to
zmiana imienia Andrzej na własne. Nie musisz też koniecznie wpisywać tekstów w nawiasach
C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc 7
8 Turbo Pascal  ćwiczenia praktyczne
klamrowych. Tak w Turbo Pascalu oznaczane są komentarze, nie mające wpływu na działa-
nie programu, ale mające kolosalne znaczenie w przypadku, kiedy program trzeba bądzie
poprawić albo wyjaśnić komuś jego strukturą. Mimo tego, że komentarzy wpisywać nie mu-
sisz, zrób to, aby od początku nabrać dobrych przyzwyczajeń. I nie daj sią zwieść myśli, że
zrobisz to póz
niej. Ja wielokrotnie obiecywałem sobie, że ponieważ jest mało czasu, bądą
pisał sam tekst programu, a kiedyś,  w wolnej chwili , opiszą go komentarzami. Jak sią nie-
trudno domyślić, zaowocowało to tysiącami wierszy nieopisanego tekstu w Turbo Pascalu,
który nigdy już nikomu sią do niczego nie przyda. Zrozumienie, w jaki sposób program
działa może zająć wiącej czasu niż napisanie go od nowa. Wpisując, nie zwracaj uwagi na
to, że niektóre słowa są pogrubione. Zostały tak oznaczone jedynie dla poprawienia czytelności
tekstu. Jeżeli korzystasz z Turbo Pascala w wersji 7.0, zostaną one zresztą automatycznie
wyróżnione podczas wpisywania.
Nadszedł moment uruchomienia. Wciśnij klawisze Ctrl-F9 (jest to odpowiednik wybrania
z menu Run polecenia Run, albo wciśniącia kombinacji klawiszy Alt-R-R). Jeżeli przy wpi-
sywaniu programu popełniłeś błądy, informacja o tym pojawi sią w górnym wierszu okna.
Nie próbuj na razie wgłąbiać sią w jej treść, tylko jeszcze raz dokładnie przejrzyj program
i popraw błąd. Jeżeli program wpisałeś poprawnie, nie zobaczysz nic. A gdzie powitanie?
Powitanie jest, tyle że ukryte. Turbo Pascal wyniki działania programów ukazuje na specjalnym,
do tego celu przeznaczonym ekranie (ang. user screen) który, na razie jest niewidoczny. Aby
przełączyć sią do tego ekranu, należy wcisnąć klawisze Ctrl-F5. Powrót nastąpuje po wci-
śniąciu dowolnego klawisza.
Oto, co powinieneś zobaczyć na ekranie:
Turbo Pascal Version 7.0 Copyright (c) 1983,92 Borland International
Witaj, Andrzej!
Na koniec trzeba wyjść z Turbo Pascala. Wciśnij kombinacją Alt-X (co odpowiada wybraniu
z menu File polecenia Quit (wersja 5.5) bądz
Exit (wersje 6 i 7). Na pytanie, czy zapisać zmiany,
odpowiedz negatywnie.
No właśnie. Przekonałeś sią, że komputer do spółki z Pascalem potrafią zrozumieć to, co masz
im do powiedzenia, wiąc pora... zająć sią teorią. Tak powinieneś robić zawsze, kiedy przyjdzie
Ci rozwiązać jakiś problem za pomocą komputera. Warto siąść z kartką papieru i zastanowić
sią nad jego istotą. Każda minuta poświącona na analizą problemu, może zaowocować
oszcządnością godzin podczas pisania kodu... Najważniejsze jest dobrze problem zrozumieć
i wymyślić algorytm jego rozwiązania. No właśnie. Co to słowo tak właściwie oznacza?
Najprościej rzecz ujmując, algorytm to po prostu metoda rozwiązania problemu, albo pisząc
inaczej  przepis na jego rozwiązanie. Oczywiście nie jest to tylko pojącie informatyczne 
równie dobrze stosuje sią je w wielu dziedzinach życia codziennego (jak choćby w gotowaniu).
Równie dobrze jak myśleć o przepisie na ugotowanie makaronu można rozważać algorytm
jego gotowania. Rozważając algorytm rozwiązania problemu informatycznego, należy mieć
na uwadze:
dane, które mogą być pomocne do jego rozwiązania  wraz ze sposobem ich prze-
chowania, czyli strukturą danych,
wynik, który chcemy uzyskać.
8 C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc
Rozdział 1. Ćwiczenia z myślenia algorytmicznego 9
Gdzieś w tle rozważamy też czas, który mamy na uzyskanie wyniku z danych. Oczywiście,
tak na prawdą myślimy o dwóch czasach: jak szybko dany program trzeba napisać i jak
szybko musi działać. A
atwo jest szybko napisać program, który działa wolno, jeszcze łatwiej
wolno  taki, który działa jak żółw. Prawdziwą sztuką jest szybko napisać coś, co pracuje
sprawnie. Warto jednak mieć na uwadze, że zwykle program (bądz
też jego cząść) jest pisa-
ny raz, a wykorzystywany wiele razy, wiąc  o ile nie grozi to zawaleniem terminów  warto
poświącić czas na udoskonalenie algorytmu.
Rozważając wiąc dane, które masz do dyspozycji oraz mając na uwadze czas, musisz okre-
ślić, w jaki sposób taki wynik uzyskać. Inaczej mówiąc musisz określić działania, których
podjącie jest konieczne do uzyskania wyniku oraz ich właściwą kolejność.
Ćwiczenie 1.2
Zapisz sposób, czyli algorytm gotowania makaronu.
Wróćmy do przykładu z makaronem. Być może istnieją inne sposoby jego ugotowania, ale
moja metoda (algorytm) jest nastąpująca. Przyjmują, że mam makaron spagetti jakości po-
zwalającej uzyskać zadowalający mnie wynik, sól, wodą, garnek, cedzak, minutnik i kuchnią.
Makaron proponują ugotować tak:
1. Wsypać makaron do garnka.
2. Nalać do garnka wodą tak, aby makaron został przykryty.
3. Posolić do smaku (w kuchni takie pojącie jest łatwiej akceptowalne niż w informatyce
 tu trzeba by dokładnie zdefiniować, co oznacza  do smaku , a być może zaprojek-
tować jakiś system doradzający, czy ilość soli jest wystarczająca; ponieważ chcemy
jednak stworzyć algorytm prosty i dokładny, przyjmijmy moją normą  � łyżki ku-
chennej soli na 5 litrów wody.
4. Gotować wodą z makaronem na kuchni. Po zagotowaniu czekać około 8 minut.
5. Zagotowany makaron odcedzić cedzakiem.
6. Również używając cedzaka polać makaron dokładnie zimną wodą, aby sią nie sklejał.
7. Przesypać makaron na talerz.
No i jedzenie gotowe. Można jeszcze pomyśleć nad przyprawieniem makaronu jakimś so-
sem, ale to już inny algorytm. Nie mówią przy tym, że przedstawiona metoda jest najlepsza
czy jedyna. To po prostu mój algorytm gotowania makaronu, który mi smakuje.
Warto zwrócić uwagą, że oprócz samych składników oraz czynności do wykonania niezwykle
ważna jest kolejność wykonania tych czynności. Makaron posolony już na talerzu (po punkcie 7
algorytmu) smakowałby dużo gorzej (choć muszą szczerze przyznać, że już mi sią zdarzyła
taka wpadka). Polewanie zimną wodą makaronu przed włożeniem go do garnka (a wiąc
przed punktem 1) na pewno nie zapobiegnie jego sklejeniu. Już nie mówią o takiej katastrofie,
jaką by było przeniesienie punktu 1 za 4.
Jakie to mało informatyczne. Czy to w ogóle ma związek z tworzeniem programów? Moim
zdaniem TAK. W nastąpnym ćwiczeniu rozważymy mniej kulinarny, a bardziej matematyczny
problem (matematyka cząsto przeplata sią z informatyką i wiele problemów rozwiązywanych
za pomocą komputerów to problemy matematyczne).
C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc 9
10 Turbo Pascal  ćwiczenia praktyczne
Ćwiczenie 1.3
Znajdz
największy wspólny podzielnik (NWD) liczb naturalnych A i B.
Zadanie ma wiele rozwiązań. Pierwsze nasuwające sią  nazwiemy je  siłowym , jest równie
skuteczne, co czasochłonne i niezgrabne. Pomysł jest nastąpujący. Począwszy od mniejszej
liczby, a skończywszy na znalezionym rozwiązaniu sprawdzamy, czy liczba dzieli A i B bez
reszty. Jeżeli tak  to mamy wynik, jak nie  pomniejszamy liczbą o 1 i sprawdzamy dalej.
Innymi słowy sprawdzamy podzielność liczb A i B (załóżmy, że B jest mniejsze) przez B,
potem przez B-1, B-2 i tak do skutku... Algorytm na pewno da pozytywny wynik (w najgorszym
przypadku zatrzyma sią na liczbie 1, która na pewno jest podzielnikiem A i B). W najgor-
szym przypadku bądzie musiał wykonać 2B dzieleń i B odejmowań. To zadanie na pewno
da sią i należy rozwiązać lepiej.
Drugi algorytm nosi nazwą Euklidesa. Polega na powtarzaniu cyklu nastąpujących operacji:
podziału wiąkszej z liczb przez mniejszą (z resztą) i do dalszej działalności wybrania dziel-
nika i znalezionej reszty. Operacja jest powtarzana tak długo, aż resztą bądzie 0. Szukanym
najwiąkszym wspólnym podzielnikiem jest dzielnik ostatniej operacji dzielenia. Oto przy-
kład (szukamy najwiąkszego podzielnika liczb 12 i 32):
32 / 12 = 2 reszty 8
12 / 8 = 1 reszty 4
8 / 4 = 2 reszty 0
Szukanym najwiąkszym wspólnym podzielnikiem 12 i 32 jest 4. Jak widać zamiast spraw-
dzania 9 liczb (12, 11, 10, 9, 8, 7, 6, 5, 4), z wykonaniem dwóch dzieleń dla każdej z nich,
jak miałoby to miejsce w przypadku rozwiązania siłowego, wystarczyły nam tylko trzy
dzielenia.
Bardzo podoba mi sią trzeci algorytm, bądący modyfikacją algorytmu Euklidesa, ale nie
wymagający ani jednego dzielenia. Tak, to jest naprawdą możliwe. Jeżeli liczby są różne,
szukamy ich różnicy (od wiąkszej odejmując mniejszą). Odrzucamy wiąkszą z liczb i czynimy
to samo dla mniejszej z nich i wyniku odejmowania. Na końcu, kiedy liczby bądą sobie
równe  bądą jednocześnie wynikiem naszych poszukiwań. Nasz przykład z liczbami 32 i 12
bądzie sią przedstawiał nastąpująco:
32  12 = 20
20  12 = 8
12  8 = 4
8  4 = 4
4 = 4
Znowu znaleziono poprawny wynik, czyli 4. Operacji jest co prawda wiącej, ale warto
zwrócić uwagą, że są to jedynie operacje odejmowania, a nie dzielenia. Koszt operacji do-
dawania i odejmowania jest zaś znacznie mniejszy, niż dzielenia i mnożenia (pisząc  koszt
mam tu na myśli czas pracy procesora, niezbądny do wykonania działania). Zastanówmy sią
jeszcze, na czym polega różnica pomiądzy ostatnimi dwoma algorytmami. Po prostu szuka-
nie reszty z dzielenia liczb A i B poprzez dzielenie zastąpiono wieloma odejmowaniami.
10 C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc
Rozdział 1. Ćwiczenia z myślenia algorytmicznego 11
Ćwiczenie 1.4
Znajdz
najmniejszą wspólną wielokrotność (NWW) liczb naturalnych A i B.
Czasem najlepsze są rozwiązania najprostsze. Od razu możemy sią domyślić, że  siłowe
rozwiązania (na przykład sprawdzanie podzielności przez A i B liczb od A*B w dół aż do
wiąkszej z nich i przyjącie jako wynik najmniejszej, której obie są podzielnikami) choć istnieją,
nie są tym, czego szukamy. A wystarczy przypomnieć sobie fakt z matematyki z zakresu
szkoły podstawowej:
NWW (A, B) = A*B/NWD (A,B)
i już wiadomo, jak problem rozwiązać, wykorzystując algorytm, który już znamy. Usilne (i cząsto
uwieńczone sukcesem) próby rozwiązania problemu poprzez sprowadzenie go do takiego,
który już został rozwiązany, to jedna z cech programistów. Jak zobaczysz w nastąpnych ćwi-
czeniach, cząsto stosując różne techniki, programiści są nawet w stanie sprowadzić rozwiązanie
zadania do ... rozwiązania tego samego zadania dla innych (łatwiejszych) danych, w nadziei,
że dane w końcu staną sią tak proste, że bądzie można podać wynik  z głowy . I to działa!
Podstawą tak sprawnego znalezienia rozwiązania tego ćwiczenia okazała sią znajomość
elementarnej matematyki. Jak już pisałem, matematyka dość silnie splata sią z programowa-
niem i dlatego dla własnego dobra przed przystąpieniem do  klepania w klawiaturą warto
przypomnieć sobie kilka podstawowych zależności i wzorów. Jako dowód tego zapraszam
do rozwiązania kolejnego ćwiczenia.
Ćwiczenie 1.5
Znajdz
wynik działania AB.
Wygląda na to, że twórcy Turbo Pascala o czymś zapomnieli albo uznali za niepotrzebne, li-
cząc na znajomość matematyki wśród programistów (z drugiej strony wbudowanych jest
wiele mniej przydatnych funkcji). W każdym razie  choć trudno w to uwierzyć  nie ma
bezpośrednio możliwości podniesienia jednej liczby do potągi drugiej. Jest to zapewne jedna
z pierwszych własnych funkcji, które napiszesz. Tylko jakim sposobem? Jako ułatwienie
podpowiem, że trzeba skorzystać z własności logarytmu i funkcji ex.
Należy przeprowadzić nastąpujące rozumowanie:
AB = eln(AB) = eB*ln(A)
ponieważ x = eln(x) oraz ln(xy)= y * ln(x). Obie funkcje (ex i ln(x)) są w Pascalu dostąpne,
wiąc problem w ten sposób możemy uznać za rozwiązany. Nie było to trudne dla osób, które
potrafią sią posługiwać suwakiem logarytmicznym, ale mnie przyprawiło kiedyś o ból głowy
i konieczność przypomnienia sobie logarytmów. Warto pamiątać, że rozwiązanie to bądzie
skuteczne jedynie dla dodatnich wartości podstawy potągi i nie znajdziemy w ten sposób
istniejącego wyniku działania (-4)4.
C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc 11
12 Turbo Pascal  ćwiczenia praktyczne
Ćwiczenie 1.6
Znajdz
silnię danej liczby (N!).
Jak z lekcji matematyki wiadomo, silnia liczby jest iloczynem wszystkich liczb naturalnych
mniejszych od niej lub jej równych. Czyli:
N! = 1 * 2 * ... * (N-1) * N
Już bezpośrednio z tej definicji wynika jedno (całkiem poprawne) rozwiązanie tego proble-
mu. Należy po prostu uzyskać wynik mnożenia przez siebie wszystkich liczb naturalnych
mniejszych lub równych danej. Ten algorytm nosi nazwą iteracyjnego i zostanie dokładnie
pokazany w ćwiczeniu 3.39.
Zastanów sią jednak nad jeszcze drugim algorytmem. Silnia posiada też drugą definicją
(oczywiście równoważną poprzedniej):
1 jeżeli N = 0;
N! =
N * (N-1)! jeżeli N>1.
Coś dziwnego jest w tej definicji. Odwołuje sią do... samej siebie. Na przykład przy liczeniu
5! każe policzyć 4! i pomnożyć przez 5. Jako pewnik daje nam tylko fakt, że 0! = 1. Jak sią
okazuje  zupełnie to wystarczy. Spróbuj na kartce, zgodnie z tą definicją policzyć 5!. Powi-
nieneś otrzymać taki ciąg obliczeń:
5! = 5 * 4!
5! = 5 * (4 * 3!)
5! = 5 * (4 * (3 * 2!))
5! = 5 * (4 * (3 * (2 * 1!)))
5! = 5 * (4 * (3 * (2 * (1 * 0!))))
5! = 5 * (4 * (3 * (2 * (1 * 1))))
5! = 5 * (4 * (3 * (2 * 1)))
5! = 5 * (4 * (3 * 2))
5! = 5 * (4 * 6)
5! = 5 * 24
5! = 120
Jak widać otrzymaliśmy poprawny wynik. Mam nadzieją, że prześledzenie tego przykładu
pozwoli na zrozumienie takiego sposobu definiowania funkcji i przeprowadzania obliczeń.
Metoda ta jest bardzo cząsto wykorzystywana w programowaniu i nosi nazwą rekurencji.
W skrócie mówiąc, polega ona na definiowaniu funkcji za pomocą niej samej, ale z mniejszymi
(bądz
w inny sposób łatwiejszymi) argumentami. A w przypadku programowania  na wy-
korzystaniu funkcji lub procedury przez nią samą.
12 C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc
Rozdział 1. Ćwiczenia z myślenia algorytmicznego 13
Ćwiczenie 1.7
Spróbuj zdefiniować mnożenie dwóch liczb naturalnych A i B w sposób rekurencyjny.
To tylko ćwiczenie  do niczego sią w przyszłości nie przyda (wszak komputery potrafią
mnożyć), ale  mam nadzieją  bliżej zapozna z rekurencją.
A jeżeli B = 1;
A*B =
A + [A * (B-1)] jeżeli B>1.
oczywiście można też:
B jeżeli A = 1;
A*B =
[(A-1) * B] + B jeżeli A>1.
Wiele podejmowanych działań (zarówno matematycznych, jak i w życiu codziennym) pod-
lega zasadzie rekurencji. Kilka ćwiczeń dodatkowych pod koniec rozdziału pozwoli jeszcze
lepiej sią z nią zapoznać.
Ćwiczenie 1.8
Przemyśl sensowność rozwiązania rekurencyjnego problemu N-tego wyrazu ciągu Fibonacciego.
To ćwiczenie to ilustracja swoistej  pułapki rekurencji , w którą łatwo może wpaść nie-
uważny programista. Wiele osób po poznaniu tej techniki stosuje ją, kiedy sią tylko da. A
już na pewno zawsze, gdy problem jest zdefiniowany w sposób rekurencyjny. A
atwo można
stać sią ofiarą tej pożytecznej techniki.
Rozważmy ciąg Fibonacciego, którego wyrazy opisane są definicją rekurencyjną:
0 jeżeli N = 0
1 jeżeli N = 1
F(N) =
F(N-1) + F(N-2) jeżeli N>1.
Wydaje sią, że sama definicja już nasz problem rozwiązuje. Wystarczy wykorzystać rekurencją.
Spróbujmy wiąc na kartce, zgodnie z definicją, policzyć kilka pierwszych wyrazów ciągu:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = F(1) + F(0) + F(1) = 1 + 0 + 1 = 2
F(4) = F(3) + F(2) = F(2) + F(1) + F(2) =
F(1) + F(0) + F(1) + F(1) + F(0) =
1 + 0 + 1 + 1 + 0 = 3
C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc 13
14 Turbo Pascal  ćwiczenia praktyczne
F(5) = F(4) + F(3) = F(3) + F(2) =
F(2) + F(1) + F(2) + F(2) + F(1) =
F(1) + F(0) + F(1) + F(1) + F(0) + F(1) + F(0) +
F(1) = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5
F(8) = F(7) + F(6) = F(6) + F(5) + F(5) + F(4) =
F(5) + F(4) + F(4) + F(3) + F(4) + F(3) + F(3) +
F(2) = ... coś to liczenie nie idzie w dobrym kierunku ...
F(50) =
Czy są jacyś odważni?
Coś jest nie tak  algorytm liczący F(8) każe nam w pewnym momencie liczyć aż trzy razy
F(4) i trzy razy F(3). Oczywiście nie bądzie tego liczył tylko raz i przyjmował wyniku dla
wszystkich obliczeń, ponieważ wystąpują one w różnych wywołaniach rekurencyjnych
i wzajemnie o swoich wynikach nic nie wiedzą. Podobnie nie da sią skorzystać z wyliczonych
już poprzednich wartości, ponieważ nigdzie nie są przechowywane. To jest bardzo zły sposób
rozwiązania tego problemu. Mimo tego, że funkcja posiada dobrą rekurencyjną definicją, jej
zaprogramowanie za pomocą rekurencji nie jest dobre.
A jak zaprogramować obliczanie wartości takiej funkcji za pomocą komputera? Bardzo łatwo
 iteracyjnie. Wystarczy liczyć jej kolejne wartości dla liczb od 2 aż do szukanej i pamiątać
zawsze tylko ostatnie dwa wyniki. Ich suma stanie sią za każdym razem nową wartością i do
kolejnego przebiegu przyjmiemy właśnie ją i wiąkszą z poprzednich dwóch. Czas pracy
rozwiązania iteracyjnego jest wprost proporcjonalny do wartości N. A od czego zależy ten
czas w przypadku rozwiązania rekurencyjnego? Niestety od 2N. Pamiątasz legendą o twórcy
szachów? Jeżeli nie, koniecznie ją odszukaj. Jest ona piąkną ilustracją wzrostu wartości
funkcji potągowej:
N2N
12
24
38
416
10 1024
11 2048
12 4096
20 1048576
30 1073741824
40 1099511627776
60 1152921504606846976
100 267650600228229401496703205376
1000 ok. 1*10301
14 C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc
Rozdział 1. Ćwiczenia z myślenia algorytmicznego 15
Jak widać, wraz ze wzrostem wielkości danej, czas rozwiązywania zadania bądzie rósł w sposób
niesamowity. W ćwiczeniu 3.63 bądziesz miał możliwość sprawdzenia czasu działania algorytmu
o złożoności wykładniczej (tak informatycy nazywają funkcją, która określa czas obliczeń
w zależności od rozmiaru danych) dla różnych danych.
Algorytmów o złożoności wykładniczej stosować nie należy. Istnieje co prawda cała grupa
problemów, dla których nie znaleziono lepszej niż wykładnicza metody rozwiązania
(i prawdopodobnie nigdy nie zostanie ona znaleziona), ale przy ich rozwiązywaniu stosuje
sią inne, przybliżone ale działające szybciej algorytmy. W przeciwnym razie, nawet dla pro-
blemu z bardzo małą daną na rozwiązanie ,trzeba by było czekać wieki.
Dużo lepsze są algorytmy o złożoności wielomianowej (takie, gdzie czas pracy zależy od
potągi rozmiaru problemu (na przykład od kwadratu problemu). Bardzo dobre  w klasie
wielomianowych  są te o złożoności liniowej (i taki udało sią nam wymyślić!). Istnieje jed-
nak jeszcze jedna klasa, którą informatycy lubią najbardziej, i którą poznasz w nastąpnym
ćwiczeniu.
A jako ostatnią informacją z tego ćwiczenia zapamiątaj, że każdy algorytm rekurencyjny da
sią przekształcić do postaci iteracyjnej. Czasami tak łatwo, jak silnią czy ciąg Fibonacciego,
czasem trudniej lub bardzo trudno (swego czasu zamieniałem na postać iteracyjną algorytm,
który w postaci rekurencyjnej miał kilka wierszy, zaś postać iteracyjna miała ich wielokrotnie
wiącej). Prawie zawsze stracimy na czytelności. Zwykle zyskamy na czasie pracy i obciążeniu
komputera. Jeżeli wiąc przekształcenie do postaci iteracyjnej jest proste i oczywiste, należy
to zrobić  ale nie za wszelką ceną.
Ćwiczenie 1.9
Znajdz
metodę obliczania wyrażenia 2N, gdzie N jest liczbą naturalną.
Nasunął Ci sią pierwszy pomysł: skorzystanie z naszego znakomitego algorytmu z ćwiczenia
1.5. Wszak 2N = eN*ln(2), wiąc z szybkim wyliczeniem nie bądzie problemu. Pomysł nawet mi
sią podoba (świadczy o tym, że oswoiłeś sią już z myślą, by rozwiązywać problemy przez
ich sprowadzenie do już rozwiązanych). Ale kłopot polega na tym, że nasza metoda opiera
sią na funkcjach, które działają na liczbach rzeczywistych (ex i ln(x)). Ponieważ komputer
reprezentuje liczby rzeczywiste z pewnym przybliżeniem, nie dostaniemy niestety dokładnego
wyniku  liczby naturalnej. Dla odpowiednio dużego N wynik zacznie być obarczony błądem.
A my tymczasem potrzebujemy wyniku, bądącego liczbą naturalną. Pomyślmy wiąc nad in-
nym rozwiązaniem.
A gdyby tak po prostu N razy przemnożyć przez siebie liczbą 2 (a jeżeli N=0, za wynik
przyjąć 1)? Pomysł jest dobry. Jego złożoność jest liniowa (przed chwilą napisaliśmy, że dla
liczby N należy N razy pomnożyć  liniowość rozwiązania widać bardzo dobrze). Rozwiązanie
jest poprawne.
Ale da sią to zrobić lepiej  rekurencyjnie. Spróbujmy zdefiniować 2N w nastąpujący sposób:
1 jeżeli N=0
2
2N = (2N/2) jeżeli N jest parzyste
2
2*(2 N/2/ ) jeżeli N jest nieparzyste
(jako N/2 rozumiemy całkowitą cząść dzielenia N przez 2). Jako drobne ćwiczenie mate-
matyczne proponują sprawdzić (a może nawet udowodnić?), że jest to prawda. Jeżeli ktoś
C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc 15
16 Turbo Pascal  ćwiczenia praktyczne
chce sią zmierzyć z dowodem, proponują przypomnieć sobie dowody indukcyjne. Rekurencja
w informatyce i indukcja w matematyce to rodzone siostry.
Powstaje pytanie (metodą  rekurencyjną już mamy): czy to daje nam jakąś oszcządność?
Przyjrzyjmy sią jeszcze raz temu wzorowi. Za każdym razem wartość argumentu maleje nie
o jeden czy dwa (jak było w przypadku silni czy ciągu Fibonacciego), ale ... o połową. Czyli
jak szukamy potągi 32, za drugim razem bądziemy już szukać 16, za trzecim 8, potem 4, 2, 1
i zerowej. To nie jest nijak liniowe. To jest o wiele lepsze! Jak nazwać złożoność tego algo-
rytmu? Przyjąło sią mówić, że jest to złożoność logarytmiczna. Oznacza to, że czas rozwią-
zania problemu jest zależny od logarytmu (w tym przypadku o podstawie 2) wielkości danych.
To jest to, co informatycy lubią najbardziej.
Tabelka, którą pokazaliśmy powyżej byłaby niepełna bez danych o złożoności logarytmicznej.
Powtórzmy ją zatem jeszcze raz:
N log 2(N) 2N
10 2
21,00 4
31,58 8
42,00 16
10 3,32 1024
11 3,462048
12 3,58 4096
20 4,32 1048576
30 4,91 1073741824
40 5,32 1099511627776
60 5,91 1152921504606846976
100 6,64 267650600228229401496703205376
1000 9,97 ok. 1*10301
Czy widzisz różnicą? Dla danej o wartości 1000 algorytm logarytmiczny musi wykonać tyl-
ko 10 mnożeń, a liniowy  aż tysiąc. Gdybyśmy wymyślili algorytm wykładniczy, liczby
mnożeń nie dałoby sią łatwo nazwać, a już na pewno nie dałoby sią tej operacji przeprowadzić
na komputerze.
Ten typ algorytmów, które sprowadzają problem nie tylko do mniejszych tego samego typu, ale
do mniejszych przynajmniej dwukrotnie nazwano (moim zdaniem słusznie)  dziel i zwycię-
żaj . Zawsze, jak uda Ci sią problem podzielić w podobny sposób na mniejsze, masz szansą
na uzyskanie dobrego, logarytmicznego algorytmu.
16 C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc
Rozdział 1. Ćwiczenia z myślenia algorytmicznego 17
Ćwiczenie 1.10
Sprawdz
, czy liczba N jest liczbą pierwszą.
Dla przypomnienia: liczba pierwsza to taka, która ma tylko dwa różne, naturalne podzielniki: 1
i samą siebie.
Zadanie wbrew pozorom nie jest tylko sztuką dla sztuki. Funkcja sprawdzająca, czy zadana
liczba jest pierwsza, czy nie (i znajdująca jej podzielniki) w szybki sposób (a wiąc o małej
złożoności) miałaby ogromne znaczenie w kryptografii  i to takiej silnej, najwyższej jako-
ści, a konkretnie w łamaniu szyfrów. Warto wiąc poświącić mu chwilką.
Pierwszy pomysł: dla każdej liczby od 2 do N-1 sprawdzić, czy nie dzieli N. Jeżeli któraś z nich
dzieli  N nie jest pierwsze. W przeciwnym razie jest. Pierwszy pomysł nie jest zły. Funkcja
na pewno działa i ma złożoność liniową. Troszką sią ją da poprawić, ale czy bardzo?
Poczyńmy nastąpującą obserwacją. Jeżeli liczba N nie była podzielna przez 2, to na pewno
nie jest podzielna przez żadną liczbą parzystą. Można wiąc śmiało wyeliminować sprawdzanie
dla wszystkich liczb parzystych wiąkszych od 2. Czyli sprawdzać dla 2, 3, 5, 7, itd. Redu-
kujemy w ten sposób problem o połową, uzyskując złożoność, no właśnie  jaką? Tak, dalej
liniową. Algorytm bez wątpienia jest szybszy, ale ciągle w tej samej klasie.
Pomyślmy dalej. Dla każdego  dużego (wiąkszego od ) podzielnika N musi istnieć po-
N
dzielnik  mały (mniejszy od )  bądący ilorazem N i tego  dużego . Nie warto wiąc
N
sprawdzać liczb wiąkszych od  jeżeli przedtem nie znalez
liśmy podzielnika, dalej też
N
go nie bądzie. Czyli nie sprawdzamy liczb do N-1, tylko do . Czy coś nam to dało?
N
Oczywiście algorytm działa jeszcze szybciej. A jak z jego złożonością? Co prawda nie jest
liniowa, ale dalej pozostała wykładnicza (tylko z lepszym, niż liniowa wykładnikiem). Pro-
ste pytanie: z jakim wykładnikiem złożoność wielomianowa jest liniowa, a z jaką ta, którą
uzyskaliśmy? Jeżeli podałeś odpowiednio wartości 1 i �, to udzieliłeś poprawnej odpowiedzi.
Co to jest algorytm?
Co to jest złożoność algorytmu?
Co to jest iteracja?
Co to jest rekurencja?
Dlaczego rekurencja nie zawsze jest dobra?
Na czym polega metoda  dziel i zwyciężaj ?
Jak wyglądają dobre algorytmy dla kilku prostych problemów: gotowania makaronu,
szukania najwiąkszego wspólnego dzielnika, najmniejszej wspólnej wielokrotności,
silni, wyrazu ciągu Fibonacciego, potągi liczby, sprawdzania czy liczba jest pierwsza.
C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc 17
18 Turbo Pascal  ćwiczenia praktyczne
Ćwiczenie 1.11
Napisz algorytm gotowania ulubionej potrawy.
Możesz posłużyć sią książką kucharską. Zwróć szczególną uwagą na składniki (czyli  dane
algorytmu) oraz na kolejność działań.
Ćwiczenie 1.12
Podaj algorytm udzielania pierwszej pomocy osobie poszkodowanej w wypadku samochodowym.
Ćwiczenie 1.13
Napisz algorytm liczenia pierwiastków równania kwadratowego.
Funkcja (dla przypomnienia) ma postać f(x)=ax2+bx+c. Przypomnij sobie szkolny sposób
liczenia pierwiastków  on w zasadzie jest już bardzo dobrym algorytmem.
Ćwiczenie 1.14
Przeanalizuj problem obliczania wartości wielomianu.
Wielomian ma nastąpującą postać: w(x) = anxn + an-1xn-1 + ... + a1x + a0. Porównaj metodą naj-
bardziej oczywistą (mnożenie i dodawanie  po kolei ) z algorytmem opartym na schemacie
Hornera, który mówi, że wielomian można przekształcić do postaci: w(x) = (...(anx + an-1)x
+ ... + a1)x + a0. Aby to nieco rozjaśnić: wielomian trzeciego stopnia: w3(x) = a3x3 + a2x2 +
a1x + a0 można przekształcić do postaci: w(x) = ((a3x + a2)x+ a1)x + a0  sprawdz
, że to to
samo. Porównaj liczbą działań (mnożeń i dodawań) w obu przypadkach. Czy złożoność
w którymś z nich jest lepsza? Jeżeli nie, to czy mimo wszystko warto stosować któryś z nich?
Może jesteś w stanie zauważyć także jakieś inne jego zalety?
Ćwiczenie 1.15
Przeanalizuj grę w zgadywanie liczby.
Pamiątasz grą: zgadnij liczbą z zakresu 1-1000? Zgadujący podaje odpowiedz
, a Ty mówisz
 zgadłeś ,  za dużo albo  za mało . Gdyby zgadujący  strzelał , długo trwałoby trafienie.
Można jednak wymyślić bardzo sprawny algorytm zgadniącia liczby. Spróbuj go sformuło-
wać. Ile maksymalnie razy trzeba zgadywać, żeby mieć pewność uzyskania prawidłowego
wyniku? Jaką złożoność ma algorytm? Czy przypomina Ci którąś z metod z poprzednich
ćwiczeń? Zapamiątaj nazwą tej metody: przeszukiwanie binarne.
18 C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc
Rozdział 1. Ćwiczenia z myślenia algorytmicznego 19
Ćwiczenie 1.16
Sprawdz
, czy punkt X leży wewnątrz, czy na zewnątrz trójkąta ABC.
Narysuj oba przypadki na kartce i rozważ pola trójkątów, które powstały poprzez połączenie
wierzchołków trójkąta z punktem i kombinacje ich sum. Podaj algorytm sprawdzania.
Ćwiczenie 1.17
Napisz algorytm rozwiązania problemu wież z Hanoi.
Wieże z Hanoi to klasyka zadań informatycznych. Do dyspozycji masz trzy stosy, na któ-
rych układasz kółka. Na początku kółka tworzą piramidą na jednym z nich. Należy całą
przenieść na drugi stos, zgodnie z zasadami: każdorazowo można przenieść tylko jedno kół-
ko ze szczytu dowolnego stosu. Nie można kłaść kółek wiąkszych na mniejsze. Przyjrzyj sią
ilustracji.
Podaj algorytm rozwiązania tego problemu. Zastanów sią nad rozwiązaniem rekurencyjnym.
Jaką złożoność może mieć wymyślony algorytm? Czy myślisz, że da sią znalez
ć rozwiązanie
o lepszej złożoności?
Ćwiczenie 1.18
Rozważ algorytmy przeszukiwania ciągu liczb w celu znalezienia maksimum.
Masz do dyspozycji nieuporządkowany skończony ciąg liczb i zadanie, aby znalez
ć w nim
najwiąkszą liczbą. Przemyśl dwie metody:
1. Przesuwasz sią po kolejnych wyrazach ciągu, sprawdzasz, czy bieżący nie jest wiąkszy
od dotychczas znalezionego najwiąkszego (który pamiątasz), jeżeli tak, to przyjmu-
jesz, że to on jest najwiąkszy. Po dojściu do końca ciągu bądziesz znał odpowiedz
.
2. Działasz rekurencyjnie. Jeżeli ciąg jest jednoelementowy uznajesz, że ten element jest
najwiąkszy. W przeciwnym razie dzielisz ciąg na 2 cząści i sprawdzasz, co jest wiąk-
sze  najwiąkszy element lewego podciągu czy najwiąkszy element prawego podciągu.
Drugi algorytm jest typu  dziel i zwyciążaj i na pierwszy rzut oka wydaje sią lepszy niż
pierwszy (liniowy). Sprawdz
, czy to prawda. Zrób to na kilku przykładach. Który algorytm
jest lepszy? Dlaczego wynik jest taki zaskakujący?
C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc 19
20 Turbo Pascal  ćwiczenia praktyczne
Ćwiczenie 1.19
Przyjrzyj się funkcji Ackermanna.
n+1 jeżeli m=0
A (m-1, n) jeżeli m>0, n=0
A (m, n) =
A (m-1, A (m, n-1)) jeżeli m, n>0
Ta niewinnie wyglądająca funkcja zdefiniowana rekurencyjnie to prawdziwy koszmar. Spróbuj
policzyć A(2, 3), bez pamiątania w czasie wyliczania wartości już policzonych. A A(3, 3)? Czy
odważyłbyś sią policzyć A (4, 3)? Czy algorytm rekurencyjny zdaje tu egzamin?
Spróbuj podejść do zadania w inny sposób. Zapisuj wyliczane wyniki w tabelce (na przykład
w pionie dla wartości m, w poziomie dla n. Poniżej masz początek takiej tabelki:
m.\n 0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10
0
2 3 4 5 6 7 8 9 10 11
1
3 5 7 9
2
5
3
4
Spróbuj policzyć kilka kolejnych wartości. Zastanów sią, w jaki sposób można próbować za-
brać sią do rozwiązania tego problemu iteracyjnie.
20 C:\Andrzej\PDF\TurboPascal - ćwiczenia praktyczne\01.doc


Wyszukiwarka

Podobne podstrony:
Turbo Pascal cwiczenia praktyczne Wydanie II
Pascal Ćwiczenia praktyczne
Praktyczny kurs Turbo Pascala Wydanie IV
Access 10 PL cwiczenia praktyczne cwac10
GIMP cwiczenia praktyczne Wydanie II
Fotografia cyfrowa Ćwiczenia praktyczne
C cwiczenia praktyczne Wydanie II
Flash MX 2004 ActionScript cwiczenia praktyczne cwf4as
Microsoft Publisher 2007 PL cwiczenia praktyczne
Tworzenie stron WWW Ćwiczenia praktyczne Wydanie III
Pajaczek 5 NxG cwiczenia praktyczne
Internet cwiczenia praktyczne Wydanie III cwint3

więcej podobnych podstron