plik


POLITECHNIKA WARSZAWSKA POLITECHNIKA WARSZAWSKA Instytut Automatyki i Robotyki Instytut Automatyki i Robotyki ZASADY PROGRAMOWANIA KOMPUTERW ZASADY PROGRAMOWANIA KOMPUTERW Jzyk programowania: C/C++ Jzyk programowania: C/C++ Zrodowisko programistyczne: C++ Zrodowisko programistyczne: C++Builder Builder66 WykBad 8 WykBad 8. Funkcje - wizanie parametrw. Rekurencja. . Funkcje -wizanie parametrw. Rekurencja. Parametry formalne i aktualne Parametry formalne i aktualne Lista parametrw formalnych ( nazwa typu parametr 1 , nazwa typu parametr 2 , ... nazwa typu parametr n) " nazwa typu musi okre[la typ wbudowany (int, char,...) lub wcze[niej zdefiniowany (np. struktur, ktra musi by wcze[niej zdefiniowana) " do nazwy parametru mog by dodatkowo dodane przedrostki & lub * (znaczenie ich bdzie omwione w dalszej cz[ci tego wykBadu) Lista parametrw aktualnych ( parametr 1 , parametr 2 , ... parametr n ) " ilo[ parametrw aktualnych musi by taka sama, jak ilo[ parametrw formalnych " typ parametrw aktualnych musi by zgodny z typem parametru formalnego lub da si na niego przekonwertowa. " Parametry formalne nale|y traktowa jak jakie[ zmienne podanego typu, za pomoc ktrych definiowane jest dziaBanie funkcji. Nazwy tych parametrw nie maj znaczenia. " Parametry aktualne musz odwoBywa si do konkretnych obiektw zdefiniowanych w programie. Wizanie parametrw formalnych i aktualnych Wizanie parametrw formalnych i aktualnych PARAMETRY PRZEKAZYWANE PRZEZ WARTOZ " Parametr aktualny mo|e by dowolnym wyra|eniem, ale nie typu plikowego WYKONANIE PODPROGRAMU : " przydzielenie pamici dla parametru formalnego " obliczenie warto[ci parametru aktualnego " nadanie obliczonej warto[ci parametrowi formalnemu (wraz z ewentualn konwersj w przypadku niezgodno[ci typw) " wykonanie algorytmu z tak ustalon pocztkow warto[ci parametru formalnego ( warto[ tego parametru mo|e ulega zmianie ) " zwolnienie pamici zajtej przez parametr formalny ( nawet je[li parametr formalny ulegB zmianie, to parametr aktualny pozostanie nie zmieniony ! ) PARAMETRY PRZEKAZYWANE PRZEZ ZMIENN ( czyli przez referencj) - s poprzedzone w nagBwku znakiem & (ampersand) " Parametr aktualny musi by zmienn (!), nie mo|e by liczb, staB, wyra|eniem. Bardzo wskazana jest dbaBo[ o peBn zgodno[ typw parametrw aktualnego i formalnego. WYKONANIE PODPROGRAMU : " nazwa parametru formalnego zostaje zastpiona nazw parametru aktualnego " podprogram wykonuje si na parametrze oryginalnym - je[li parametr aktualny zmieniB si w trakcie wykonania podprogramu, to zachowuje zmienion warto[ po zakoDczeniu jego wykonania. Wizanie parametrw formalnych i aktualnych c.d. Wizanie parametrw formalnych i aktualnych c.d. PARAMETRY PRZEKAZYWANE PRZEZ WARTOZ " kopia parametrw tworzona jest na wewntrzny u|ytek funkcji " wszelkie zmiany tych parametrw czynione w trakcie dziaBania funkcji zostan wic utracone po jej zakoDczeniu. PARAMETRY PRZEKAZYWANE PRZEZ ZMIENN (referencj) " funkcja wykonuje si na oryginalnych parametrach, nie na kopiach " wszelkie zmiany parametrw dokonane w trakcie dziaBania funkcji pozostaj wic aktualne po jej zakoDczeniu. Jak przekazywa parametry ? 1. Wszystkie parametry, przez ktre funkcja zwraca wyniki, musz zosta przekazane przez zmienn (czyli musz by poprzedzone w nagBwku znakiem &) . 2. We wszystkich pozostaBych przypadkach nale|y stosowa przekazywanie przez warto[ (jest to konieczne, je[li parametr aktualny nie jest nazw zmiennej). 3. Wyjtkiem od tej reguBy s tablice - zawsze s przekazywane przez zmienn (to pozwala unikn niepotrzebnego kopiowania du|ych tablic), nie poprzedza si ich znakiem & (byBby to bBd kompilacji). PrzykBady nagBwkw funkcji PrzykBady nagBwkw funkcji double f ( int x , int y) {.......} int y int y int y // funkcja zwraca warto[ typu double, obliczon na podstawie jakich[ dwu // zmiennych x i y typu int // oba parametry musz by przekazywane przez warto[, dziki czemu // mo|liwe bdzie wywoBanie postaci: cout << f (a+5, 7) << f (2, f (3, 1) ); // w drugim przypadku wynik dziaBania funkcji f // jest argumentem funkcji f - ale musi ulec konwersji z double na integer void min_max ( double A [ ] [ n ], double &min, double &max) {..........} // funkcja wczytuje jak[ tablic A typu double i wyznacza // jakie[ dwie zmienne min i max typu double gdyby te parametry nie byBy przekazywane przez nazw, to par. aktualne min1 , max1 itd.. nie ulegByby zmianie po wywoBaniu funkcji // przykBad wywoBania: double min1, max1, min2, max2, a[n][n], b[n][n] ; min_max (a, min1, max1); min_max (b, min2, max2); cout << min1 << max1 <<min2 <<max2; Zasig zmiennych Zasig zmiennych Zasig zmiennej " wszystkie miejsca w programie, z ktrych mo|liwy jest dostp do tej zmiennej " ZMIENNE GLOBALNE " zadeklarowane na zewntrz podprogramw (funkcji) " zasigiem zmiennej jest caBy program wraz z podprogramami " mo|e by przesBonita w podprogramie " ZMIENNE LOKALNE " zadeklarowane wewntrz podprogramu " zasigiem jest podprogram " przesBania zmienn globaln o tej samej nazwie " ZASIG PARAMETRW FORMALNYCH W PODPROGRAMIE " zasigiem jest podprogram " mog przesBoni zmienne globalne PrzykBad  PrzykBad  zasig identyfikatorw zasig identyfikatorw ... using namespace std; int i, j; // zmienne globalne, dostpne w caBym programie // tak|e wewntrz podprogramw, chyba |e zostan przesBonite double policz ( ) { double i,k; // zmienne lokalne, dostpne tylko w tej funkcji policz ........... // zmienna lokalna i przesBania zmienn globaln i ........ // tutaj mo|na u|ywa zmiennej globalnej j } int main ( ) { ........... // tutaj nie mo|na u|ywa zmiennej k } * je[li zmienna jest zadeklarowana wewntrz jakiego[ bloku, ograniczonego nawiasami klamrowymi, to dostpna jest tylko wewntrz tego bloku, poczynajc od miejsca tej deklaracji. * zmienna zdefiniowana w ptli for jest dostpna tylko w obszarze tej ptli. Rekurencja - Rekurencja -wprowadzenie wprowadzenie " REKURENCJA zachodzi wwczas, gdy podprogram wywoBuje sam siebie bezpo[rednio lub po[rednio ( za pomoc innego podprogramu ) " Podprogramy rekurencyjne musz charakteryzowa si dwoma wBasno[ciami: 1. W ramach algorytmu musi by zdefiniowany warunek koDca 2. Po ka|dym wywoBaniu podprogramu musi nastpi zmiana warto[ci zmiennych lub parametrw podprogramu REKURENCJA BEZPOZREDNIA " Podprogram zawiera w swojej tre[ci bezpo[rednie odwoBanie do samego siebie PrzykBad: void A (......) { // nagBwek funkcji A ........... if ( warunek ) A (......); // wywoBanie funkcji A .......... } Rekurencja po[rednia Rekurencja po[rednia REKURENCJA POZREDNIA " Podprogram A zawiera odwoBanie do innego podprogramu B, ktry zawiera po[rednie lub bezpo[rednie odwoBanie do podprogramu A. PrzykBad: void A(....); // tylko nagBwek, czyli deklaracja funkcji A void B(...) { .... A(....); // funkcja B wywoBuje funkcj A ... }; void A(....) { ... B(...); // funkcja A wywoBuje funkcj B ... } int main( ) { ... A(...); // wywoBanie funkcji A, ktra wywoBa B, a ta z kolei wywoBa A // czyli po[rednio sam siebie } Rekurencja ogonowa Rekurencja ogonowa REKURENCJA OGONOWA - najprostsza " WywoBanie rekurencyjne jest na samym koDcu dziaBania funkcji - w momencie wywoBania funkcji nie ma ju| w niej nic wicej do wykonania " WywoBanie to jest jedynym wywoBaniem rekurencyjnym w tej funkcji void czytaj_i_pisz ( ) { double x; cin >> x; cout << x << endl; if (x!=0) Funkcja rekurencyjna - tu nie czytaj_i_pisz ( ); ma jawnej ptli ! } Wczytuje i drukuje Rekurencj ogonow bardzo Batwo jest zastpi ptl: cig liczb a| do void czytaj_i_pisz ( ) { napotkania zera double x; (zero te| drukuje) do { cin >> x; Funkcja nierekurencyjna cout << x << endl; } while (x!=0) ; } Rekurencyjne wywoBywanie podprogramw Rekurencyjne wywoBywanie podprogramw Realizowane jest podobnie, jak zwykBe wywoBania podprogramu w podprogramie. " Zmienne przechowujce warto[ parametrw aktualnych (w przypadku parametrw formalnych przekazywanych przez warto[) i zmienne lokalne podprogramu wywoBujcego s zapamitywane na stosie wraz z adresem powrotu do miejsca wywoBania, po czym nastpuje wywoBanie podprogramu z nowymi parametrami aktualnymi i zmiennymi lokalnymi. " Po wykonaniu tego podprogramu nastpuje powrt do podprogramu wywoBujcego, i wwczas zmienne lokalne oraz parametry aktualne tego podprogramu staj si znowu aktywne. " Dla podprogramu rekurencyjnego parametry formalne i zmienne lokalne maj po ka|dym wywoBaniu takie same nazwy i znaczenie, ale zwykle maj inne warto[ci. Powstaje stos, ktry najpierw ro[nie (i nawet mo|e si przepeBni), a pzniej zanika. Jedynie rekurencja ogonowa nie wymaga stosu. " PrzeksztaBcanie funkcji rekurencyjnej na iteracyjn wymaga zwykle jawnego obsBu|enia stosu. Wersja rekurencyjna jest bardziej elegancka, poprawia czytelno[ kodu, lepiej si samodokumentuje - w przypadkach, kiedy problem jest z natury rekurencyjny. Ale zwykle jest wolniejsza od wersji iteracyjnej. PrzykBad  PrzykBad  Odwrotne drukowanie Odwrotne drukowanie Program drukowania w odwrotnej kolejno[ci cigu znakw wprowadzanych z klawiatury, a| do napotkania znaku zapytania (jest on drukowany jako pierwszy znak cigu wynikowego). znak adres powrotu Stos: ... ... adres powrotu void dr_wstecz ( ) { znak znak znak adres powrotu adres powrotu adres powrotu char znak; znak znak znak znak ... ... adres do main adres do main adres do main adres do main cin >> znak; if (znak!= ? ) dr_ wstecz ( ) ; cout << znak << endl; } Dla ka|dego wywoBania procedury tworzona jest nowa zmienna lokalna znak. Poziom: 1 2 ..... N cin >> znak cin >> znak ...... cin >> znak { znak== ? } ...... cout << znak cout << znak cout << znak PrzykBad  PrzykBad  Obliczanie silni Obliczanie silni Program wyznaczania warto[ci silni: k !=k*(k-1)! dla k>1; k!=1 dla k=1. int silnia (int k) { if (k > 1) { return k * silnia (k-1); } else { return 1; } Dla ka|dego wywoBania funkcji tworzona jest Podobny przykBad: funkcja, ktra nowa zmienna przechowujca warto[ zwraca sum cigu liczb <100 zakoDczonych liczb >=100. parametru k. Np.: dla wczytanej warto[ci k rwnej 3: int policz ( ) { Poziom: 1 2 3 int x; cin >> x; k=3 if (x<100) k=2 k=1 return x+policz ( ) ; silnia=1 else return 0; } silnia=2*1 silnia=3*2 PrzykBad  PrzykBad  Obliczanie wyrazw cigu Fibonacciego Obliczanie wyrazw ciguFibonacciego Program wyznaczania wyrazw cigu Fibonacciego: 0 1 1 2 3 5 8 13 ... Fib (n)= n je[li n <2 Fib(n-2) +Fib (n-1) int Fib (int n) { if (n < 2) return n; else return Fib (n-1) + Fib (n-2); } PrzykBad nadu|ywania rekurencji - te same wyra|enia obliczane s wielokrotnie F(4) F(2) F(3) n= 6 13 wywoBaD F(0) F(1) F(1) F(2) n= 20 21 tys. wywoBaD F(0) F(1) n= 31 3 mln wywoBaD! PrzykBad - PrzykBad -FloodFill wypeBnianie wntrza obszaru FloodFill--wypeBnianie wntrza obszaru oldColor newColor void Fill (x, y) { if (getPixel (x, y) == oldColor) { putPixel (x, y, newColor); Fill (x, y + 1); Fill (x, y - 1); Fill (x + 1, y); Fill (x - 1, y); } return; } // getPixel - pobierz kolor pixela // putPixel - zamaluj pixel kolorem PrzykBad - PrzykBad -pBatek [niegu Kocha pBatek [niegu Kocha ile = 0 void Koch (int bok, int ile) { if (ile==0) rysuj_odcinek_o_dlugosci (bok); 1 else { ...// zapamitaj poBo|enie Koch (bok/3, ile-1); ...// przesuD si o bok/3 ...// obr si o -60o 2 Koch (bok/3, ile-1); ...// przesuD si o bok/3 ...// obr si o 120o Koch (bok/3, ile-1); 3 ...// przesuD si o bok/3 ...// obr si o -60o Koch (bok/3, ile-1); ...// wr tam, gdzie byBe[ } 4 }

Wyszukiwarka

Podobne podstrony:
wyklad nr 5 2 xi
wyklad nr 7 # xi
wyklad nr 6  xi
ZARZĄDZANIE WARTOŚCIĄ PRZEDSIĘBIORSTWA Z DNIA 26 MARZEC 2011 WYKŁAD NR 3
Zarzadzanie strategiczne wyklad nr 2
wyklad nr 2 PK
Wykład nr 6 Decyzja
wyklad nr 4 & x
SS wyklad nr 6 ppt
Sem 4 Wykład nr 9 Interakcje 2013
AUDYT WEWNĘTRZNY Z DNIA 26 LUTY 2011 WYKŁAD NR 1
WYKŁAD NR 5 HYDRAULIKA i HYDROLOGIA (PDF)
wykład nr 6
Wyklad nr 8
WYKŁAD NR 3
Wykład nr 3
OP wyklad nr 4
ET DI2 ObwodySygnaly2 wyklad nr 9 10 czworniki aktywne
Prezentacja Wykład nr 5

więcej podobnych podstron