WYKŁAD 4 i 5

TYPY STRUKTURALNE

Poznane dotąd typy danych : Integer, Real, Char, Boolean, wyliczeniowy i okrojony są typami prostymi albo niestrukturalnymi.

Podobnie jak z instrukcji prostych budowaliśmy instrukcje strukturalne, typ strukturalny buduje się z typów składowych ; posługujemy się przy tym ustaloną w języku metodą strukturalizacji. Język pascal pozwala użytkownikowi definiować następujące typy strukturalne

a) typ tablicowy

b) typ zbiorowy

c) typ rekordowy

d) typ plikowy

Ad a)

Tablica służy do zapamiętania wielu elementów tego samego typu, np liczb. Maksymalna liczba elementów, którą można zapamiętać podawana jest w deklaracji typu tablicy. Do deklarowania typu tablicy służy słowo zastrzeżone array, po którym podaje się w nawiasach kwadratowych - listą indeksów. Jeśli podano tylko jeden indeks, to mówimy o tablicy jednowymiarowej w przeciwnym przypadku - o wielowymiarowej (dwuwymiarowej, trójwymiarowej itd). Po słowie kluczowym of podaje się typ elementu tworzonego typu tablicowego. Indeksy muszą być typu porządkowego.

Tablicą nazywamy strukturę złożoną z elementów tego samego typu, wskazywanych przez indeks lub zespół indeksów

Odpowiednikami tablic w matematyce są wektory i macierze.

Przykłady definicji typów tablicowych :

type wektor = array[1..100] of real; (a)

macierz = array[1..10,1..10] of real; (b)

wektwekt = array[1..10] of array[1..10] of real; (c)

licznikliter = array['a'..'z'] of integer; (d)

orzelresz = array[boolean] of integer; (e)

pole = array(puste, pion, skoczek, goniec, wieza, hetman, król); (f)

szach = array[1..8,'a'..'h'] of pole;

zakres = 1..40; (g)

inicjaly = array[zakres] of array[1..2] of char;

W przykładach zdefiniowano kolejno typy zawierające :

a) jednowymiarowe tablice stuelementowe liczb rzeczywistych

b) dwuwymiarowe tablice stuelementowe liczb rzeczywistych

c) jednowymiarowe tablice dziesięcioelementowe tablic dziesięcioelementowych

d) jednowymiarowe, 26-elementowe tablice liczb całkowitych;

e) jednowymiarowe, dwuelementowe tablice liczb całkowitych;

f) dwuwymiarowe, 64-elementowe tablice wartości typu wyliczeniowego pole;

g) jednowymiarowe, 40-elementowe tablice tablic dwuelementowych.

Zakładając definicje typów jak w poprzednim przykładzie możemy zadeklarować zmienne tablicowe :

var w, v : wektor;

ll : licznikliter;

m : macierz;

s : szachownica;

vi : inicjaly;

Graficzną reprezentację zmiennych tablicowych przedstawia rys (8.2)

Do wskazywania elementów tablicy służy zmienna indeksowana. Przy powyższych deklaracjach zmiennymi indeksowanymi mogą być :

w[5*sqr(2)] - 20-ty element tablicy w, tj. wartość typu real;

ll['c'] - 3-ci element tablicy ll, tj. wartość typu integer;

m[8,4] - 4-ty element z 8-mego wiersza tablicy m; wartość typu real;

s[2,'d'] - 4-ty element z 2-giego wiersza tablicy s (pole d2 szachownicy), tj. wartość typu wyliczeniowego pole;

vi[39] - 39-ty element tablicy vi, tj tablica 2-elementowa;

vi[39][2] - 2-gi element tablicy vi[39], tj. wartość typu char.

Przykłady stosowania tablic :

W poniższych przykładach zakładamy deklaracje takie jak poprzednio.

a) wczytanie liczb rzeczywistych do kolejnych elementów tablicy jednowymiarowej

for i := 1 to 100 do

read(w[i]);

b) wczytywanie liczb rzeczywistych do kolejnych elementów tablicy dwuwymiarowej

for i := 1 to 10 do

for j := 1 to 10 do

read(m[i,j])

c) wydruk tablicy dwuwymiarowej po 10 liczb w wierszu wydruku

for i:= 1 to 10 do

begin

for j := 1 to 10 do

write(m[i,j]:11:2);

writeln

end

PODPROGRAMY : FUNKCJE i PROCEDURY

Większe programy, tak jak zwykły tekst w języku naturalnym, wygodnie jest dzielić na mniejsze części. W pascalu tak jak w innych językach programowania, można wydzielać fragmenty algorytmu w odrębne jednostki, zwane podprogramami. Odpowiednie reguły języka pozwalają na zdefiniowanie dwóch rodzajów podprogramów : procedur i funkcji. Do podprogramów można się następnie odwoływać, tzn. powodować wykonanie algorytmu opisanego w definicji podprogramu. Program składa się więc z wywołań odpowiednio połączonych podprogramów.

Podprogram - wyodrębniona część programu stanowiąca odrębną całość ( blok), posiadająca nazwę i ustalony sposób wymiany informacji z pozostałymi częściami programu

Funkcja - podprogram, którego zadaniem jest wyznaczenie pojedynczej wartości zadanego typy, która podstawiana jest pod jej nazwą

Procedura - podprogram, którego zadaniem jest obliczenie jednej lub wielu wartości , bądź wyodrębnienie takiej części algorytmu w której nie obliczamy żadnej istotnej wartości. np. podprogram rysowania zadanej figury geometrycznej

Przyczyny wyodrębniania w programach procedur i funkcji (podprogramów) :

1) Dekompozycja problemu na prostsze.

Dzielenie problemu na podproblemy i uzyskiwanie w ten sposób prostszych zadań do rozwiązania jest naturalną techniką radzenia sobie z bardziej złożonymi problemami. Język pozwala na takie podejście do problemów.

2) Czytelność i przejrzystość programów

Nawet jeśli problem nie jest zbyt trudny, warto program podzielić na mniejsze, spójne logicznie fragmenty wydzielone w postaci podprogramów. Znacznie ułatwia to projektowanie, uruchamianie i ewentualne modyfikowanie dłuższych programów..

3) Unikanie powtórzeń

Jeśli pewien zespół czynności powtarza się kilkakrotnie w algorytmie głównym programu, wygodne jest wyodrębnienie go jako osobnego algorytmu pomocniczego, a następnie tylko wskazywanie, że właśnie należy wykonać ów algorytm pomocniczy.

4) Oszczędność pamięci

Dzięki wykorzystaniu zmiennych lokalnych pamięć dla nich jest rezerwowana tylko w momencie wywołania podprogramu

5) możliwość wymiany podprogramów

Możliwa jest wymiana podprogramów między programami co pozwala na korzystanie z gotowych profesjonalnych rozwiązań przez różnych programistów

Deklaracje procedur i funkcji

Wszystkie funkcje i procedury deklarowane przez użytkownika a wykorzystywane przez program muszą być zakodowane w sekcji deklaracji, po deklaracjach zmiennych. Deklarowany w sekcji deklaracji podprogram składa się z nagłówka i bloku podprogramu. Tak jak w programie jest konieczna, oprócz instrukcji opisujących algorytm definicja struktury danych, na których są przeprowadzane obliczenia, tak i podprogramy oprócz opisu algorytmu mogą obejmować deklaracje potrzebnych obiektów, np. typów lub zmiennych. W skład podprogramu mogą więc wchodzić sekcje definicji i deklaracji poznane wcześniej, wprowadzające odpowiednie identyfikatory. Zakres ważności obiektów deklarowanych w podprogramach ograniczony jest tylko do tych podprogramów. Ponieważ obiekty te mają znaczenie tylko w części programu, nazywamy je lokalnymi w danym programie. Obiekty wprowadzane bezpośrednio po nagłówku programu nazywamy globalnymi, ponieważ ich zakresem jest cały program. Sekcja deklaracji podprogramów składa się z ciągu deklaracji procedur i funkcji, z których każda jest zakończona średnikiem. Sekcja deklaracji podprogramów nie rozpoczyna się wyróżnionym słowem kluczowym, natomiast deklaracje procedur i funkcji zaczynają się od odpowiednich słów kluczowych. Najogólniej różnica między procedurą i funkcją polega na tym, że zadaniem procedury jest obliczenie jednej lub kilku wartości, podczas gdy zadaniem funkcji obliczenie tylko jednej wartości, która podstawiana jest pod jej nazwę. Opis (definicja) procedury lub funkcji który podaje się w części opisowej programu rozpoczyna się od nagłówka, po którym następuje blok zakończony średnikiem. Nagłówek procedury różni się od nagłówka funkcji : nagłówek procedury rozpoczyna się od słowa procedure, nagłówek funkcji od słowa function. Ponadto w nagłówku funkcji określa się jej typ (typ wartości funkcji).

- nagłówek procedury :

procedure identyfikator_procedury (lista_parametrów_formalnych);

- nagłówek funkcji :

function identyfikator_funkcji (lista_parametrów_formalnych) : typ wyniku;

Lista_argumetrów_formalnych zawiera deklaracje parametrów formalnych odzielone znakami średników. Deklaracja parametru formalnego zawiera identyfikatory parametru formalnego oraz identyfikator typu parametru formalnego. Słowo kluczowe var występujące w nagłówku poniższego przykładu określa sposób wymiany parametrów z otoczeniem ( o czym później)

Przyk_ad definicji procedury :

Procedure PanTadeusz ( a,b : real;

var x,y,z : real);

Begin

x:= a + b;

y:= a - b;

z:= a * b;

end;

Przykład definicji funkcji :

Function suma (a,b : real) : real;

Begin

suma:= a + b;

end;

Function roznica (a,b : real) : real;

Begin

roznica:= a - b;

end;

Nazwę procedury jest PanTadeusz. Wielkościami opisującymi dane wejściowe są a,b typu real. Wynikiem wykonania procedury są trzy wielkości : suma: a + b, różnica: a - b, iloczyn: a * b, które przekazuje się na zewnątrz procedury poprzez trzy zmienne x, y, z. Wielkości wejściowe (a,b) oraz wyjściowe (x,y,z) nazywa się parametrami procedury.

Przykład wywołania procedury :

LiczbaA := 3.1;

LiczbaB := 7.1;

PanTadeusz (LiczbaA,LiczbaB, Suma,Roznica,Iloczyn);

przy czym zmienne liczbaA, liczbaB, suma, roznica i iloczyn powinny być zadeklarowane w części opisowej programu.

Rozpatrzmy dwa programy - z użyciem i bez użycia procedury :

Program pW1 ;

var

liczbaA,liczbaB : real;

suma,roznica,iloczyn : real;

begin

liczbaA := 3;

liczbaB := 2;

suma := liczbaA + liczbaB;

roznica := liczbaA - liczbaB;

iloczyn := liczbaA * liczbaB;

writeln(' suma = ',suma);

writeln('roznica = ',roznica);

writeln('iloczyn = ',iloczyn);

end.

Program pW2 ;

var

liczbaA,liczbaB : real;

suma,roznica,iloczyn : real;

procedure PanTadeusz (a,b : real ;

var x,y,z : real);

begin

x := a + b;

y := a - b;

z := a * b;

end;

begin

liczbaA := 3;

liczbaB := 2;

panTadeusz (liczbaA,liczbaB,

suma,roznica,iloczyn);

writeln('suma = ',suma);

writeln('roznica = ',roznica);

writeln('iloczyn = ',iloczyn);

end.

Wykonanie dwóch powyższych programów pW1 oraz pW2 będzie miało taki sam skutek tzn. na ekran wyprowadzone zostaną trzy następujące napisy :

suma = 5

roznica = 1

iloczyn = 6

Jak już wspomniano funkcja służy do obliczania jednej wartości. Zamiast zdefiniowanej wyżej procedury PanTadeusz można zdefiniować trzy odrębne funkcje :

function suma (a,b : real) : real;

begin

suma := a + b;

end;

function roznica (a,b : real) : real;

begin

roznica := a - b;

end;

function iloczyn (a,b : real) : real;

begin

iloczyn := a * b;

end;

i zastosować je do obliczania sumy, roznicy i iloczynu zmiennych x i y jak w poniższym przykładzie :

program pW3 ;

var

x,y : real ;

funktion suma (a,b : real) : real;

begin

suma := a + b;

end;

funktion roznica (a,b : real) : real:

begin

roznica := a - b;

end;

funktion iloczyn (a,b : real) : real;

begin

iloczyn := a * b;

end;

begin

x := 2; y := 3;

writeln('suma = ',suma(x,y));

writeln('roznica = ',roznica(x,y));

writeln('iloczyn = ',iloczyn(x,y));

end.

Wykonanie programu pW3 da taki sam efekt jak wykonanie programu pW1 i programu pW2

Przy definiowaniu podprogramów ważną rolę spełniają tzw. parametry formalne - występujące w linii nagłówka w nawiasie. Są to wprowadzone w odpowiedni sposób nazwy, zastępujące właściwe obiekty używane potem przy odwołaniu do podprogramu. W definicji podprogramu parametry formalne służą do zapisu algorytmu. Natomiast przy wykonaniu tego algorytmu w wyniku wywołania podprogramu parametry formalne są zastępowane obiektami rzeczywistymi spoza podprogramu, tzw. parametrami aktualnymi. Wykonanie podprogramu poprzedza tzw. przekazywanie (wiązanie) parametrów, tj. proces przyporządkowania wartości albo nazwy kolejnych parametrów aktualnych odpowiednio kolejnym parametrom formalnym. Dopiero po przekazaniu parametrów i po pewnych czynnościach dodatkowych związanych z obsługą innych obiektów zadeklarowanych w podprogramie przystępuje się do właściwego wykonania podprogramu. Realizacja poszczególnych kroków algorytmu podprogramu przebiega analogicznie jak dla programu. Zasadnicza różnica polega na tym, że akcje opisane za pomocą parametrów formalnych w rzeczywistości są wykonywane przy użyciu odpowiednich parametrów aktualnych.

Wywoływanie funkcji i procedury

Wykonanie algorytmu opisanego w deklaracji funkcji następuje wtedy, gdy w trakcie wyliczania wartości jakiegoś wyrażenia zostaje napotykany nazewnik funkcji. Nazewnik składa się z identyfikatora funkcji, po którym następuje opis parametrów aktualnych, tj. argumentów wywołania funkcji. Liczba i rodzaj kolejnych parametrów wywołania musi odpowiadać liczbie i rodzajowi parametrów formalnych deklaracji funkcji.

Wykonanie algorytmu opisanego w deklaracji procedury następuje wskutek wykonania instrukcji procedury. Instrukcja procedury składa się z identyfikatora procedury, po którym następuje opis argumentów wywołania procedury. Liczba i rodzaj kolejnych parametrów aktualnych musi odpowiadać liczbie i rodzajowi parametrów formalnych deklaracji procedury.

Warto zwrócić uwagę na następującą analogię. Niech deklaracje funkcji plus oraz procedury dodawanie będą następujące :

funktion plus (x : real, y : real ) : real ;

begin

plus := x + y ;

end;

procedure dodawanie (x,y : real ;

var plus : real ) ;

begin

plus := x + y;

end;

Wówczas wykonanie instrukcji a) i b)

a) x := 1; y := 7;

z := plus(x,y); {wywołanie funkcji}

b) x := 1; y := 7;

dodawanie (x,y,z) ; {wywołanie funkkcji }

da dokładnie ten sam efekt tzn. za zmienną z podstawiona zostanie suma wartości x i y;

UWAGA : Wywołanie funkcji jest elementem wyrażenia, natomiast wywołanie procedury stanowi osobną instrukcję

Przekazywanie parametrów do podprogramów

Zadaniem podprogramów jest wykonanie operacji na danych przekazanych z programu lub na danych lokalnych. Mechanizmem umożliwiającym przekazanie danych do programu i na zewnątrz jest zastępowanie parametrów formalnych listę parametrów aktualnych w momencie wywołania podprogramu. Podstawowymi zagadnieniami związanymi z zastępowaniem parametrów formalnych przez aktualne są :

(a) sposób zastępowania parametrów formalnych przez parametry aktualne

(b) zakres odziaływania parametrów formalnych.

Jak już wspomniano wcześniej podprogramy komunikują się z częścią operacyjną programu za

pośrednictwem tzw. parametrów formalnych. Wyróżnia się dwa rodzaje tego typu parametrów :

- przekazywane przez wartość ;

- przekazywane przez zmienną.

ad a)

Lista parametrów formalnych w każdym z wymienionych przypadków przyjmuje następującą postać :

ad a) lista_parametrów : typ;

ad b) var lista_parametrów : typ;

Wystąpienie lub pominięcie słowa kluczowego var decyduje o sposobie wiązania parametrów tj. o tym w jaki sposób parametry formalne procedur i funkcji są zastępowane parametrami aktualnymi podczas wywołania podprogramu. Jeśli słowo var występuje, mówimy o przekazaniu parametrów przez zmienną w przeciwnym przypadku o przekazaniu parametrów przez wartość.

Różnicę w działaniu programu na skutek różnych sposobów wymiany danych podprogramu z otoczeniem ilustruje poniższy przykład gdzie programy różnią się tylko sposobem komunikacji podprogramu z częścią operacyjną programu :

1

2

Program test1;

var a: integer;

Procedure proc (x : integer );

Begin

writeln(x); x:= x + 2; writeln(x)

end;

Begin

a:= 3; writeln(a); proc(a); writeln(a)

end.

wyniki : na ekranie mamy :

3 (w prog. głównym, na początku )

3 (w procedurze proc, na początku)

5 (w procedurze proc, na końcu )

3 (w programie głównym, na końcu )

Program rest1;

var a: integer;

Procedure proc (var x:integer );

Begin

writeln(x); x:= x + 2; writeln(x)

end;

Begin

a:= 3; writeln(a); proc(a); writeln(a)

end.

wyniki : na ekranie mamy :

3 (w prog. głównym, na początku )

3 (w procedurze proc, na początku)

5 (w procedurze proc, na końcu )

5 (w programie głównym, na końcu )

Analiza :

Realizowany jest blok programu między nawiasami programowymi Begin i end zaznaczonymi grubą czcionką. Pierwsza wypisana trójka nie wymaga komentarza. Pojawienie się drugiej trójki oznacza, że w momencie wejścia do procedury proc x otrzymuje wartość równą parametrowi wywołania (czyli 3, jako wartości zmiennej a). Liczba 5, wypisana jako trzecia, potwierdza zwiększenie x o dwa. Wreszcie ostatnia wypisana trójka pokazuje, że wartość x z procedury proc nie została przekazana do zmiennej a programu głównego, będącego parametrem wywołania. Ten sposób przekazywania parametrów nazywamy przekazywaniem przez wartość. Charakteryzuje się on tym, że procedura (funkcja) co prawda pobiera wartości parametrów przekazywanych do niej w wywołaniu, ale nie daje możliwości przekazywania wyników do otoczenia za pomocą tychże parametrów ( nie zwraca wartości). Dokładniej : parametr procedury (funkcji) należy wówczas traktować jako zmienną lokalną. Wartość tej zmiennej przy wywołaniu procedury (funkcji) staje się równa wartości parametru wywołania. Można ją wykorzystywać i zmieniać wewnątrz procedury (funkcji), ale ginie ona wraz z zakończeniem wywołania procedury (funkcji). W naszym przykładzie - zwiększeniu o dwa uległa wartość zmiennej lokalnej - parametru x, a nie wartość zmiennej a. Przekazując parametry do procedury (funkcji) możemy też postąpić inaczej ( prawa strona). Dwie wersje przedstawionego programu różnią się tylko nagłówkiem procedury . Widzimy, że wstawienie słowa var przed nazwą parametru spowodowało, że jako czwarta została wypisana liczba 5, zamiast 3. Ostatnia wypisana piątka sygnalizuje, że operacje wykonywane na parametrze x były faktycznie wykonywane na zmiennej a. Ten sposób przekazywania parametrów nazywamy przekazywaniem przez zmienną. Charakteryzuje się on tym, że procedura (funkcja) zarówno pobiera, jak i zwraca (ewentualnie zmienione) wartości parametrów wywołania. Daje w ten sposób możliwość przekazywania wyników do otoczenia podprogramu (funkcji) za pośrednictwem parametrów. Dokładniej: wszystkie operacje przeprowadzane na parametrach przekazywanych w ten sposób - wykonywane są na odpowiadających im parametrach aktualnych (nielokalnych zmiennych).

ad b)

Pascal należy do języków o strukturze blokowej. Oznacza to , że język dopuszcza istnienie pewnej konstrukcji, zwanej blokiem, wewnątrz której mogą występować takie same konstrukcje składniowe. Wewnątrz bloku mogą występować inne bloki, zwane wewnętrznymi; wewnątrz tych bloków mogą występować dalsze, itd. Bloki te występują jakby na różnych poziomach, gdyż jedne z nich leżą wewnątrz innych. Mówimy o strukturze wielopoziomowej albo zagnieżdżonej. Wprowadzone wcześniej pojęcie bloku języka pascal ma również wymienione powyżej cechy.

Program pascala składa się z nagłówka i bloku po którym następuje kropka. Blok składa się z sekcji definicji i deklaracji oraz z instrukcji złożonej. Wśród różnych sekcji bloku znajduje się sekcja deklaracji podprogramów, gdzie można podać deklarację dowolnej liczby procedur i funkcji. Każda z nich składa się z nagłówka i bloku, takiego samego pod względem składniowym jak blok programu. Bloki procedur i funkcji mogą więc zawierać m.in. deklaracje podprogramów wewnętrznych (lokalnych), a te znowu... itp.,itp. Są języki o strukturze zasadniczo różnej od struktury blokowej pascala. Są to języki o strukturze segmentowej, a najbardziej popularnym językiem z tej klasy jest Fortran.

Zasadniczą zaletą struktury blokowej jest to, że umożliwia ona skonstruowanie programu w sposób oddający zależności logiczne problemu głównego. Na przykład podziałowi zasadniczego problemu na mniejsze odpowiada podział programu na podprogramy. Te z kolei, jeśli są zbyt złożone, możemy dzielić dalej wyróżniając podprogramy wewnętrzne. itd. Taka organizacja pozwala na wiązanie ze sobą fragmentów o silnych związkach wzajemnych i separowanie fragmentów niezależnych.. Mechanizmem wspomagającym taką organizację jest ograniczenie zasięgu identyfikatorów. Zasięgiem identyfikatora nazywamy fragment tekstu, wewnątrz którego można używać identyfikatora zgodnie z przeznaczeniem, tj. do wskazania obiektu, z którym jest związany. Przy rozpatrywaniu zasięgu identyfikatorów istotna jest struktura tekstu programu, a nie sens poszczególnych deklaracji. W pascalu obowiązuje ogólna reguła, że zasięgiem identyfikatora zdefiniowanego w danym bloku jest tylko ten blok, od miejsca zdefiniowania identyfikatora ( za pomocą deklaracji ) aż do końca bloku.. Reguła ogólna dotyczy identyfikatorów stałych, typów, zmiennych, procedur i funkcji. Identyfikatory procedur i funkcji są wprowadzane za pomocą nagłówka i podprogramu. Ponadto zasięgiem parametru formalnego podprogramu jest tekst tego podprogramu. od miejsca wprowadzenia parametru w nagłówku do końca bloku tego podprogramu. Z podanej reguły ogólnej wynika, że zasięg identyfikatora wprowadzonego w danym bloku obejmuje również wszystkie bloki wewnętrzne danego bloku. Inaczej mówiąc w podprogramie mogą być dostępne obiekty zdefiniowane w bloku zewnętrznym, obejmującym dany blok (podprogram). W szczególności obiekty, których identyfikatory wprowadzono w bloku programu, nazywa się globalnymi dla podkreślenia globalnego zasięgu. Do obiektów zewnętrznych można się odwoływać w bloku wewnętrznym, o ile tylko nie ma kolizji takich samych nazw. Na przykład w podprogramie można przypisać zmiennej globalnej wartość wyrażenia, zadeklarować zmienną , podając identyfikator typu z bloku zewnętrznego, itd.. Można spytać, co się dzieje, gdy dwa różne obiekty mają taki sam identyfikator ? Dla obiektów tego samego poziomu jest to niemożliwe, tzn. zabrania się definiowania i deklarowania w jednym bloku obiektu o identyfikatorze już wprowadzonym w tym właśnie bloku. Natomiast w bloku wewnętrznym można wprowadzić identyfikator taki sam jak już wcześniej zdefiniowany w bloku zewnętrznym obejmującym dany blok. Zachodzi wtedy taka sytuacja, że w bloku wewnętrznym mamy jeden identyfikator do oznaczenia dwu różnych obiektów programu. Obowiązuje wtedy zasada, że identyfikowanym w takim przypadku obiektem jest obiekt wewnętrzny. Mówimy, że zachodzi tzw. przesłanianie nazw, tj., że identyfikator obiektu wewnętrznego przesłania zewnętrzny. Oznacza to jednocześnie, że obiekt zewnętrzny jest niedostępny aż do końca bloku wewnętrznego.

Podprogramy rekurencyjne

Podprogramy rekurencyjne - to podprogram, który wywołuje sam siebie. W języku pascal można deklarować funkcje i procedury rekurencyjne, które w sekcji instrukcji zawierają wywołania tych samych procedur lub funkcji. Niektóre problemy można w pascalu rozwiązać w sposób iteracyjny bądź rekurencyjny. Zaletą rekurencji jest przejrzysty zapis problemu Wadą natomiast jest duże zaangażowanie pamięci i długi czas obliczeń. Przykładem omawianego zagadnienia może być obliczanie silni.

Definicji silni : N! = 1 * 2 * 3 * * * (N - 1) * N ( ITERACJA )

PROGRAM SILNIA_ITERACJA (Input, Output);

var N: byte;

FUNCTION SIL(L : INTEGER) : INTEGER;

VAR I,F : INTEGER;

BEGIN

F:= 1;

FOR I := 1 to L

DO F := I * F ;

SIL := F

END;

BEGIN {poczatek programu glownego}

Write(' Podaj N ');

Readln(N);

Writeln(' Wartosc N! = ', SIL(N))

END.

Definicja silni :

1 dla N = 0'

N! = ( REKURENCJA )

N*(N-1)! dla N > 0,

PROGRAM SILNIA_REKURENCJA (Input, Output);

VAR N : Byte;

Function SILNIA(X:Byte):Longint;

BEGIN

IF X > 10 THEN HALT;

IF X = 0 THEN SILNIA:=1

ELSE SILNIA:=X * SILNIA(X-1); {REKURENCJA}

END; {SILNIA}

BEGIN {Poczatek programu głównego}

Write(' Podaj N ');

Readln(N);

Writeln(' Wartosc N! = ',SILNIA(N));

END.

Zasady programowania strukturalnego

Programowanie strukturalne charakteryzuje się analitycznym podejściem do postawionego zadania, co oznacza podział zadania na podzadania, które z kolei dekomponuje się na podzadania niższego poziomu, itd. Proces podziału przebiega dotąd, dopóki zadania cząstkowe nie będą na tyle małe i proste, że sposób ich realizacji stanie się oczywisty. Podejście to prowadzi do uzyskania programu o wyraźnej strukturze i dlatego nazywa się je programowaniem strukturalnym, bądź metodą kolejnych uściśleń. W praktyce programistycznej przy opracowywaniu nowych algorytmów (programów) metoda kolejnych uściśleń jest dominująca. Natomiast dostosowywanie programu do nieco zmienionego zadania wymaga korzystania z metody syntetycznej.

Ogólne zalecenia odnośnie programowania strukturalnego :

1) Podział programu na mniejsze moduły

2) Treść modułu powinna zawierać całą informację o strukturze danych modułu

3) Przepływ danych między modułami powinien być minimalny i kontrolowany.

4) Liczba wejść i wyjść modułu powinna być jak najmniejsza

5) Tekst modułu powinien mieścić się na jednej stronie wydruku

6) Tworzony kod powinien być wykonywany sekwencyjnie, bez skoków

7) Treść powinna być jednoznaczna, bez wywołań pośrednich

8) Należy unikać efektów ubocznych tj. niepożądanych i nieprzewidzianych zniekształceń przesłanych do niego danych wejściowych oraz zmiennych globalnych.

9) Należy zwrócić uwagę na zasłanianie zmiennych w przypadku nadania tych samych nazw obiektom lokalnym i globalnym. Obiekty globalne tracą ważność wewnątrz bloku w którym jest określony jednoimienny obiekt lokalny.

10) Duże struktury danych (np tablice) należy przekazywać raczej przez zmienną niż przez wartość, które angażuje dodatkowy obszar pamięci na kopię całej struktury danych i czas na kopiowanie

11) W zadaniach które można rozwiązać iteracyjnie należy unikać rekurencji

TYPY STRUKTURALNE

Klasa typów używanych do definiowania złożonych struktur

TABLICE REKORDY ZBIORY PLIKI

CECHY OGÓLNE :

TYPY STRUKTUR. DEFINIUJE SIĘ ZA POMOCA INNYCH TYPÓW

OBIEKTY OKREŚLANE PRZEZ TYPY STR. MAJĄ RÓŻNĄ STRUKTURĘ

TABLICE

STRUKTURA DANYCH ZłOŻONA Z ELEMENTÓW TEGO SAMEGO TYPU

(Elementy tablicy wskazywane są przez zmienną indeksową)

DEFINICJA TYPÓW TABLICOWYCH :

TYPE

(a) wektor = array [1..100] of real ;

(b) macierz = array [1..10,1..10] of real ;

(c) wektwe = array [1..10] of array [1..10] of real ;

(d) licznikli = array ['a'..'z'] of integer ;

(e) orzelresz = array [Boolean] of integer ;

(f) pole = (puste, pion, skoczek, goniec, wieza, hetman, krol) ;

szachy = array [1..8,'a'..'h'] of pole ;

(g) zakres = 1..40 ;

inicjaly = array [zakres] of array [1..2] of char ;

Powyższe typy zawierają :

(a) 1-wymiarowe tablice 100 elementowe liczb rzeczywistych

(b) 2-wymiarowe tablice 100 elementowe liczb rzeczywistych

(c) 1-wymiarowe tablice 10 elementowe tablic 10-cio elementowych

(d) 1-wymiarowe, 26-elementowe tablice liczb całkowitych

(e) 1-wymiarowe, 2-elementowe tablice liczb całkowitych

(f) 2-wymiarowe, 64-elementowe tablice wartości typu wyliczeniowego pole

(g) 1-wymiarowe, 40-elementowe tablice tablic 2-elementowych

DEKLARACJE ZMIENNYCH TABLICOWYCH ;

var w, v : wektor ;

ll : licznikl ;

m : macierz ;

s : szachy ;

vi : inicjaly ;

DEKLARACJE ZMIENNYCH TABLICOWYCH ;

var w, v : wektor ;

ll : licznikl ;

m : macierz ;

s : szachy ;

vi : inicjaly ;

ZMIENNA INDEKSOWA - WSKAZUJE ELEMENTY TABLICY

Przykłady :

w[5*sqr(2)] - 20-ty element tablicy w, tj. wartość typu real ;

ll ['c'] - 3-ci element tablicy ll, tj. wartość typu integer ;

m [8,4] - 4-ty element z ósmego wiersza tablicy m tj. wartość typu real

s [2, 'd'] - 4-ty element z drugiego wiersza tablicy s; wartość typu pole

vi[39] - 39-ty element tablicy vi, tj. tablica 2- elementowa

vi[39][2] - 2-gi element tablicy vi[39], tj. wartość typu char.

PRZYKLADY STOSOWANIA TABLIC

a) Wczytanie liczb rzeczywistych do kolejnych elem. tabl. jednowym.

for i := 1 to 100 do

read(w[i])

b) Wczytanie liczb rzecz. do kolejnych elem. tablicy dwuwymiarowej

for i := 1 to 10 do

for j := 1 to 10 do

read(m[i,j])

c)Wydruk tablicy dwuwymiarowej po 10 liczb w wierszu wydruku

for i := 1 to 10 do

begin

for j := 1 to 10 do

write(m[i,j]:11:2);

writeln

end

d) Znajdowanie największej liczby w tablicy jednowymiarowej

max := w[1];

for i := 2 to 100 do

if max < w[i] then max := w[i] ;

writeln('Największa liczba w tablicy to ', max)

e) Przypisanie tablicy wartości innej tablicy

for i := 1 to 100 do

w[i] := v[i]

f) Zamiana miejscami dwóch elementów tablicy w, o indeksach k i l;

pom := w[k];

w[k] := w[l];

w[l] := pom;

PRZYKŁAD PROGRAMU

TABLICE - sortowanie przez wybór kolejnych minimów

Problem : 25 wyników pomiarów wczytać i wydrukować w kolejności rosnącej

PROGRAM sort (input, output) ;

CONST

maxindeks = 25;

VAR

k, poczatek, pozmin : integer ;

min : real ;

pomiar : ARRAY [1..maxindeks] OF real ;

BEGIN

writeln(' Program porządkowania ciagu pomiarów ') ;

writeln(' Podaj ',maxindeks, ' pomiarow ' );

FOR k := 1 TO maxindeks DO

read(pomiar[k] ;

FOR poczatek := 1 TO maxindeks - 1 DO

BEGIN

{wybor minimum z czesci wektora

poczatek..maxindeks }

min := pomiar[poczatek] ;

pozmin := poczatek ;

FOR k := poczatek + 1 TO maxindeks DO

IF pomiar[k] < min THEN

BEGIN

min := pomiar[k] ;

pozmin := k

END;

{ zamiana }

pomiar[pozmin] := pomiar[poczatek] ;

pomiar[poczatek] := min

END;

writeln;

writeln(' Pomiary uporzadkowane rosnaco ') ;

writeln( ' Nr pomiar ') ;

FOR k := 1 TO maxindeks DO

writeln(k:2, ' ', pomiar[k]:6:2)

END.

W7-8/1/SZCZYGIE_

W7-8/22/SZCZYGIE_

---