Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00163 013867 11052122 na godz. na dobę w sumie
Algorytmy. Ćwiczenia - książka
Algorytmy. Ćwiczenia - książka
Autor: Liczba stron: 272
Wydawca: Helion Język publikacji: polski
ISBN: 83-246-2007-9 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> inne - programowanie
Porównaj ceny (książka, ebook, audiobook).

Poznaj algorytmy, a profesjonalne programowanie nie będzie miało przed Tobą tajemnic

W czasach ery informatycznej coraz większa liczba osób zainteresowana jest zdobyciem umiejętności programowania. Jednakże umiejętność ta wymaga zarówno rozległej i rzetelnej wiedzy, jak i doświadczenia. Podstawą owej wiedzy jest dobra znajomość algorytmów, która umożliwia przeprowadzanie kolejnych etapów programowania. Pozwala ona na przechodzenie od analizy i zdefiniowania problemu, poprzez testowanie i usuwanie błędów, aż do opracowania dokumentacji. Książka, którą trzymasz w rękach, pomoże Ci zrozumieć każdą z tych faz i nauczy Cię pisać własny kod.

'Algorytmy. Ćwiczenia' to niezbędny elementarz dla każdego przyszłego programisty. Dzięki temu podręcznikowi poznasz różne sposoby opisu algorytmów oraz ich klasyfikację. Dowiesz się, jaki wpływ ma zastosowanie określonej metody obliczeniowej na dokładność wyników końcowych, a także, na czym polega przetwarzanie danych w pętli programowej. Wykonując kolejne ćwiczenia, opatrzone szczegółowymi komentarzami i wskazówkami, nauczysz się pisać algorytmy, sporządzać wykresy i schematy blokowe oraz tworzyć kod programu. Książka jest doskonałym podręcznikiem dla studentów informatyki, jednak dzięki temu, że wszystkie informacje przedstawiono tu w jasny i klarowny sposób, może z niej korzystać każdy, kto chce rozpocząć samodzielne programowanie.

Poznaj algorytmy i zacznij myśleć jak programista!

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

Darmowy fragment publikacji:

Algorytmy. ˘wiczenia Autor: Bogdan Buczek ISBN: 978-83-246-2007-4 Format: A5, stron: 272 Poznaj algorytmy, a profesjonalne programowanie nie bŒdzie mia‡o przed Tob„ tajemnic (cid:149) Jak zaprojektowa(cid:230) rozwi„zanie problemu w formie algorytmu? (cid:149) Jak stosowa(cid:230) instrukcje iteracyjne? (cid:149) Jak przedstawi(cid:230) algorytm w postaci schematu blokowego? W czasach ery informatycznej coraz wiŒksza liczba os(cid:243)b zainteresowana jest zdobyciem umiejŒtno(cid:156)ci programowania. Jednak¿e umiejŒtno(cid:156)(cid:230) ta wymaga zar(cid:243)wno rozleg‡ej i rzetelnej wiedzy, jak i do(cid:156)wiadczenia. Podstaw„ owej wiedzy jest dobra znajomo(cid:156)(cid:230) algorytm(cid:243)w, kt(cid:243)ra umo¿liwia przeprowadzanie kolejnych etap(cid:243)w programowania. Pozwala ona na przechodzenie od analizy i zdefiniowania problemu, poprzez testowanie i usuwanie b‡Œd(cid:243)w, a¿ do opracowania dokumentacji. Ksi„¿ka, kt(cid:243)r„ trzymasz w rŒkach, pomo¿e Ci zrozumie(cid:230) ka¿d„ z tych faz i nauczy CiŒ pisa(cid:230) w‡asny kod. (cid:132)Algorytmy. ˘wiczenia(cid:148) to niezbŒdny elementarz dla ka¿dego przysz‡ego programisty. DziŒki temu podrŒcznikowi poznasz r(cid:243)¿ne sposoby opisu algorytm(cid:243)w oraz ich klasyfikacjŒ. Dowiesz siŒ, jaki wp‡yw ma zastosowanie okre(cid:156)lonej metody obliczeniowej na dok‡adno(cid:156)(cid:230) wynik(cid:243)w koæcowych, a tak¿e, na czym polega przetwarzanie danych w pŒtli programowej. Wykonuj„c kolejne (cid:230)wiczenia, opatrzone szczeg(cid:243)‡owymi komentarzami i wskaz(cid:243)wkami, nauczysz siŒ pisa(cid:230) algorytmy, sporz„dza(cid:230) wykresy i schematy blokowe oraz tworzy(cid:230) kod programu. Ksi„¿ka jest doskona‡ym podrŒcznikiem dla student(cid:243)w informatyki, jednak dziŒki temu, ¿e wszystkie informacje przedstawiono tu w jasny i klarowny spos(cid:243)b, mo¿e z niej korzysta(cid:230) ka¿dy, kto chce rozpocz„(cid:230) samodzielne programowanie. (cid:149) Sposoby opisu algorytm(cid:243)w (cid:149) Klasyfikacja algorytm(cid:243)w (cid:149) Algorytmy sekwencyjne (cid:149) Kodowanie algorytm(cid:243)w (cid:149) Algorytmy z rozga‡Œzieniami (cid:149) Przetwarzanie danych w pŒtli programowej (cid:149) Algorytmy iteracyjne (cid:149) Funkcja silnia (cid:149) Instrukcje iteracyjne w Turbo Pascal i Visual Basic (cid:149) Algorytmy rekurencyjne (cid:149) Schemat Kornera (cid:149) Pozycyjne systemy liczbowe (cid:149) Algorytmy sortowania danych Poznaj algorytmy i zacznij my(cid:156)le(cid:230) jak programista! Wydawnictwo Helion ul. Ko(cid:156)ciuszki 1c 44-100 Gliwice tel. 032 230 98 63 e-mail: helion@helion.pl Spis treĂci WstÚp Rozdziaï 1. NiezbÚdne informacje o algorytmach Czym jest algorytm? Ocena jakoĂci algorytmu Planowanie pracy Sposoby opisu algorytmów Klasyfikacja algorytmów Podsumowanie Rozdziaï 2. Algorytmy sekwencyjne. Kodowanie algorytmów Algorytm sekwencyjny Obliczanie wartoĂci funkcji Kodowanie algorytmów Liczymy koszt rozmowy telefonicznej Uwagi koñcowe mwiczenia do samodzielnego wykonania Rozdziaï 3. Algorytmy z rozgaïÚzieniami. Sterowanie przepïywem w algorytmie Algorytm z rozgaïÚzieniami Miejsce zerowe funkcji, rozwiÈzanie równania liniowego Obliczanie pierwiastków równania kwadratowego Uwagi koñcowe mwiczenia do samodzielnego wykonania 5 7 7 9 9 11 22 24 27 27 28 29 45 55 57 59 59 61 68 86 88 4 Algorytmy • mwiczenia Rozdziaï 4. Algorytmy iteracyjne. Przetwarzanie danych w pÚtli programowej Algorytm iteracyjny Rysowanie gwiazdek Co umoĝliwia iteracja? Uwagi koñcowe mwiczenia do samodzielnego wykonania Rozdziaï 5. Algorytmy rekurencyjne Algorytm rekurencyjny Funkcja silnia Obliczanie potÚgi liczby rzeczywistej Uwagi koñcowe mwiczenia do samodzielnego wykonania Rozdziaï 6. Schemat Hornera. Obliczanie wartoĂci wielomianu Schemat Hornera Uwagi koñcowe mwiczenia do samodzielnego wykonania Rozdziaï 7. Pozycyjne systemy liczbowe System liczbowy Obliczanie wartoĂci liczby zapisanej w dowolnym systemie pozycyjnym Przedstawianie liczb w dowolnym pozycyjnym systemie liczbowym Uwagi koñcowe mwiczenia do samodzielnego wykonania Rozdziaï 8. Algorytmy sortowania danych Sortowanie zbioru danych Metody sortowania zbioru danych Uwagi koñcowe mwiczenia do samodzielnego wykonania 91 91 94 102 110 111 115 115 116 127 134 137 139 139 165 167 169 169 174 194 214 216 217 217 220 265 266 5 Algorytmy rekurencyjne Algorytm rekurencyjny Rekurencja, zwana równieĝ rekursjÈ, jest technikÈ programowania, w której stosowany jest podprogram (funkcja lub procedura) wywo- ïujÈcy sam siebie albo wywoïujÈcy innÈ procedurÚ, która wywoïa podprogram pierwotny. W tym drugim przypadku mówimy o rekur- sji podwójnej lub skroĂnej. Kolejne wywoïania trwajÈ, aĝ do osiÈ- gniÚcia warunku zakoñczenia rekurencji. Jest nim oczekiwany wynik albo przekroczenie rozmiaru zbioru, na którym wykonywane sÈ obli- czenia. Liczba kolejnych wywoïañ rekursywnych nie ma znaczenia. CzÚsto jest wrÚcz niemoĝliwa do okreĂlenia przed rozpoczÚciem przetwarza- nia danych, nie zawsze bowiem da siÚ okreĂliÊ poziom zagïÚbienia w wywoïania. Wynik aktualnie realizowanego obliczenia rekurencyjnego zaleĝy od poprzedzajÈcego go powtórzenia. Kaĝde kolejne wywoïanie powo- duje zmniejszenie rozmiaru badanego zbioru (np. tablicy) o 1, dziÚki czemu problem zostaje rozbity na czÚĂci elementarne, które operujÈ na mniejszej liczbie danych — sÈ zatem mniej skomplikowane. Do- piero w momencie powrotu z wywoïañ wyznaczane sÈ wszystkie po- przednie wartoĂci. 116 Algorytmy • mwiczenia Rekurencja wokóï nas PostÚpowanie o charakterze rekurencyjnym trwale zwiÈzane jest z wie- loma czynnoĂciami zachodzÈcymi w otaczajÈcej nas rzeczywistoĂci, choÊ czÚsto nie zauwaĝamy tego lub nie jesteĂmy Ăwiadomi. Moĝna wskazaÊ wiele przykïadów czynnoĂci, które majÈ cechy rekur- sji, a sÈ wykonywane przez czïowieka, zwierzÚta albo zaprogramo- wane automaty. Chodzenie i bieganie, tañczenie, jedzenie, masowe toczenie na tokarce, zbieranie rozsypanych przedmiotów, mycie, zry- wanie owoców z drzewa itp. Równie czÚsto opisujemy sïownie procesy, stosujÈc jÚzyk typowy dla rekursji. InstruujÈc kogoĂ, jak naleĝy myÊ stos talerzy, mówimy: „Umyj talerz do czysta i myj dalej”. TïumaczÈc, jak uïoĝyÊ na póïce rozsypane na podïodze ksiÈĝki, powiemy: „PodnieĂ ksiÈĝkÚ, ustaw na póïce i podobnie ukïadaj kolejne”. Ten schemat postÚpowania jest przedstawiony graficznie na rysunku 5.1. W obu przykïadach czynnoĂÊ jest powtarzana. Róĝne sÈ jednak warunki zakoñczenia rekurencji. W pierwszym przykïadzie koniec powinien nastÈpiÊ, gdy talerze sÈ czyste, w drugim — gdy braknie ksiÈĝek do ustawiania. Rysunek 5.1. Model rekurencyjnego ukïadania ksiÈĝek na póïce Funkcja silnia Zgodnie z obietnicÈ danÈ w poprzednim rozdziale wracamy do funkcji silnia. Tym razem poznamy algorytm i rekurencyjne wersje programów wykonujÈcych stosowne obliczenia. m W I C Z E N I E 5.1 Algorytm rekurencyjnego obliczania n! Przedstaw w postaci schematu blokowego rekurencyjny algorytm ob- liczania silni n!, nN. Dokonaj analizy przepïywu w algorytmie dla n = 3. Rozdziaï 5. • Algorytmy rekurencyjne 117 RozwiÈzanie Dane: Liczba naturalna n wprowadzona przez uĝytkownika, równa ostatniemu wyrazowi iloczynu. Oczekiwany wynik: WartoĂÊ funkcji n!. Analiza problemu: Definicja silni n! liczby naturalnej n wystÈpiïa w poprzednim rozdziale w Êwiczeniu 4.4. Z definicji klasycznej n! = 1 · 2 · 3 · … · n wynika wïasnoĂÊ silni n! = n(n – 1)!, która pozwala okre- ĂliÊ tÚ funkcjÚ w postaci rekurencyjnej: ­ 1!0 ® n ! ¯ ˜ nn (  )!1 Obliczenie kolejnej wartoĂci n! nastÚpuje poprzez pomnoĝenie war- toĂci poprzedniej (n – 1)! przez nastÚpnÈ liczbÚ naturalnÈ n. Tak zde- finiowana rekurencja nazywana jest liniowÈ. Proces obliczeniowy powinien byÊ powtarzany, aĝ n osiÈgnie wartoĂÊ zadanÈ przez uĝytkownika. Na podstawie powyĝszego moĝna zapisaÊ w innej formie rekurencyjnÈ definicjÚ funkcji silnia: ­ ® ¯ a 0 a n 1 a  1 n ˜ n ,  Nn Algorytm przedstawiony na rysunku 5.2 skïada siÚ z dwóch czÚĂci: algorytmu (programu) gïównego i podprogramu realizujÈcego reku- rencyjne obliczanie funkcji silnia. Powyĝszy algorytm moĝna próbowaÊ scaliÊ, co pokazuje rysunek 5.3. W tej formie rekurencyjny algorytm obliczania silni wystÚpuje w lite- raturze najczÚĂciej. Niestety obarczony jest powaĝnym bïÚdem, jakim jest wczytywanie wartoĂci n przy kaĝdym kolejnym odwoïaniu reku- rencyjnym! Ten algorytm nie dziaïa prawidïowo. Analiza przepïywu w rekurencyjnym algorytmie obliczania silni W algorytmie z rysunku 5.2 stosowane sÈ dwie zmienne: n — liczba naturalna wprowadzona przez uĝytkownika (dana wsadowa), Silnia — wartoĂÊ funkcji silnia. Zapis z uĝyciem nawiasu: Silnia(argument) oznacza wartoĂÊ funkcji dla podanego argumentu, na przykïad Silnia(2) oznacza wartoĂÊ funkcji silnia dla n = 2. 118 Algorytmy • mwiczenia Rysunek 5.2. Rekurencyjny algorytm obliczania silni: a) program gïówny, b) podprogram rekurencyjnego obliczania silni Rysunek 5.3. BïÚdny algorytm obliczania silni bez uĝycia podprogramu Rozdziaï 5. • Algorytmy rekurencyjne 119 Algorytm gïówny z rysunku 5.2 a ma postaÊ schematu sekwencyjne- go, ïatwego do analizy i zrozumienia. Rozpoczyna siÚ od wczytania wartoĂci n. W kolejnym bloku wywoïywany jest podprogram Silnia, któremu jest przekazywana wczytana liczba naturalna. Po dokonaniu obliczeñ nastÚpuje powrót z podprogramu, a wynik jest wyĂwietlany na ekranie. Caïa zïoĝonoĂÊ obliczeniowa algorytmu przeniesiona jest do podprogramu przedstawionego na rysunku 5.2 b. Oto, jak dziaïa algorytm z rysunku 5.2 b dla n = 3: T Wraz z wywoïaniem funkcji Silnia jest do niej przekazywany argument n = 3. Poniewaĝ 3 jest róĝne od 0, wynikiem komparacji w bloku warunkowym jest odpowiedě negatywna. Zgodnie z formuïÈ podanÈ w klatce wykonawczej funkcja przyjmuje, ĝe jej wynikiem jest 3*Silnia(2). Jednak Silnia(2) nie jest znana, wiÚc nastÚpuje chwilowe wstrzymanie obliczania wyraĝenia 3*Silnia(2) oraz uruchomienie (wywoïanie) algorytmu dla n = 2. T Algorytm wywoïaï sam siebie z argumentem n = 2. Obliczana jest wartoĂÊ Silnia(2). Poniewaĝ 2 0, odpowiedziÈ w bloku warunkowym jest ponownie NIE. Podprogram uruchomi Silnia(1) i pomnoĝy jÈ przez dwa. WartoĂÊ wyniku czÈstkowego Silnia(1) jest nieznana, dlatego nastÚpuje wstrzymanie obliczania wartoĂci 2*Silnia(1) i ponowne odwoïanie do tej samej procedury rekurencyjnej z argumentem n = 1. T Dla przekazanego argumentu n = 1 nadal nie jest speïniony warunek n = 0 i odpowiedziÈ komparatora jest NIE. Silnia(1) odwoïa siÚ zatem do kolejnej instancji podprogramu rekurencyjnego — uruchomi Silnia(0) i pomnoĝy jÈ przez jeden. Poniewaĝ wartoĂÊ wyraĝenia Silnia(0) w tym odwoïaniu nie jest znana, obliczanie 1*Silnia(0) zostaje wstrzymane, a podprogram rekurencyjny wykonuje swÈ kolejnÈ bliěniaczÈ kopiÚ z argumentem równym zero. T Uruchomiony po raz kolejny podprogram wykonywany jest dla n = 0 i obliczana jest Silnia(0). Wynikiem porównania argumentu z zerem jest odpowiedě twierdzÈca. Wykonywany jest blok, w którym Silnia(0) przyjmuje wartoĂÊ 1. 120 Algorytmy • mwiczenia T Skoro znany jest wynik Silnia(0), moĝe juĝ nastÈpiÊ powrót z wywoïañ i obliczenie rzeczywistych wartoĂci iloczynów. Znana juĝ wartoĂÊ Silnia(0) = 1 zostaje przekazana do instancji jÈ wywoïujÈcej i wówczas Silnia(1) = 1 · 1 = 1, analogicznie Silnia(2) = 2 · 1 i przyjmuje wartoĂÊ dwa. CofajÈc siÚ ponownie, otrzymujemy Silnia(3) = 3 · 2, co daje wynik koñcowy równy 6, a to wïaĂnie 3! = 1 · 2 · 3. ZapamiÚtaj! Wywoïywanie kolejnych, bliěniaczych egzemplarzy podprogramu trwa dopóty, dopóki dla pewnego argumentu istnieje konkretny wynik czÈstkowy. W naszym algorytmie jest to wartoĂÊ argumentu n = 0. Poziomy i zagïÚbianie siÚ Kaĝde kolejne wywoïanie rekurencyjne odbywa siÚ dla argumentu o 1 mniejszego niĝ w poprzednim egzemplarzu procedury rekurencyjnej. Kaĝda wywoïana instancja podprogramu rekurencyjnego nazywana jest poziomem. Kolejne poziomy identyfikowane sÈ poprzez numer równy wartoĂci n. Poziom 0 oznacza elementarny egzemplarz procedu- ry rekurencyjnej, podczas wykonania której uzyskuje siÚ jednoznaczny wynik. Dopiero w chwili powrotu z wywoïañ obliczane sÈ wyniki rze- czywiste. Z poziomu 0 wynik czÈstkowy przekazywany jest na kolejne wyĝsze poziomy: poziom 1, poziom 2 itd. Wywoïywanie kolejnych rekurencyjnych egzemplarzy podprogramu nazywane jest zagïÚbianiem siÚ z poziomu n na poziom n – 1. Prze- kazywanie informacji (danych wsadowych i wyników czÈstkowych) odbywa siÚ za pomocÈ pamiÚci komputerowej zwanej stosem. WiÚcej na ten temat znajduje siÚ w uwagach koñcowych do tego rozdziaïu. Dziaïanie opisanego powyĝej algorytmu rekurencyjnego obliczajÈcego Silnia(3) przedstawia rysunek 5.4. Na rysunku 5.4 strzaïka pionowa oznacza zagïÚbianie siÚ algorytmu z poziomu wyĝszego na poziom niĝszy. Strzaïka ukoĂna oznacza prze- kazanie wyniku czÈstkowego z poziomu niĝszego na wyĝszy. Rozdziaï 5. • Algorytmy rekurencyjne 121 Rysunek 5.4. Drzewo wywoïañ rekurencyjnych i przekazywania wyniku czÈstkowego przy obliczaniu Silnia(3) m W I C Z E N I E 5.2 Algorytm rekurencyjnego obliczania n!. Program w Pascalu WykorzystujÈc algorytm z Êwiczenia 5.1, napisz rekurencyjny pro- gram w Turbo Pascalu, który obliczy i wyĂwietli wartoĂÊ funkcji n!, dla nN. RozwiÈzanie 1. Uruchom Turbo Pascala i utwórz nowy plik, wybierajÈc z paska menu polecenia File/New. 2. W oknie edycyjnym wpisz kod z listingu 5.1 albo wczytaj program z pliku cw5_2.pas znajdujÈcego siÚ w katalogu TP/Rozdz_05. Rezultat powinien byÊ identyczny jak na rysunku 5.5. Listing 5.1. Kod rekurencyjnego programu obliczajÈcego wartoĂÊ silni program cw5_2; { Program oblicza wartosc silni n!, } { stosujac funkcje zdefiniowana rekurencyjnie. } 122 Algorytmy • mwiczenia Rysunek 5.5. Okno edycyjne TP z kodem rekurencyjnego programu obliczania n! { Deklaracja zmiennej uzywanej w programie: } { n - ostatni wyraz iloczynu n! } var n : Integer; { -- Deklaracja i kod funkcji rekurencyjnej Silnia -- } function Silnia (n : Integer): Longint; begin if n = 0 then Silnia := 1 else Silnia := n * Silnia (n-1); end; { ----------------- Koniec funkcji Silnia ---- } Rozdziaï 5. • Algorytmy rekurencyjne 123 { ---- Program glowny ------------------------------- } begin writeln; writeln ( Rekurencyjne obliczanie wartosci n! ); writeln ( ------------------------------------- ); writeln; write ( n = ); readln (n); writeln ( Podaje wynik obliczen: ); writeln ( , n, ! = , Silnia(n)); readln; end. Symbole i nazwy uĝyte w programie sÈ identyczne jak w algorytmie z rysunku 5.2, dziÚki czemu jego zrozumienie nie powinno sprawiÊ kïopotu. W razie wÈtpliwoĂci proszÚ jeszcze raz przeanalizowaÊ przykïad poprzedni. Najistotniejszym fragmentem programu jest rekurencyjna funkcja uĝyt- kownika o nazwie Silnia. Blok instrukcji jÈ tworzÈcych funkcjÚ rozpo- czyna siÚ deklaracjÈ w postaci: function Silnia (n : Integer): Longint. Argument funkcji n jest liczbÈ caïkowitÈ wprowadzanÈ przez uĝyt- kownika, a jej wynik jest typu Longint. Funkcja wywoïywana jest w gïównym torze programu. Sïuĝy do tego komenda Silnia(n), umieszczona w linii organizujÈcej sposób wyĂwie- tlenia wyniku w postaci writeln (n, ‘! = ‘, Silnia(n)). Wywoïana funkcja dziaïa zgodnie z przepïywem na schemacie z ry- sunku 5.2 b. Obliczenia rekurencyjne zostaïy zrealizowane za pomo- cÈ bloku warunkowego. Jeĝeli n 0, to wykonywana jest instrukcja rekursyjna Silnia := n * Silnia (n-1). Kolejne odwoïania trwajÈ tak dïugo, aĝ argument funkcji zyska wartoĂÊ równÈ zero. Oznacza to, ĝe zostaï osiÈgniÚty poziom zerowy zagïÚbienia w podprogram. Uzy- skany na tym poziomie wynik czÈstkowy jest konkretnÈ liczbÈ i moĝe byÊ przekazany na poziom wyĝszy, gdzie nastÚpujÈ kolejne obliczenia. Na najwyĝszym poziomie n obliczana jest wartoĂÊ stanowiÈca wynik koñcowy wyĂwietlany na ekranie (rysunek 5.6). 124 Algorytmy • mwiczenia Rysunek 5.6. Efekt wykonania programu cw5_2 m W I C Z E N I E 5.3 Aplikacja rekurencyjnego obliczania silni w Excelu Napisz w Excelu aplikacjÚ obliczajÈcÈ rekurencyjnie silniÚ n!. W tym celu utwórz funkcjÚ uĝytkownika dziaïajÈcÈ wedïug algorytmu z ry- sunku 5.2 b. RozwiÈzanie 1. Uruchom program Excel i zapisz domyĂlnie pojawiajÈcy siÚ Zeszyt1 w wybranym przez siebie katalogu pod nazwÈ cw5_3. Moĝna równieĝ wczytaÊ arkusz cw5_3.xls z katalogu EX/Rozdz_05. 2. Zmieñ nazwÚ zakïadki Arkusz1 na Silnia. 3. Usuñ zakïadki Arkusz 2 i Arkusz3. 4. W komórce C2 umieĂÊ tekst: Aplikacja rekurencyjnego obliczania silni n!. Proponowana czcionka: Arial CE, pogrubiona, w kolorze niebieskim, rozmiar 18. 5. Wprowadě funkcjÚ przeliczeniowÈ Silnia. W tym celu: T Wywoïaj okno edytora VBE i wstaw moduï standardowy Module1 (Moduï1). T W sekcji General (Ogólne) moduïu Module1 (Moduï1) wpisz kod z listingu 5.2. PowinieneĂ uzyskaÊ efekt jak na rysunku 5.7. Rozdziaï 5. • Algorytmy rekurencyjne 125 Listing 5.2. Funkcja uĝytkownika Silnia w Êwiczeniu cw5_3 Function Silnia(n As Integer) As Long Funkcja rekurencyjnego obliczania wartoħci n! If n = 0 Then Silnia = 1 Else Silnia = n * Silnia(n - 1) End If End Function Rysunek 5.7. WyglÈd okna edytora VBE z wpisanÈ funkcjÈ Silnia Wprowadzona funkcja jest bliěniaczo podobna do funkcji utworzonej w Êwiczeniu poprzednim. Dziaïa równieĝ identycznie. Jedynie znaczniki poczÈtku i koñca nieco siÚ od siebie róĝniÈ. 6. Dokoñcz budowÚ tabeli arkusza, wykonujÈc podane poniĝej polecenia: T We wskazanych komórkach arkusza umieĂÊ nagïówki: 126 Algorytmy • mwiczenia T komórka C6 — n, T komórka D6 — n!, T komórka C7 — wpisz liczbÚ 4. Proponowana czcionka: Arial CE, normalna, rozmiar 10. Wyrównaj do prawej zawartoĂÊ C6:D6 oraz podkreĂl komórki stylem KrawÚdě dolna. T Wpisz w komórce D7 formuïÚ wywoïujÈcÈ funkcjÚ: =SILNIA(C7). Moĝesz równieĝ skorzystaÊ z menu Wstaw, kliknÈÊ polecenie Funkcja…i wybraÊ funkcjÚ uĝytkownika o nazwie Silnia. Jako jej argument naleĝy podaÊ komórkÚ C7. T WyïÈcz siatkÚ arkusza. ZakoñczyïeĂ tworzenie arkusza, który powinien mieÊ wyglÈd jak na rysunku 5.8. Rysunek 5.8. Arkusz aplikacji cw5_3 Sprawdě dziaïanie aplikacji. Poeksperymentuj, zmieniajÈc wartoĂci w komórce C7, a nastÚpnie zakoñcz pracÚ z arkuszem i Excelem, wy- bierajÈc Plik oraz Zakoñcz. Rozdziaï 5. • Algorytmy rekurencyjne 127 Obliczanie potÚgi liczby rzeczywistej Zagadnienie obliczania potÚg zostaïo juĝ zasygnalizowane w Êwicze- niu 2.1 podczas omawiania algorytmów sekwencyjnych. Rozwaĝania dotyczyïy jednak tylko potÚg z wykïadnikiem parzystym. Obecnie zo- stanie przedstawiona rekurencyjna metoda obliczania wartoĂci potÚgi o dowolnym wykïadniku. Przykïad zobrazuje jednoczeĂnie, jak w jed- nym podprogramie uĝyÊ dwóch instrukcji rekurencyjnych. m W I C Z E N I E 5.4 Rekurencyjne obliczanie potÚgi liczby rzeczywistej Przedstaw w postaci listy kroków rekurencyjny algorytm funkcji ob- liczajÈcej potÚgÚ an, gdzie aR, nN. RozwiÈzanie Dane: WartoĂÊ podstawy aR oraz potÚgi nN. Oczekiwany wynik: WartoĂÊ podstawy (argumentu) a podniesionej do potÚgi n. Analiza problemu: PotÚgowanie rekurencyjne bazuje na podnoszeniu liczby do kwadratu. Dla n = 1 wynikiem obliczeñ jest wartoĂÊ podstawy a. Dla n 1 pierwsze dziaïanie zaleĝy od tego, czy wykïadnik jest pa- rzysty, czy nie: T Jeĝeli wykïadnik jest liczbÈ naturalnÈ parzystÈ, to doprowadza siÚ go do takiej postaci, by wystÚpowaïo potÚgowanie wewnÚtrzne i zewnÚtrzne o wykïadniku 2, na przykïad 34 = (32)2, 210 = (25)2. Dla dowolnej parzystej liczby n, zapis ten ma postaÊ: n a ( a n 2 ) 2 . T Jeĝeli wykïadnik jest nieparzysty wiÚkszy od jednoĂci, to wyodrÚbnia siÚ fragment z potÚgÈ parzystÈ i otrzymany wynik poĂredni mnoĝy siÚ przez podstawÚ a, na przykïad 39 = 38 · 3. Dla dowolnej liczby nieparzystej n, zapis ten ma postaÊ: n a 1 n aa . 128 Algorytmy • mwiczenia Teraz wykïadnik n – 1 we wzorze jest juĝ parzysty, zatem potÚgowanie moĝna zapisaÊ w postaci: n a ( a  1 n 2 2 ) a . Operacje redukowania naleĝy powtarzaÊ tak dïugo, aĝ wszystkie dziaïania w wyraĝeniu otrzymajÈ opisanÈ wyĝej postaÊ. ObrazujÈ to przykïady: 39 = 38 · 3 = (34)2 · 3 = ((32)2)2 · 3, 714 = (77)2 = (76 · 7)2 = ((73)2 · 7)2 = ((72 · 7)2 · 7)2. Skoro za kaĝdym razem istotna jest informacja, czy podstawa jest pa- rzysta, czy nieparzysta, to w algorytmie musi wystÈpiÊ fragment, który sprawdza parzystoĂÊ wykïadnika. W tym celu wystarczy podzieliÊ licz- bÚ bÚdÈcÈ wykïadnikiem przez 2. Jeĝeli reszta z dzielenia równa jest zero, to wykïadnik jest podzielny przez 2, a reszta ma wartoĂÊ zero. Drugim staïym elementem w zredukowanych wyraĝeniach jest pod- noszenie do kwadratu. Warto tÚ operacjÚ zrealizowaÊ za pomocÈ od- rÚbnej funkcji, do której przekazuje siÚ odpowiedni argument. Po uwzglÚdnieniu parzystoĂci i dokonaniu redukcji wykïadnika wedïug reguï podanych powyĝej otrzymujemy zaleĝnoĂÊ klamrowÈ w postaci: , ndla 1 a (5.1) (5.2) (5.2) ­ ° ° ® ( ° ° ( ¯ n a a n 2 n 2 ,)  1 2 a 2 ) a , n jest liczbą parzystą n jest liczbą nieparzyst ą Algorytm w postaci listy kroków Zakïadamy, ĝe tworzymy dwuargumentowÈ funkcjÚ o nazwie Potega, do której przekazywane sÈ nastÚpujÈce argumenty: podstawa — do- wolna liczba rzeczywista aR, wykïadnik — liczba naturalna nN. PostaÊ funkcji rekurencyjnej jest zatem dwuargumentowa: Potega(a, n). Funkcja ta wywoïywana jest kaĝdorazowo, gdy wystÈpi w algorytmie. Krok 1. Sprawdě, czy n = 1. Jeĝeli tak, to podstaw Potega = a, po czym przejdě do kroku 7. Jeĝeli nie, to przejdě do kroku 2. Krok 2. Sprawdě, czy reszta z dzielenia wykïadnika n przez 2 jest równa zero. Jeĝeli tak, to przejdě do kroku 3. Jeĝeli nie, to przejdě do kroku 5. Rozdziaï 5. • Algorytmy rekurencyjne 129 Krok 3. {Wykïadnik jest liczbÈ parzystÈ.} Przypisz n = n/2 i przejdě do kroku 4. Krok 4. {Obliczanie potÚgi liczby a zgodnie ze wzorem (5.2) z zaleĝ- noĂci klamrowej podanej powyĝej}. Wywoïaj funkcjÚ rekurencyjnÈ Potega(a, n), a nastÚpnie podnieĂ jÈ do kwadratu: Potega = (Potega (a, n))2. Przejdě do kroku 7. Krok 5. {Wykïadnik jest liczbÈ nieparzystÈ.} Podstaw n = (n – 1)/2 i przejdě do kroku 6. Krok 6. {Obliczanie potÚgi liczby a zgodnie ze wzorem (5.3) z zaleĝ- noĂci klamrowej.} Wywoïaj funkcjÚ Potega(a, n), po czym podnieĂ jÈ do potÚgi drugiej i pomnóĝ przez podstawÚ a: Potega = (Potega(a, n))2*a. Przejdě do kroku 7. Krok 7. Zakoñcz dziaïanie algorytmu. Wynikiem jest bieĝÈca war- toĂÊ Potega. Sprawdě — wykonujÈc obliczenia na papierze — poprawnoĂÊ algo- rytmu dla wybranych wartoĂci a oraz n. m W I C Z E N I E 5.5 Algorytm rekurencyjnego obliczania potÚgi. Program w Turbo Pascalu Napisz w Turbo Pascalu program rekurencyjnego obliczania potÚgi naturalnej dowolnej liczby rzeczywistej. W programie wykorzystaj funkcjÚ zbudowanÈ z wykorzystaniem algorytmu przedstawionego w Êwiczeniu 5.4. Podnoszenie do kwadratu wykonaj za pomocÈ funkcji elementarnej Sqr. RozwiÈzanie Funkcja zrealizowana wedïug opisu podanego w algorytmie z Êwicze- nia 5.4 nie zawiera bloku wprowadzania danych i wyĂwietlania wyniku. Odpowiednie, umoĝliwiajÈce to instrukcje muszÈ znaleěÊ siÚ w programie gïównym, z którego nastÈpi wywoïanie funkcji po- tÚgujÈcej. 130 Algorytmy • mwiczenia 1. Uruchom Turbo Pascala i utwórz nowy plik, wybierajÈc z paska menu polecenia File/New. 2. W oknie edycyjnym wpisz kod z listingu 5.3 albo wczytaj program z pliku cw5_5.pas znajdujÈcego siÚ w katalogu TP/Rozdz_05. Listing 5.3. Kod rekurencyjnego programu obliczajÈcego wartoĂÊ naturalnej potÚgi liczby rzeczywistej program cw5_5; { Program oblicza rekurencyjnie wartosc } { liczby a podniesionej do potegi n. } { Deklaracja zmiennych uzywanych w programie: } { a - liczba potegowana, n - wykladnik potegi. } var a: Real; n: Integer; { ---- Deklaracja i kod funkcji rekurencyjnej Potega ------ } function Potega (a: Real; n : Integer): Real; begin if n = 1 then Potega := a else if (n mod 2 = 0) then begin n := n div 2; Potega := Sqr( Potega(a, n)); end else begin n := (n - 1) div 2; Potega := Sqr(Potega(a, n)) * a; end end; { ----------------- Koniec funkcji Potega ---- } { ---- Program glowny ------------------------------- } begin writeln; writeln ( Rekurencyjne obliczanie potegi podanej liczby ); writeln ( ----------------------------------------------- ); writeln; Rozdziaï 5. • Algorytmy rekurencyjne 131 write ( Podstawa a = ); readln (a); write ( Wykladnik n = ); readln (n); writeln; writeln ( Wynik obliczen: ); writeln ( , a:0:2, do potegi , n, = , Potega(a,n):0:2); readln; end. Funkcja rekurencyjna Potega wystÚpujÈca w listingu 5.3 jest dokïad- nym odwzorowaniem algorytmu i tak teĝ dziaïa. Do podnoszenia do kwadratu sïuĝy funkcja wbudowana Sqr(argument), która oblicza kwa- drat podanego w nawiasie argumentu. Sprawdzenie parzystoĂci liczby dokonywane jest w instrukcji warun- kowej przy wykorzystaniu instrukcji mod o skïadni: n mod 2. Wynikiem tej operacji jest reszta z dzielenia liczby caïkowitej n przez 2. Rezultat zero oznacza, ĝe n jest podzielne przez 2 — jest zatem liczbÈ parzystÈ i wykonywany jest blok instrukcji po sïowie kluczowym then. W przy- padku n nieparzystego program wykonuje polecenia po sïowie else. Iloraz w podprogramie obliczany jest za pomocÈ funkcji div, która re- alizuje dzielenie caïkowite liczb caïkowitych. Oznacza to, ĝe nie wy- stÚpuje reszta z dzielenia, na przykïad 7 div 4 = 1. Wynik dzielenia jest przypisywany argumentowi n, który jest liczbÈ naturalnÈ. Gïówny tor programu to deklaracja zmiennych oraz wczytanie danych: podstawy a i wykïadnika n. Potem wywoïywana jest dwuargumento- wa funkcja Potega(a, n). Wywoïanie nastÚpuje bezpoĂrednio z linii wy- prowadzajÈcej wyniki na ekran: writeln (a:0:2, ‘ do potegi , n, = , Potega(a,n):0:2). Sposób wyĂwietlania danych i rezultatu obliczeñ — z dwoma miejscami dziesiÚtnymi — moĝna oczywiĂcie dostosowaÊ wedïug uznania. Efekt wykonania programu przedstawia rysunek 5.9. m W I C Z E N I E 5.6 Algorytm rekurencyjnego obliczania potÚgi. Aplikacja w Excelu Napisz w Excelu program rekurencyjnego obliczania potÚgi natural- nej dowolnej liczby rzeczywistej. W programie wykorzystaj funkcjÚ uĝytkownika zbudowanÈ z wykorzystaniem algorytmu przedstawio- nego w Êwiczeniu 5.4. 132 Algorytmy • mwiczenia Rysunek 5.9. Efekt wykonania programu cw5_5 RozwiÈzanie 1. Uruchom program Excel i zapisz domyĂlnie pojawiajÈcy siÚ Zeszyt1 w wybranym przez siebie katalogu pod nazwÈ cw5_6 albo wczytaj arkusz cw5_6.xls z katalogu EX/Rozdz_05. 2. Zmieñ nazwÚ zakïadki Arkusz1 na PotÚgowanie. 3. Usuñ zakïadki Arkusz 2 i Arkusz3. 4. W komórce C2 umieĂÊ tekst — Aplikacja rekurencyjnego obliczania potÚgi. Proponowana czcionka: Arial CE, pogrubiona, w kolorze fioletowym, rozmiar 18. 5. Utwórz funkcjÚ przeliczeniowÈ Potega. W tym celu: T Wywoïaj okno edytora VBE i wstaw moduï standardowy Module1 (Moduï1). T W sekcji General (Ogólne) moduïu Module1 (Moduï1) wpisz kod z listingu 5.4, tak jak przedstawia to rysunek 5.10. Listing 5.4. Kod funkcji Potega z Êwiczenia 5.6 Function Potega(a, n) Funkcja potúgowania rekurencyjnego. Znaczenie argumentów a - podstawa, n - wykđadnik. If n = 1 Then Potega = a Else If (n Mod 2) = 0 Then Rozdziaï 5. • Algorytmy rekurencyjne 133 Rysunek 5.10. Edytor VBE z kodem funkcji Potega. Po lewej widoczne jest okno eksploratora, a poniĝej okno wïaĂciwoĂci budowanego arkusza PotÚgowanie Wykđadnik n jest parzysty. n = n / 2 Potega = Potega(a, n) Potega = Potega * Potega Else Wykđadnik n jest nieparzysty. n = (n - 1) / 2 Potega = Potega(a, n) Potega = Potega * Potega * a End If End If End Function Dziaïanie funkcji jest identyczne jak w Êwiczeniu poprzednim. Niewielkie róĝnice w kodzie polegajÈ na innym zorganizowaniu podnoszenia do kwadratu (mnoĝenie przez siebie) oraz na zastosowaniu zwykïego operatora dzielenia (/). 6. Dokoñcz budowÚ arkusza, tworzÈc tabelÚ przeliczeniowÈ: T We wskazanych komórkach arkusza umieĂÊ nagïówki: 134 Algorytmy • mwiczenia T komórka C4 — Podstawa a, T komórka E4 — Wykđadnik n, T komórka G4 — an; sformatuj literÚ n jako Indeks górny, T komórka C5 — 2, T komórki E5:E14 — wprowadě kolejne liczby naturalne od 1 do 10. T Zmieñ szerokoĂÊ kolumn C, E, G na 85 pikseli. T PodkreĂl komórki arkusza C4, E4 i G4 stylem Gruba krawÚdě dolna,. Zmieñ kolor tekstu w komórkach na zielony, po czym go wyĂrodkuj. 7. W komórce G5 wpisz formuïÚ przeliczeniowÈ — =Potega ($C$5;E5), a nastÚpnie skopiuj jÈ do komórek G6:G14. Znak ($) oznacza adresowanie bezwzglÚdne (absolutne) — podczas kopiowania formuïy adres komórki C5, do której odwoïuje siÚ formuïa, nie ulegnie zmianie. W formule wystÚpuje teĝ odwoïanie wzglÚdne, które we wklejanej formule jest aktualizowane i dotyczy innych komórek wzglÚdem poïoĝenia formuïy. W naszej funkcji sÈ to kolejne komórki z kolumny E, poczynajÈc od E5. 8. Tworzenie arkusza zostaïo zakoñczone. Efekt widoczny jest na rysunku 5.11. 9. Poeksperymentuj z wartoĂciami podstawy a oraz wykïadnika n, zmieniajÈc wartoĂci w odpowiednich komórkach, a nastÚpnie zakoñcz pracÚ z arkuszem i Excelem, wybierajÈc Plik oraz Zakoñcz. Uwagi koñcowe Mocne i sïabe strony rekurencji Zalety programów realizowanych rekurencyjnie: T pozwalajÈ rozwiÈzywaÊ problemy o dowolnej rozpiÚtoĂci zbioru i trudne do opisu, T zwiÚzïoĂÊ i elegancja zapisu. Rozdziaï 5. • Algorytmy rekurencyjne 135 Rysunek 5.11. Arkusz PotÚgowanie z aplikacji cw5_6 Niestety, sÈ teĝ powaĝne wady. Zaliczamy do nich: T powielanie tych samych obliczeñ, T niejasny i trudny do analizy przebieg wywoïañ, T niebezpieczeñstwo nieskoñczonej liczby odwoïañ, T duĝe zapotrzebowanie na pamiÚÊ podczas przetwarzania. NiedogodnoĂci sÈ spowodowane gïównie tym, ĝe po kaĝdym odwoïa- niu rekurencyjnym zachodzi koniecznoĂÊ zapamiÚtania informacji potrzebnych do odtworzenia stanu procesu sprzed wywoïania. Za- pamiÚtywane informacje przechowywane sÈ w obszarze pamiÚci zwa- nym stosem. Stos Stos (ang. stack) to obszar wewnÚtrznej pamiÚci komputerowej prze- znaczonej do czasowego przechowywania informacji zwiÈzanych z wykonywanym programem. Dla rekurencji istotne jest, by stos 136 Algorytmy • mwiczenia posiadaï strukturÚ LIFO (akronim z ang. Last In First Out). W dosïow- nym tïumaczeniu oznacza ostatni na wejĂciu jest pierwszym na wyjĂciu. Komputer odzyskuje potrzebne do wykonania programu in- formacje, pobierajÈc je z wierzchoïka stosu. ¿Èdany element lokali- zowany jest dziÚki rejestrowi zwanemu wskaěnikiem stosu (ang. stack pointer), który jest powiÚkszany o 1 kaĝdorazowo przed umiesz- czeniem kolejnego elementu na stosie i dekrementowany o 1 po zdjÚ- ciu elementu ze stosu. ’atwo zauwaĝyÊ, ĝe gdy wskaěnik ma wartoĂÊ zero, to stos jest pusty. Stos jest obszarem pamiÚci o ograniczonej pojemnoĂci, dlatego ïatwo moĝe dojĂÊ do jego przepeïnienia. Podczas rekursji zdarza siÚ to nader czÚsto i wywoïuje bïÈd, który sygnalizowany jest komunikatem stack overflow (z ang. przepeïnienie stosu). Dziaïanie stosu obrazuje rysunek 5.12. Rysunek 5.12. PoglÈdowa struktura stosu obrazujÈca: a) dodanie informacji, b) przechowanie informacji, c) pobranie informacji ze stosu Z rysunku widaÊ, ĝe stos ma strukturÚ studni. Dane umieszczane sÈ zawsze na szczycie stosu i stÈd teĝ pobierane. Informacja wprowa- dzona jako pierwsza zostanie pobrana jako ostatnia. Rozdziaï 5. • Algorytmy rekurencyjne 137 mwiczenia do samodzielnego wykonania m W I C Z E N I E 5.7 Uïóĝ algorytm obliczania sumy kolejnych liczb naturalnych. m W I C Z E N I E 5.8 Sprawdě, czy w podprogramie z listingu 5.3 moĝna zastosowaÊ zwy- kïy operator dzielenia (/). Czy instrukcjÚ n := (n - 1) div 2 moĝna zastÈpiÊ poleceniem n := n div 2? Jak to wyjaĂniÊ? m W I C Z E N I E 5.9 Przedstaw algorytm z Êwiczenia 5.4 w postaci schematu blokowego. m W I C Z E N I E 5.10 Uïóĝ algorytm obliczania pierwiastka stopnia n z podanej liczby, a na- stÚpnie zakoduj go w Turbo Pascalu i Visual Basicu.
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Algorytmy. Ćwiczenia
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ą: