Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00143 007788 10468836 na godz. na dobę w sumie
Turbo Pascal. Ćwiczenia praktyczne - książka
Turbo Pascal. Ćwiczenia praktyczne - książka
Autor: Liczba stron: 144
Wydawca: Helion Język publikacji: polski
ISBN: 83-7197-219-9 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> turbo pascal - programowanie
Porównaj ceny (książka, ebook, audiobook).

Turbo Pascal w wersji 5.5 do ściągnięcia ze strony Borlanda

Turbo Pascal, mimo upływu lat i wielu krytycznych głosów (np. sugerujących, że jego czas już minął), wciąż jest uważany za dobry start w nauce programowania. Co więcej, ma coraz popularniejszego potomka, jakim jest Delphi.

Aby poznać uroki programowania, początkujący użytkownik musi zapoznać się podstawami. Książka Andrzeja Kierzkowskiego gwarantuje, że już wkrótce przestaną być tajemnicą niekóre zagadnienia natury programistycznej. Ze wspaniałą wprawą, autor zapoznaje czytelnika z podstawami programowania, a następnie wprowadza w tematy trudniejsze, jak np. moduły, definiowanie własnych typów tablic, wskaźniki. W serii przeszło stu skomentowanych ćwiczeń zawarta została esencja programowania za pomocą Turbo Pascala.

Nie czekaj! Napisz już dziś swoją pierwszą aplikację! A 'nawet jeżeli nigdy w życiu nie zostaniesz programistą, jeżeli żaden z twoich programów nie zostanie sprzedany i nie będzie wykorzystany przez rzesze użytkowników', czytelnik zdobędzie, jak zapewnia autor, 'umiejętność algorytmicznego myślenia' i sprawnej analizy sposobów rozwiąznia problemów.

Książka jest wspaniałym podstawowym podręcznikiem dla każdego ucznia, studenta oraz wykładowcy. Przygotuje do lekcji, kolokwium, egzaminu, a przede wszystkim nauczy cię Turbo Pascala. Znajdziesz w niej m.in.:

Na nowo poznasz naturę liczb stało- i zmiennopozycyjnych, niebezpieczeństwa używania zmiennych! Zostaniesz wprowadzony w zagadnienia:
Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

Turbo Pascal. ˘wiczenia praktyczne Andrzej Kierzkowski Autor: ISBN: 83-7197-219-9 Format: B5, stron: 144 Zawiera dyskietkŒ Przyk‡ady na ftp: 73 kB Niniejsza pozycja przeznaczona jest dla uczni(cid:243)w, student(cid:243)w i wszystkich tych, kt(cid:243)rzy pragn„ zaznajomi(cid:230) siŒ z tajnikami programowania. Z pewno(cid:156)ci„ przyda siŒ r(cid:243)wnie¿ nauczycielom, stanowi„c dla nich cenn„ pomoc w przygotowywaniu siŒ do zajŒ(cid:230) z(cid:160) uczniami. ˘wiczenia zawarte w tej ksi„¿ce zapoznaj„ z podstawami programowania, a tak¿e (cid:150)(cid:160) co(cid:160) stanowi jej niew„tpliw„ zaletŒ - ucz„ (cid:132)algorytmicznego(cid:148) my(cid:156)lenia i sprawnej analizy sposob(cid:243)w rozwi„zania problemu. IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TRE(cid:140)CI SPIS TRE(cid:140)CI KATALOG KSI¥flEK KATALOG KSI¥flEK KATALOG ONLINE KATALOG ONLINE ZAM(cid:211)W DRUKOWANY KATALOG ZAM(cid:211)W DRUKOWANY KATALOG TW(cid:211)J KOSZYK TW(cid:211)J KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAM(cid:211)W INFORMACJE ZAM(cid:211)W INFORMACJE O NOWO(cid:140)CIACH O NOWO(cid:140)CIACH ZAM(cid:211)W CENNIK ZAM(cid:211)W CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥flEK ONLINE FRAGMENTY KSI¥flEK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Wstęp ...................................................i...................................................i.............................. 5 ROZDZIAŁ 1. Ćwiczenia z myślenia algorytmicznego ...................................................i...................... 7 1.1. Na dobry początek – jednak prosty program...................................................y................................7 1.2. Wróćmy do metod ...................................................y...................................................y.....................8 1.3. Co powinieneś zapamiętać z tego cyklu ćwiczeń...................................................y.......................17 1.4. Ćwiczenia do samodzielnego rozwiązania ...................................................y.................................18 ROZDZIAŁ 2. Schematy blokowe ...................................................i...................................................i... 21 2.1.Podstawowe informacje i proste ćwiczenia...................................................y................................21 2.2. Co powinieneś zapamiętać z tego cyklu ćwiczeń...................................................y.......................26 2.3. Ćwiczenia do samodzielnego rozwiązania ...................................................y.................................27 ROZDZIAŁ 3. Podstawy Turbo Pascala...................................................i............................................ 29 3.1. Krótki kurs obsługi środowiska zintegrowanego ...................................................y.......................30 3.2. Struktura programu w Turbo Pascalu...................................................y.........................................32 3.3. Instrukcje wyjścia (write i writeln)...................................................y.............................................33 3.4. Stałe i zmienne, najczęściej stosowane typy ...................................................y..............................39 3.5. Predefiniowane funkcje ...................................................y..............................................................45 3.6. Instrukcje wejścia (read i readln)...................................................y................................................47 3.7. Instrukcja warunkowa.............................y...................................................y....................................49 ........................54 3.8. Pętla for ...................................................y...................................................y.......... 3.9. Inne rodzaje pętli ...................................................y...................................................y. ...................61 3.10. Funkcje i procedury...................................................y...................................................y...............67 3.11. Co powinieneś zapamiętać z tego cyklu ćwiczeń...................................................y.....................77 3.12. Ćwiczenia do samodzielnego rozwiązania ...................................................y...............................78 ROZDZIAŁ 4. Zagadnienia trudniejsze ...................................................i............................................ 83 4.1. Tablice ...................................................y...................................................y.....................................83 4.2. Definiowanie własnych typów ...................................................y...................................................89 4.3. Moduły standardowe ...................................................y...................................................y.. .............97 4.4. Instrukcja wyboru (case) ...................................................y..........................................................106 4.5. Zbiory ...................................................y...................................................y.............. ......................109 4.6. Typ rekordowy ...................................................y...................................................y......................113 4.7. Obsługa plików.....................................y...................................................y....................................118 4.8. Wskaźniki ...................................................y...................................................y........... ...................126 4.9. Co powinieneś zapamiętać z tego cyklu ćwiczeń...................................................y.....................136 4.10. Ćwiczenia do samodzielnego rozwiązania ...................................................y.............................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 Nimieniem. Uruchom program Turbo Pascal, wpisując polecenie turbo. Z menu File wybierz New (lub wciśnij kombinację klawiszy Alt-F-N). W otwarte okienko edycyjne wpisz poniższy program: program cw1_1; { Program wypisuje powitanie osoby, ktora o } { wlasciwie wpisze swoje imie w odpowiednie miejsceo. } { dyskietka: 1_01.pas o } 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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.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óź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 Interonational 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ądź 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ściwkie 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: M dane, które mogą być pomocne do jego rozwiązania – wraz ze sposobem ich prze- chowania, czyli strukturą danych, M wynik, który chcemy uzyskać. 8 C:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc Rozdział 1. M Ć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ć. Ł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ądź 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 ickh 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. 2. 3. 4. 5. 6. 7. Wsypać makaron do garnka. Nalać do garnka wodę tak, aby makaron został przykrkyty. 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. Gotować wodę z makaronem na kuchni. Po zagotowaniu czkekać około 8 minut. Zagotowany makaron odcedzić cedzakiem. Również używając cedzaka polać makaron dokładnie zimnąk wodą, aby się nie sklejał. 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 makakronu, 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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc 9 10 Ćwiczenie 1.3 Turbo Pascal – ćwiczenia praktyczne Znajdź największy wspólny podzielnik (NWD) liczb naturaNlnych 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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc Rozdział 1. M Ćwiczenia z myślenia algorytmicznego 11 Ćwiczenie 1.4 Znajdź najmniejszą wspólną wielokrotność (NWW) liczb natuNralnych 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 kpodać 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 Znajdź wynik działania A B . 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 x podpowiem, że trzeba skorzystać z własności logarytkmu i funkcji e . Należy przeprowadzić następujące rozumowanie: B A = e ln(AB) B*ln(A) = e y x )= y * ln(x). Obie funkcje (e ln(x) oraz ln(x ponieważ x = e 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, alke 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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc 11 12 Ćwiczenie 1.6 Turbo Pascal – ćwiczenia praktyczne Znajdź 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ądź w inny sposób łatwiejszymi) argumentami. A w przypadku programowania – na wy- korzystaniu funkcji lub procedury przez nią samą. 12 C:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc Rozdział 1. M Ćwiczenia z myślenia algorytmicznego 13 Ćwiczenie 1.7 Spróbuj zdefiniować mnożenie dwóch liczb naturalnych A Ni 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 rekurekncją. oczywiście można też: A*B = A*B = A jeżeli B = 1; A + [A * (B-1)] jeżeli B 1. B jeżeli A = 1; [(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 problemNu 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. Łatwo można stać się ofiarą tej pożytecznej techniki. Rozważmy ciąg Fibonacciego, którego wyrazy opisane są kdefinicją rekurencyjną: F(N) = 0 jeżeli N = 0 1 jeżeli N = 1 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ą, polickzyć 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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.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 ..e. 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 dobrke. 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: N 1 2 3 4 10 11 12 20 30 40 60 100 1000 2N 2 4 8 16 1024 2048 4096 1048576 1073741824 1099511627776 1152921504606846976 267650600228229401496703205376 ok. 1*10301 14 C:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc Rozdział 1. M Ć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 bykł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 Znajdź metodę obliczania wyrażenia 2 N , gdzie N jest liczbą naturalną. N N*ln(2) = e Nasunął Ci się pierwszy pomysł: skorzystanie z naszegok znakomitego algorytmu z ćwiczenia 1.5. Wszak 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 x i ln(x)). Ponieważ komputer się na funkcjach, które działają na liczbach rzeczywistych (e 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 N 2 = (2 jeżeli N jest parzyste 2 N/2 ) (cid:1)N/2/(cid:2) ) 2*(2 2 jeżeli N jest nieparzyste (jako (cid:1)N/2(cid: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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.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 sikostry. 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 1 2 3 4 10 11 12 20 30 40 60 100 1000 log 2(N) 0 1,00 1,58 2,00 3,32 3,46 3,58 4,32 4,91 5,32 5,91 6,64 9,97 2N 2 4 8 16 1024 2048 4096 1048576 1073741824 1099511627776 1152921504606846976 267650600228229401496703205376 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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc Rozdział 1. M Ćwiczenia z myślenia algorytmicznego 17 Ćwiczenie 1.10 Sprawdź, 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śwkię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ąk 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ągkle w tej samej klasie. Pomyślmy dalej. Dla każdego „dużego” (większego od N ) podzielnika N musi istnieć po- dzielnik „mały” (mniejszy od N ) – będący ilorazem N i tego „dużego”. Nie warto więc sprawdzać liczb większych od N – jeżeli przedtem nie znaleźliśmy podzielnika, dalej też go nie będzie. Czyli nie sprawdzamy liczb do N-1, tylko do N . Czy coś nam to dało? 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. M Co to jest algorytm? M Co to jest złożoność algorytmu? M Co to jest iteracja? M Co to jest rekurencja? M Dlaczego rekurencja nie zawsze jest dobra? M Na czym polega metoda „dziel i zwyciężaj”? M 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, sprkawdzania czy liczba jest pierwsza. C:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.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 poNszkodowanej w wypadku samochodowym. Ćwiczenie 1.13 Napisz algorytm liczenia pierwiastków równania kwadNratowego. Funkcja (dla przypomnienia) ma postać f(x)=ax liczenia pierwiastków – on w zasadzie jest już bardzo dobrym algorytmem. +bx+c. Przypomnij sobie szkolny sposób 2 Ćwiczenie 1.14 Przeanalizuj problem obliczania wartości wielomianu. n-1 + an-1x n Wielomian ma następującą postać: w(x) = anx + ... + a1x + a0. Porównaj metodę naj- bardziej oczywistą (mnożenie i dodawanie „po kolei”) z algorytmem opartym na schemacie + an-1)x Hornera, który mówi, że wielomian można przekształcić do postaci: w(x) = (...(anx 3 + ... + a1)x + a0. Aby to nieco rozjaśnić: wielomian trzeciego stopnia: w3(x) = a3x + a2x + a1x + a0 można przekształcić do postaci: w(x) = ((a3x + a2)x+ a1)x + a0 – sprawdź, ż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? 2 Ćwiczenie 1.15 Przeanalizuj grę w zgadywanie liczby. Pamiętasz grę: zgadnij liczbę z zakresu 1-1000? Zgadujący podaje odpowiedź, 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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc Rozdział 1. M Ćwiczenia z myślenia algorytmicznego 19 Ćwiczenie 1.16 Sprawdź, czy punkt X leży wewnątrz, czy na zewnątrz trNó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. kPodaj 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śliskz, że da się znaleźć rozwiązanie o lepszej złożoności? Ćwiczenie 1.18 Rozważ algorytmy przeszukiwania ciągu liczb w celu znNalezienia maksimum. Masz do dyspozycji nieuporządkowany skończony ciąg liczb i zadanie, aby znaleźć w nim największą liczbę. Przemyśl dwie metody: 1. 2. 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 ckiągu będziesz znał odpowiedź. 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). Sprawdź, czy to prawda. Zrób to na kilku przykładach. Który algorytm jest lepszy? Dlaczego wynik jest taki zaskakujący? C:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc 19 20 Ćwiczenie 1.19 Przyjrzyj się funkcji Ackermanna. Turbo Pascal – ćwiczenia praktyczne n+1 jeżeli m=0 A (m, n) = A (m-1, n) jeżeli m 0, n=0 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 rekurencyjkny 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: 1 2 3 5 2 3 4 7 3 4 5 9 4 5 6 5 6 7 6 7 8 7 8 9 8 9 10 9 10 11 0 1 2 3 5 m. 0 1 2 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:AndrzejPDFTurboPascal - ćwiczenia praktyczne1.doc
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Turbo Pascal. Ćwiczenia praktyczne
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: