Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00268 005089 15197117 na godz. na dobę w sumie
Pascal. Ćwiczenia praktyczne. Wydanie III - książka
Pascal. Ćwiczenia praktyczne. Wydanie III - książka
Autor: Liczba stron: 208
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-2833-9 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> turbo pascal - programowanie
Porównaj ceny (książka, ebook, audiobook).

Język Pascal - prostszy, niż przypuszczasz!

Choć popularny Turbo Pascal powstał niemal trzy dekady temu, a historia samego Pascala liczy sobie już ponad czterdzieści lat, nadal jest on jednym z najpopularniejszych języków programowania strukturalnego. Nie tylko dlatego, że wiele napisanych w nim programów działa po dziś dzień i w dalszym ciągu wymaga konserwacji, a bardzo popularne środowisko Delphi wykorzystuje pewną jego odmianę. Głównym powodem jest jego wartość edukacyjna - prosta i czytelna składnia Pascala, niewielki zestaw słów kluczowych i spore możliwości czynią z niego doskonałą platformę nauki dla początkujących programistów. Opanowanie tego języka znakomicie ułatwia poznawanie innych języków oraz skutecznie uczy rozwiązywania problemów algorytmicznych, o czym najlepiej może świadczyć fakt, że język ten nadal wykorzystywany jest w procesie kształcenia przyszłych informatyków na wielu polskich uczelniach.

'Pascal. Ćwiczenia praktyczne. Wydanie III' to kolejne wydanie najpopularniejszej w Polsce książki o Pascalu, sprawdzonej i wykorzystywanej przez wykładowców, studentów, nauczycieli informatyki oraz ich uczniów. Znajdziesz tu zbiór ćwiczeń, dzięki którym poznasz zasady programowania w tym języku i używane w nim struktury danych. Nauczysz się rozwiązywać zadania programistyczne za pomocą algorytmów i dowiesz się, z jakich elementów składa się każdy program w Pascalu. Wykonując kolejne ćwiczenia, poznasz instrukcje tego języka, opracujesz własne procedury i funkcje, utworzysz nowe typy danych oraz dowiesz się, jak kompilować i uruchamiać swoje programy. Przede wszystkim zaś nauczysz się myśleć i działać jak prawdziwy informatyk. A wtedy kariera profesjonalnego programisty stanie przed Tobą otworem!

Poznaj najlepsze metody rozwiązywania problemów programistycznych

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje naruszenie praw autorskich niniejszej publikacji. Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich właścicieli. Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Redaktor prowadzący: Michał Mrowiec Redakcja merytoryczna: Marek Tłuczek Projekt okładki: Maciek Pasek Fotografia na okładce została wykorzystana za zgodą Shutterstock.com Wydawnictwo HELION ul. Kościuszki 1c, 44-100 GLIWICE tel. 32 231 22 19, 32 230 98 63 e-mail: helion@helion.pl WWW: http://helion.pl (księgarnia internetowa, katalog książek) Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie?cwtp3 Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. Kody źródłowe wybranych przykładów dostępne są pod adresem: ftp://ftp.helion.pl/przyklady/cwtp3.zip ISBN: 978-83-246-2833-9 Copyright © Helion 2012 Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Spis treĂci WstÚp Rozdziaï 1. mwiczenia z myĂlenia algorytmicznego 1.1. Na dobry poczÈtek — jednak prosty program 1.2. WróÊmy do metod 1.3. Co powinieneĂ zapamiÚtaÊ z tego cyklu Êwiczeñ Rozdziaï 2. Schematy blokowe 2.1. Podstawowe informacje i proste Êwiczenia 2.2. Co powinieneĂ zapamiÚtaÊ z tego cyklu Êwiczeñ 2.3. mwiczenia do samodzielnego rozwiÈzania Rozdziaï 3. Podstawy Pascala 3.1. Krótki kurs obsïugi Ărodowiska zintegrowanego 3.2. Struktura programu w Pascalu 3.3. Instrukcje wyjĂcia (Write i Writeln) 3.4. Staïe i zmienne najczÚĂciej stosowane 3.5. Predefiniowane funkcje 3.6. Instrukcje wejĂcia (Read i Readln) 3.7. Instrukcja warunkowa 3.8. PÚtla for 3.9. Inne rodzaje pÚtli 3.10. Funkcje i procedury 3.11. Co powinieneĂ zapamiÚtaÊ z tego cyklu Êwiczeñ 3.12. mwiczenia do samodzielnego rozwiÈzania 5 9 9 11 23 27 27 34 34 37 38 42 43 49 57 60 63 69 80 87 101 102 4 Rozdziaï 4. Pascal • mwiczenia praktyczne Zagadnienia trudniejsze 4.1. Tablice 4.2. Definiowanie wïasnych typów 4.3. Moduïy standardowe 4.4. Instrukcja wyboru (case) 4.5. Zbiory 4.6. Typ rekordowy 4.7. Obsïuga plików 4.8. Tablice dynamiczne 4.9. Wskaěniki 4.10. Tryb graficzny 4.11. Co powinieneĂ zapamiÚtaÊ z tego cyklu Êwiczeñ 4.12. mwiczenia do samodzielnego rozwiÈzania 109 109 117 126 141 145 151 157 168 171 190 198 199 1 mwiczenia z myĂlenia algorytmicznego Pewnie oczekujesz wstÚpu do Pascala, wyjaĂnienia, czym jest, programu-Êwiczenia pozwalajÈcego wypisaÊ coĂ na ekranie, opisu budowy programów albo informacji o obsïudze samego programu. Tymczasem w najbliĝszym czasie nie bÚdziemy siÚ zajmo- waÊ Pascalem. Zajmiemy siÚ czymĂ, co jest trzonem programowania, czyli algorytmami. Aby jednak nie zaczynaÊ caïkiem na sucho, pierw- sze Êwiczenie niech bÚdzie dziaïajÈcym programem. Nie bÚdziemy siÚ na razie wgïÚbiaÊ w jego budowÚ. Spróbujmy go jedynie wpisaÊ, uruchomiÊ i zobaczyÊ efekt jego dziaïania. 1.1. Na dobry poczÈtek — jednak prosty program m W I C Z E N I E 1.1 Pierwszy program Napisz i uruchom program, który przywita CiÚ Twoim imieniem. Uruchom program Free Pascal, wpisujÈc z linii poleceñ DOS komen- dÚ fp. Z menu File wybierz New (lub wciĂnij kombinacjÚ klawiszy Alt+F, a nastÚpnie klawisz N). W otwarte okienko edycyjne wpisz po- niĝszy program: 10 Pascal • mwiczenia praktyczne program cw1_1; { Program wypisuje powitanie osoby, ktora } { wlasciwie wpisze swoje imie w odpowiednie miejsce. } { Katalog r1_01 : 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 spowodo- waÊ kïopoty z uruchomieniem. Nawet kropka na koñcu jest istotna! Jedyna zmiana, jakÈ moĝesz wprowadziÊ, to zmiana imienia Andrzej na wïasne. Nie musisz teĝ koniecznie wpisywaÊ tekstów w nawiasach klamrowych. Tak w Pascalu oznaczane sÈ komentarze. Nie majÈ one wpïywu na dziaïanie programu, ale majÈ kolosalne znaczenie w przy- padku, kiedy program trzeba poprawiÊ albo wyjaĂniÊ komuĂ jego struk- turÚ. Mimo ĝe komentarzy wpisywaÊ nie musisz, zrób to, aby od po- czÈ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Ú nietrudno domyĂliÊ, zaowoco- waïo to tysiÈcami wierszy nieopisanego tekstu w Turbo Pascalu, który nigdy juĝ nikomu siÚ do niczego nie przyda. Zrozumienie, w jaki spo- só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. Nadszedï moment uruchomienia. WciĂnij klawisze Ctrl+F9 (jest to od- powiednik wybrania z menu Run polecenia Run albo wciĂniÚcia kom- binacji klawiszy Alt+R i ponownie R). Jeĝeli przy wpisywaniu progra- mu 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 oraz Free Pascal wyniki dziaïania programów ukazujÈ na specjalnym, przeznaczonym do tego celu ekranie (ang. user screen), który na razie jest niewidoczny. Aby przeïÈczyÊ siÚ do tego ekranu, naleĝy wcisnÈÊ klawisze Alt+F5. Powrót nastÚpuje po wci- ĂniÚciu dowolnego klawisza. PowinieneĂ ujrzeÊ na ekranie wynik podobny do poniĝszego: Rozdziaï 1. • mwiczenia z myĂlenia algorytmicznego 11 Free Pascal IDE Version 1.0.12 [2011/04/23] Compiler Version 2.4.4 GDB Version GDB 7.2 Using configuration files from: C: urbo_pascal Running “C: urbo_pascalprogram.exe” Witaj, Andrzej! Na koniec trzeba wyjĂÊ z Free Pascala. WciĂnij kombinacjÚ Alt+X (co odpowiada wybraniu z menu File polecenia Exit). Na pytanie, czy za- pisaÊ zmiany, odpowiedz przeczÈco. 1.2. WróÊmy do metod No wïaĂnie. PrzekonaïeĂ siÚ, ĝe komputer do spóïki z Pascalem potrafiÈ zrozumieÊ to, co masz im do powiedzenia, pora wiÚc… zajÈÊ siÚ teoriÈ. Tak powinieneĂ robiÊ zawsze, kiedy przyjdzie Ci rozwiÈzaÊ jakiĂ pro- blem za pomocÈ komputera. Warto siÈĂÊ z kartkÈ papieru i zastanowiÊ siÚ nad istotÈ zagadnienia. Kaĝda minuta poĂwiÚcona na analizÚ pro- blemu moĝe zaowocowaÊ oszczÚdnoĂciÈ godzin podczas pisania ko- du… Najwaĝniejsze jest dobrze zrozumieÊ problem i wymyĂliÊ algo- rytm jego rozwiÈzania. No wïaĂnie. Co to sïowo 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. Oczy- wiĂcie nie jest to tylko pojÚcie informatyczne — równie dobrze stosuje siÚ je w wielu dziedzinach ĝycia codziennego (jak choÊby w gotowa- niu). Tak samo jak moĝna myĂleÊ o przepisie na ugotowanie makaro- nu, moĝna rozwaĝaÊ algorytm jego gotowania. RozwaĝajÈc algorytm rozwiÈzania problemu informatycznego, naleĝy mieÊ na uwadze: T dane, które mogÈ byÊ pomocne do jego rozwiÈzania — wraz ze sposobem ich przechowania, czyli strukturÈ danych; T wynik, który chcemy uzyskaÊ. GdzieĂ w tle rozwaĝamy teĝ czas, który mamy na uzyskanie wyniku z danych. OczywiĂcie tak naprawdÚ myĂlimy o dwóch czasach: jak szybko dany program trzeba napisaÊ i jak szybko musi on dziaïaÊ. ’a- two jest szybko napisaÊ program, który dziaïa wolno, jeszcze ïatwiej napisaÊ powoli taki, który dziaïa jak ĝóïw. PrawdziwÈ sztukÈ jest szyb- ko napisaÊ coĂ, co pracuje sprawnie. Naleĝy jednak mieÊ na uwadze, ĝe zwykle program (bÈdě teĝ jego czÚĂÊ) jest pisany raz, a wykorzysty- wany wiele razy, wiÚc o ile nie grozi to zawaleniem terminów, warto poĂwiÚciÊ czas na udoskonalenie algorytmu. 12 Pascal • mwiczenia praktyczne A zatem rozwaĝajÈc dane, które masz do dyspozycji, oraz majÈc na uwadze czas, musisz okreĂliÊ, w jaki sposób uzyskaÊ jak najlepszy wynik. Inaczej mówiÈc, musisz okreĂliÊ dziaïania, których podjÚcie jest konieczne do uzyskania wyniku, oraz ich wïaĂciwÈ kolejnoĂÊ. m W I C Z E N I E 1.2 Algorytm gotowania makaronu 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. Przyj- mujÚ, ĝe mam makaron spaghetti jakoĂci pozwalajÈcej uzyskaÊ zado- walajÈcy mnie wynik, sól, wodÚ, garnek, cedzak, minutnik i kuchniÚ. Makaron proponujÚ ugotowaÊ tak: 1. ZagotowaÊ w garnku wodÚ. 2. Do gotujÈcej siÚ wody wïoĝyÊ makaron, tak aby byï w niej zanurzony. 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 zaprojektowaÊ jakiĂ system doradzajÈcy, czy iloĂÊ soli jest wystarczajÈca; poniewaĝ chcemy jednak stworzyÊ algorytm prosty i dokïadny, przyjmijmy mojÈ normÚ — ¾ ïyĝki soli kuchennej na 5 litrów wody). 4. GotowaÊ okoïo 8 minut, od czasu do czasu mieszajÈc. 5. Zagotowany makaron odcedziÊ, uĝywajÈc cedzaka. 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Ă sosem, 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 niezwykle waĝna jest kolejnoĂÊ wykonania opisanych czynnoĂci. Makaron posolony juĝ na talerzu (po punkcie 7. algorytmu) smako- waïby duĝo gorzej (choÊ muszÚ szczerze przyznaÊ, ĝe zdarzyïa mi siÚ Rozdziaï 1. • mwiczenia z myĂlenia algorytmicznego 13 taka wpadka). Polewanie zimnÈ wodÈ makaronu przed wïoĝeniem go do garnka (a wiÚc przed punktem 1.) na pewno nie zapobiegnie jego sklejaniu. 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ĝy- my 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). m W I C Z E N I E 1.3 Algorytm znajdowania NWD Znajdě najwiÚkszy wspólny dzielnik (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 razie zatrzyma siÚ na liczbie 1, która na pewno jest dzielnikiem A i B). W najgorszym przypadku bÚdzie musiaï wykonaÊ 2B dzieleñ i B odej- mowañ. To zadanie na pewno jednak da siÚ i naleĝy rozwiÈzaÊ lepiej. Drugi algorytm nosi nazwÚ Euklidesa. Polega na powtarzaniu cyklu na- stÚpujÈcych operacji: podziaïu wiÚkszej z liczb przez mniejszÈ (z resz- tÈ) i dalszej dziaïalnoĂci prowadzÈcej do wybrania dzielnika i znale- zionej reszty. Operacja jest powtarzana tak dïugo, aĝ resztÈ bÚdzie 0. Szukanym najwiÚkszym wspólnym dzielnikiem jest dzielnik ostatniej operacji dzielenia. Oto przykïad (szukamy najwiÚkszego dzielnika liczb 12 i 32): 32 / 12 = 2 reszty 8 12 / 8 = 1 reszty 4 8 / 4 = 2 reszty 0 Szukanym najwiÚkszym wspólnym dzielnikiem 12 i 32 jest 4. Jak wi- daÊ, zamiast sprawdzania 9 liczb (12, 11, 10, 9, 8, 7, 6, 5, 4), z wykona- niem dwóch dzieleñ dla kaĝdej z nich, jak miaïoby to miejsce w przy- padku rozwiÈzania siïowego, wystarczyïy nam tylko trzy dzielenia. 14 Pascal • mwiczenia praktyczne Bardzo podoba mi siÚ trzeci algorytm, bÚdÈcy modyfikacjÈ algoryt- mu Euklidesa, ale niewymagajÈ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 po- szukiwañ. 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 odejmo- wania, a nie dzielenia. Koszt operacji dodawania 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 szukanie reszty z dzielenia liczb A i B poprzez dzielenie zastÈpiono wieloma odejmowaniami. m W I C Z E N I E 1.4 Algorytm znajdowania NWW Znajdě najmniejszÈ wspólnÈ wielokrotnoĂÊ (NWW) liczb naturalnych A i B. Czasem najlepsze sÈ rozwiÈzania najprostsze. Od razu moĝemy siÚ do- myĂliÊ, ĝe „siïowe” rozwiÈzania (na przykïad sprawdzanie podziel- noĂci przez A i B liczb od A·B w dóï aĝ do wiÚkszej z nich i przyjÚcie jako wyniku najmniejszej, której obie sÈ dzielnikami), choÊ istniejÈ, nie sÈ tym, czego szukamy. A wystarczy przypomnieÊ sobie fakt z ma- tematyki z zakresu szkoïy podstawowej: NWW , BA ˜ BA NWD BA , i juĝ wiadomo, jak problem rozwiÈzaÊ, wykorzystujÈc algorytm, któ- ry znamy. Usilne (i czÚsto uwieñczone sukcesem) próby rozwiÈzania problemu poprzez sprowadzenie go do takiego, który juĝ zostaï roz- wiÈzany, to jedna z cech programistów. Jak zobaczysz w nastÚpnych Rozdziaï 1. • mwiczenia z myĂlenia algorytmicznego 15 Êwiczeniach, czÚsto stosujÈc róĝne techniki, programiĂci sÈ nawet w stanie sprowadziÊ rozwiÈzanie zadania do… rozwiÈzania tego sa- mego zadania dla innych (ïatwiejszych) danych, w nadziei, ĝe dane w koñcu stanÈ siÚ tak proste, iĝ bÚdzie moĝna podaÊ wynik „z gïowy”. I to dziaïa! PodstawÈ tak sprawnego znalezienia rozwiÈzania tego Êwiczenia oka- zaïa siÚ elementarna znajomoĂÊ matematyki. Jak juĝ pisaïem, matema- tyka doĂÊ silnie splata siÚ z programowaniem i dlatego dla wïasnego dobra przed przystÈpieniem do „klepania” w klawiaturÚ warto przy- pomnieÊ sobie kilka podstawowych zaleĝnoĂci i wzorów. Jako dowód na to zapraszam do rozwiÈzania kolejnego Êwiczenia. m W I C Z E N I E 1.5 Algorytm potÚgowania Znajdě wynik dziaïania AB. WyglÈda na to, ĝe twórcy Pascala o czymĂ zapomnieli albo uznali za niepotrzebne, liczÈc na znajomoĂÊ matematyki wĂród programistów (z drugiej strony, wbudowanych jest wiele mniej przydatnych funk- cji). 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 skorzy- staÊ z wïasnoĂci logarytmu i funkcji ex. Naleĝy przeprowadziÊ nastÚpujÈce rozumowanie: ln § ¨© BA · ¸¹ B A e ln ˜ B A e poniewaĝ x = eln(x) oraz ln(xy) = y·ln(x). Obie funkcje (ex i ln(x)) sÈ w Pascalu dostÚpne, wiÚc dziÚki temu problem moĝemy uznaÊ za roz- wiÈ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 wywoïaïo koniecznoĂÊ przypomnienia sobie logarytmów. Warto pa- miÚtaÊ, ĝe rozwiÈzanie to bÚdzie skuteczne jedynie dla dodatnich war- toĂci podstawy potÚgi i nie znajdziemy w ten sposób istniejÈcego wy- niku dziaïania (–4)4. 16 m W I C Z E N I E 1.6 Pascal • mwiczenia praktyczne Algorytm obliczania silni Znajdě silniÚ danej liczby (N!). Jak wiadomo z lekcji matematyki, silnia liczby jest iloczynem wszyst- kich liczb naturalnych mniejszych od niej lub jej równych, czyli: N 21! ˜ ˜ ... ˜ N N 1 ˜ Juĝ bezpoĂrednio z tej definicji wynika jedno (caïkiem poprawne) roz- wiÈzanie tego problemu. Naleĝy po prostu uzyskaÊ wynik mnoĝenia przez siebie wszystkich liczb naturalnych mniejszych od lub równych danej. Ten algorytm nosi nazwÚ iteracyjnego i zostanie dokïadnie po- kazany w Êwiczeniu 3.37. Zastanów siÚ jednak jeszcze nad drugim algorytmem. Silnia posiada teĝ drugÈ definicjÚ (oczywiĂcie równowaĝnÈ poprzedniej): ! N ­ ® ¯ 1 NN ˜ !1  gdy gdy ! 0 0 N N W tej definicji jest coĂ dziwnego. 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 — to zupeïnie wystarczy. Spróbuj na kartce, zgodnie z tÈ definicjÈ, policzyÊ 5!. Po- winieneĂ 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Ăle- dzenie tego przykïadu pozwoli na zrozumienie takiego sposobu defi- niowania 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) argu- Rozdziaï 1. • mwiczenia z myĂlenia algorytmicznego 17 mentami. A w przypadku programowania — na wykorzystaniu funk- cji lub procedury przez niÈ samÈ. m W I C Z E N I E 1.7 Rekurencyjne mnoĝenie liczb 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Ú — pozwoli Ci siÚ bliĝej zapoznaÊ z rekurencjÈ. ˜ BA ­ ® ¯ oczywiĂcie moĝna teĝ: A ˜ BAA  @ 1  gdy gdy ! 1 1 B B ˜ BA ­ ® ¯ A B 1 ˜ @ BB  gdy gdy ! 1 1 A A Wiele podejmowanych dziaïañ (zarówno matematycznych, jak i w ĝy- ciu codziennym) podlega zasadzie rekurencji. Kilka Êwiczeñ dodatko- wych pod koniec rozdziaïu pozwoli jeszcze lepiej siÚ z niÈ zapoznaÊ. m W I C Z E N I E 1.8 Obliczanie ciÈgu Fibonacciego PrzemyĂl sensownoĂÊ rozwiÈzania rekurencyjnego problemu N-tego wyrazu ciÈgu Fibonacciego. To Êwiczenie to ilustracja swoistej „puïapki rekurencji”, w którÈ ïa- two moĝe wpaĂÊ nieuwaĝny programista. Wiele osób po poznaniu tej techniki stosuje jÈ, kiedy tylko siÚ 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È definicjÈ re- kurencyjnÈ: NF ­ ° ® ° ¯ NF 0 1 1  NF  2 gdy gdy gdy ! 0 1 1 N N N 18 Pascal • mwiczenia praktyczne Wydaje siÚ, ĝe nasz problem rozwiÈzuje juĝ sama definicja. Wystar- czy wykorzystaÊ rekurencjÚ. Spróbujmy wiÚc na kartce, zgodnie z de- finicjÈ, 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 F(5) = F(4) + F(3) = F(3) + F(2) + F(3) = 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) = …to liczenie nie idzie chyba w dobrym kierunku… F(50) = Czy sÈ jacyĂ odwaĝni? CoĂ jest nie tak — algorytm liczÈcy F(8) kaĝe nam w pewnym momen- cie 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ñ, ponie- waĝ wystÚpujÈ one w róĝnych wywoïaniach rekurencyjnych i wza- jemnie o swoich wynikach nic nie wiedzÈ. Podobnie nie da siÚ sko- rzystaÊ z wyliczonych juĝ, poprzednich wartoĂci, poniewaĝ nigdzie nie sÈ przechowywane. To jest bardzo zïy sposób rozwiÈzania tego problemu. Mimo ĝ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 ostat- nie 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 po- przednich dwóch. Czas pracy rozwiÈzania iteracyjnego jest wprost proporcjonalny do wartoĂci N. A od czego zaleĝy ten czas w przypad- ku 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: Rozdziaï 1. • mwiczenia z myĂlenia algorytmicznego 19 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 1267650600228229401496703205376 ok. 1*10301 Jak widaÊ, wraz ze wzrostem wielkoĂci danej czas rozwiÈzywania za- dania bÚdzie rósï w sposób niesamowity. W Êwiczeniu 3.61 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), jednak przy ich rozwiÈzywaniu stosuje siÚ inne, przybliĝone, lecz szybciej dziaïajÈce algorytmy. W przeciwnym razie nawet dla problemu 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, w któ- rych 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 jednak jeszcze jedna klasa, którÈ informatycy lubiÈ najbardziej. Po- znasz jÈ w nastÚpnym Êwiczeniu. A jako ostatniÈ informacjÚ z tego Êwiczenia zapamiÚtaj, ĝe kaĝdy al- gorytm rekurencyjny da siÚ przeksztaïciÊ do postaci iteracyjnej. Cza- sami tak ïatwo, jak silniÚ czy ciÈg Fibonacciego, czasem trudniej lub bardzo trudno (swego czasu zamieniaïem na postaÊ iteracyjnÈ algo- rytm, który w postaci rekurencyjnej miaï kilka wierszy, postaÊ itera- cyjna zaĂ miaïa ich wielokrotnie wiÚcej). Prawie zawsze stracimy na 20 Pascal • mwiczenia praktyczne czytelnoĂci. Zwykle zyskamy jednak na czasie pracy i obciÈĝeniu kom- putera. Jeĝeli wiÚc przeksztaïcenie do postaci iteracyjnej jest proste i oczywiste, naleĝy to zrobiÊ — ale nie za wszelkÈ cenÚ. m W I C Z E N I E 1.9 Algorytm podnoszenia 2 do potÚgi naturalnej N , gdzie N jest liczbÈ naturalnÈ. Znajdě metodÚ obliczania wyraĝenia 2 NasunÈï Ci siÚ pierwszy pomysï: skorzystanie z naszego znakomitego algorytmu z Êwiczenia 1.5. Wszak 2N = eN*ln(2), wiÚc z szybkim wyli- czeniem 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 rze- czywistych (ex i ln(x)). Poniewaĝ komputer reprezentuje liczby rzeczy- wiste z pewnym przybliĝeniem, nie dostaniemy niestety dokïadnego wyniku — liczby naturalnej. Dla odpowiednio duĝego N wynik za- cznie byÊ obarczony bïÚdem. A my tymczasem potrzebujemy wyniku bÚdÈcego liczbÈ naturalnÈ. PomyĂlmy wiÚc nad innym 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 pomnoĝyÊ N razy — 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 2 22 N 22 ˜ parzyste nieparzyst e N jest N jest N gdy gdy gdy 2 N 0 ­ ° ® ° ¯ 22 N (jako N/2 rozumiemy caïkowitÈ czÚĂÊ dzielenia N przez 2). Jako drobne Êwiczenie matematyczne proponujÚ sprawdziÊ (a moĝe nawet udo- wodniÊ?), czy jest to prawda. Jeĝeli ktoĂ chce siÚ zmierzyÊ z dowo- dem, 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. Rozdziaï 1. • mwiczenia z myĂlenia algorytmicznego 21 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 gdy szukamy potÚgi 32, za drugim razem bÚdziemy juĝ szukaÊ 16, za trzecim 8, potem 4, 2, 1 i zerowej. To nie jest w ĝaden sposób liniowe. To jest o wiele lepsze! Jak nazwaÊ zïoĝonoĂÊ tego algorytmu? 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È naj- bardziej. Tabelka, którÈ pokazaliĂmy powyĝej, byïaby niepeïna bez danych o zïoĝonoĂci logarytmicznej. Powtórzmy jÈ zatem: N 1 2 3 4 10 11 12 20 30 40 60 100 1000 log2(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 1267650600228229401496703205376 ok. 1*10301 Czy widzisz róĝnicÚ? Dla danej o wartoĂci 1000 algorytm logarytmicz- ny musi wykonaÊ tylko 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 mniej- szych tego samego typu, ale do mniejszych przynajmniej dwukrotnie, nazwano (moim zdaniem sïusznie) dziel i zwyciÚĝaj. Zawsze, gdy uda Ci siÚ podzieliÊ w podobny sposób problem na mniejsze, masz szan- sÚ na uzyskanie dobrego, logarytmicznego algorytmu. 22 m W I C Z E N I E 1.10 Pascal • mwiczenia praktyczne Algorytm okreĂlania liczb pierwszych Sprawdě, czy liczba N jest liczbÈ pierwszÈ. Dla przypomnienia: liczba pierwsza to taka, która ma tylko dwa róĝ- ne, naturalne dzielniki: 1 i samÈ siebie. Zadanie wbrew pozorom nie jest tylko sztukÈ dla sztuki. Funkcja spraw- dzajÈca, czy zadana liczba jest pierwsza, czy nie (i znajdujÈca jej dziel- niki) 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 kon- kretnie w ïamaniu szyfrów. Warto wiÚc poĂwiÚciÊ chwilkÚ na rozwiÈ- zanie tego zadania. 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 przeciw- nym razie jest. Pierwszy pomysï nie jest zïy. Funkcja na pewno dziaïa i ma zïoĝonoĂÊ liniowÈ. TroszkÚ da siÚ jÈ 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, nadal 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 N ) dzielnika N musi istnieÊ 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 dzielnika, 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ĝo- noĂciÈ? Co prawda nie jest liniowa, ale wykïadnicza (tylko z lepszym niĝ liniowa wykïadnikiem). Proste pytanie: z jakim wykïadnikiem zïo- ĝonoĂÊ wielomianowa jest liniowa, a z jakim jest taka, jakÈ uzyskali- Ămy? Jeĝeli podaïeĂ odpowiednio wartoĂci 1 i ½, to udzieliïeĂ popraw- nej odpowiedzi. Rozdziaï 1. • mwiczenia z myĂlenia algorytmicznego 23 1.3. Co powinieneĂ zapamiÚtaÊ z tego cyklu Êwiczeñ T Co to jest algorytm? T Co to jest zïoĝonoĂÊ algorytmu? T Co to jest iteracja? T Co to jest rekurencja? T Dlaczego rekurencja nie zawsze jest dobra? T Na czym polega metoda dziel i zwyciÚĝaj? T 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? 1.4. mwiczenia do samodzielnego rozwiÈzania m W I C Z E N I E 1.11 Gotowanie potraw 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ñ. m W I C Z E N I E 1.12 Udzielanie pierwszej pomocy Podaj algorytm udzielania pierwszej pomocy osobie poszkodowanej w wypadku samochodowym. m W I C Z E N I E 1.13 Obliczanie pierwiastków 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. 24 m W I C Z E N I E 1.14 Pascal • mwiczenia praktyczne Obliczanie wartoĂci wielomianu Przeanalizuj problem obliczania wartoĂci wielomianu. Wielomian ma nastÚpujÈcÈ postaÊ: w(x) = anxn + an-1xn-1 + … + a1x + a0. Porównaj metodÚ najbardziej 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 posta- ci: 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ĝo- noĂÊ 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? m W I C Z E N I E 1.15 Zgadywanie liczb 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ï”, trafienie trwaïoby dïugo. Moĝna jednak wymy- ĂliÊ bardzo sprawny algorytm zgadniÚcia liczby. Spróbuj go sformu- ïowaÊ. 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. m W I C Z E N I E 1.16 Poïoĝenie punktu wzglÚdem trójkÈta Sprawdě, 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 po- wstaïy poprzez poïÈczenie wierzchoïków trójkÈta z punktem, oraz kombinacje ich sum. Podaj algorytm sprawdzania. Rozdziaï 1. • mwiczenia z myĂlenia algorytmicznego 25 m W I C Z E N I E 1.17 Wieĝe Hanoi 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È pira- midÚ na jednym z nich. Naleĝy przenieĂÊ jÈ caïÈ na drugi stos zgod- nie 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 mniej- sze. 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 algo- rytm? Czy myĂlisz, ĝe da siÚ znaleěÊ rozwiÈzanie o lepszej zïoĝonoĂci? m W I C Z E N I E 1.18 Znajdowanie maksimum Rozwaĝ algorytmy przeszukiwania ciÈgu liczb w celu znalezienia maksimum. Masz do dyspozycji nieuporzÈdkowany skoñczony ciÈg liczb i zada- nie, aby znaleěÊ w nim najwiÚkszÈ liczbÚ. PrzemyĂl dwie metody: 1. Przesuwasz siÚ po kolejnych wyrazach ciÈgu i sprawdzasz, czy bieĝÈcy nie jest wiÚkszy od dotychczas znalezionego najwiÚkszego (który pamiÚtasz). Jeĝeli tak, to przyjmujesz, ĝe to on jest najwiÚkszy. Po dojĂciu do koñca ciÈgu bÚdziesz znaï odpowiedě. 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Úksze — najwiÚkszy element lewego podciÈgu czy najwiÚkszy element prawego podciÈgu. 26 Pascal • mwiczenia praktyczne Drugi algorytm jest typu dziel i zwyciÚĝaj i na pierwszy rzut oka wy- daje 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? m W I C Z E N I E 1.19 Analizowanie funkcji Ackermanna Przyjrzyj siÚ funkcji Ackermanna. , nmA ­ ° ® ° ¯ mA n mA ,1  1 ,1   n , nmA gdy gdy gdy m 0 m ,0 ! n 0 , ! nm 0 1  Ta niewinnie wyglÈdajÈca funkcja zdefiniowana rekurencyjnie to praw- dziwy koszmar. Spróbuj policzyÊ A (2, 3) bez pamiÚtania w czasie wy- liczania wartoĂci juĝ policzonych. A A (3, 3)? Czy odwaĝyïbyĂ siÚ po- liczyÊ A (4, 3)? Czy algorytm rekurencyjny zdaje tu egzamin? Spróbuj podejĂÊ do zadania w inny sposób. Zapisuj wyliczane wyni- ki 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 spo- sób moĝna spróbowaÊ zabraÊ siÚ do rozwiÈzania tego problemu ite- racyjnie.
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Pascal. Ćwiczenia praktyczne. Wydanie III
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ą: