INFORMATYKA

Programowanie

strukturalne

Dr Zdzisław Szczepanik

Wzorcem Języków strukturalnych w sensie

klasycznym jest Język programowania Pascal.

Można łatwo przebrnąć początkowe definicje tego

języka posługując się trzema pozycjami
literaturowymi w kolejności ich przedstawienia:

1.Wł.Arciszewski ,” Ćwiczenia z Turbo

Pascala”+dyskietka, ISBN 83-7279-051-5, wyd.
MIKOM,

www.mikom.com.pl

2.Sam.A.Abolrous, ” Pascal podstawy

programowania” + dyskietka, ISBN 83-7158-
075-4, wyd. MIKOM.

3.Andrzej Marciniak, Borland Pascal 7.0 z

elementami programowania cz I a, cz I b – język
programowania, ISBN 83-85060-53-7, ISSN
0867-6011, wyd. NAKOM, e-mail: nakom@soho-
online.com

STRUKTURA PROGRAMU W JĘZYKU

STRUKTURA PROGRAMU W JĘZYKU

PASCAL

PASCAL

NAGŁÓWEK

NAGŁÓWEK

PROGRAMU

PROGRAMU

Program

Program

nazwa

nazwa

[parametry

[parametry

]

]

  

  

BLOK DEKLARACYJNY

BLOK DEKLARACYJNY

deklaracje modułów, stałych, zmiennych,definicje typów

deklaracje modułów, stałych, zmiennych,definicje typów

Uses,const,type,var,label,procedure,function

Uses,const,type,var,label,procedure,function

  

  

BLOK

BLOK

WYKONAWCZ

WYKONAWCZ

y

y

begin

begin

(ciąg instrukcji)

(ciąg instrukcji)

np. begin-end, if..then..else, goto, repeat..until

np. begin-end, if..then..else, goto, repeat..until

For..to, while.. Do, case..of..else..end, := , inline(..)

For..to, while.. Do, case..of..else..end, := , inline(..)

Wywołanie procedury, wywołanie funkcji

Wywołanie procedury, wywołanie funkcji

end.

end.

Zagadnienie zapisu liczby w

Zagadnienie zapisu liczby w

dowolnym systemie liczbowym.

dowolnym systemie liczbowym.

S

S

10

10

= { 0,…,9 }

= { 0,…,9 }

3 2 1 0 ,-1-2

3 2 1 0 ,-1-2

2076,35 =

2076,35 =

= 2*10

= 2*10

3

3

+0*10

+0*10

2

2

+7*10

+7*10

1

1

+6*10

+6*10

0

0

+3*10

+3*10

-

-

1

1

+5*10

+5*10

-2

-2

S

S

7

7

= { 0,…,6 }

= { 0,…,6 }

3 2 1 0 ,-1-2

3 2 1 0 ,-1-2

2561,34 =

2561,34 =

= 2*7

= 2*7

3

3

+5*7

+5*7

2

2

+6*7

+6*7

1

1

+1*7

+1*7

0

0

+3*7

+3*7

-

-

1

1

+4*7

+4*7

-2

-2

=686+245+42+1+3/7+4/49=974+25/49

=686+245+42+1+3/7+4/49=974+25/49

w

w

sys.10

sys.10

Przykład mnożenia w systemie 7

Przykład mnożenia w systemie 7

4*5 = 20 = 2*7

4*5 = 20 = 2*7

1

1

+ 6*7

+ 6*7

0

0

= ( 26 )

= ( 26 )

7

7

Zdefiniujmy operację dzielenia całkowitego

Zdefiniujmy operację dzielenia całkowitego

bez reszty w postaci :

bez reszty w postaci :

m := 20 DIV 7, m= 2 ponieważ 20 / 7

m := 20 DIV 7, m= 2 ponieważ 20 / 7

= 2 + 6/7

= 2 + 6/7

Zdefiniujmy operację otrzymania reszty z

Zdefiniujmy operację otrzymania reszty z

całkowitego dzielenia

całkowitego dzielenia

r := 20 MOD 7, r = 6

r := 20 MOD 7, r = 6

Jak otrzymać ciąg cyfr reprezentujący

Jak otrzymać ciąg cyfr reprezentujący

wynik z mnożenia 4*5

wynik z mnożenia 4*5

10

10

= 26

= 26

7

7

Można to osiągnąć wprowadzając zapis

Można to osiągnąć wprowadzając zapis

m := (4*5) DIV 7 = 20 DIV 7

m := (4*5) DIV 7 = 20 DIV 7

=

=

2

2

r := (4*5) MOD 7 = 20 MOD 7 = 6

r := (4*5) MOD 7 = 20 MOD 7 = 6

A(4,5) := 10*m + r = 10*2 + 6 =

A(4,5) := 10*m + r = 10*2 + 6 =

26

26

Spróbujmy rozwiązać problem tabliczki mnożenia w

dowolnym systemie liczbowym na przykładzie systemu

siódemkowego.

*

*

1

1

2

2

3

3

4

4

5

5

6

6

1

1

1

1

2

2

3

3

4

4

5

5

6

6

2

2

2

2

4

4

6

6

11

11

13

13

15

15

3

3

3

3

6

6

12

12

15

15

21

21

24

24

4

4

4

4

11

11

15

15

22

22

26

26

33

33

5

5

5

5

13

13

21

21

26

26

34

34

42

42

6

6

6

6

15

15

24

24

33

33

42

42

51

51

Uniwersalny algorytm

Uniwersalny algorytm

tabliczki mnożenia w

tabliczki mnożenia w

dowolnym systemie

dowolnym systemie

liczbowym na

liczbowym na

przykładzie systemu

przykładzie systemu

siódemkowego.

siódemkowego.

Schemat blokowy.

Schemat blokowy.

Algorytm musi spełniać

Algorytm musi spełniać

warunki:

warunki:

 

 

1.

1.

Uniwersalność

Uniwersalność

– rozwiązanie

– rozwiązanie

pewnej klasy

pewnej klasy

zadań a nie jednostkowego

zadań a nie jednostkowego

zadania

zadania

 

 

2.

2.

Dyskretność

Dyskretność

– opis sekwencji

– opis sekwencji

pewnych

pewnych

czynności i powiązań między nimi

czynności i powiązań między nimi

 

 

3.

3.

Jednoznaczność

Jednoznaczność

– postać bez

– postać bez

niedomówień

niedomówień

i swobody interpretacji

i swobody interpretacji

 

 

4.

4.

Skończoność

Skończoność

O efektywności algorytmu

O efektywności algorytmu

decydują:

decydują:

Czas realizacji algorytmu –

Czas realizacji algorytmu –

tzw. złożoność czasowa

tzw. złożoność czasowa

Wielkość potrzebnej pamięci

Wielkość potrzebnej pamięci

operacyjnej

operacyjnej

Zajętość pamięci dyskowej

Zajętość pamięci dyskowej

STAR

T

k-
podst.

system

u

i:=1

j:=1

m:=(i*j) DIV k
r:=(i*j) MOD
k
A(i,j):=10*m+
r

j:= j+1

IF

j = k-

1

END

STO
P

Wydrukuj

tabliczkę

mnożenia

IF

i= k-1

i := i

+1

tak

tak

ni
e

ni
e

Jak zrealizować zadanie zapisu

Jak zrealizować zadanie zapisu

tego zadania w postaci

tego zadania w postaci

programu komputerowego w

programu komputerowego w

jakimś języku programowania?

jakimś języku programowania?

Język programowania

Język programowania

(

(

programing

programing

language)-

language)-

sztucznie stworzony

sztucznie stworzony

język, używany przez programistów

język, używany przez programistów

do wydawania rozkazów (poleceń)

do wydawania rozkazów (poleceń)

komputerowi. Są nim pisane

komputerowi. Są nim pisane

wszystkie programy komputerowe.

wszystkie programy komputerowe.

Za pomocą języka programowania

Za pomocą języka programowania

tworzy się tzw. kod źródłowy

tworzy się tzw. kod źródłowy

programu, który tłumaczony jest na

programu, który tłumaczony jest na

kod maszynowy.

kod maszynowy.

Program komputerowy to

algorytm

zapisany

w

języku

programowania, w którym czynności
zapisane

są

jako

instrukcje.

W programie można wyodrębnić
pewne

logiczne

całości

jako

procedury, funkcje, moduły

lub

obiekty

.

Procedury, funkcje i obiekty są zwykle
stosowane

do

opisu

czynności

wielokrotnie powtarzanych w ramach
tego samego programu ale mogą być
równie dobrze wykorzystywane w
różnych innych programach.

Języki formalne

Język formalny zwykle jest zdefiniowany

poprzez podanie

• zbioru symboli (alfabetu, słownika)
• zbioru reguł konstrukcji

Zbiór wszystkich wyrażeń poprawnie

zbudowanych danego języka formalnego

określa jego twórca

W językach formalnych proces konstrukcji

wyrażeń poprawnie zbudowanych zwykle jest

jednoznacznie określony.

Przedmiotem semantyki jest

przyporządkowywanie językowi interpretacji.

Teoria modeli badająca związki semantyczne

jest więc teorią interpretacji

Są dwa podstawowe typy języków:

 Języki programowania niskiego

poziomu

 Języki programowania wysokiego

poziomu

Asembler – język, w którym stosuje

się elementarne instrukcje procesora.

Jedno polecenie jest jednym rozkazem

– programowanie w kodzie

maszynowym.

Wady programowania w asemblerze:

Wady programowania w asemblerze:

1.

1.

    

    

proces obliczeniowy rozbijany jest na

proces obliczeniowy rozbijany jest na

drobne elementy programowane każdy osobno,

drobne elementy programowane każdy osobno,

gdyż instrukcje asemblera pozwalają tylko na

gdyż instrukcje asemblera pozwalają tylko na

dokonywanie elementarnych operacji. Stąd

dokonywanie elementarnych operacji. Stąd

długość programu

długość programu

2.

2.

    

    

Postać instrukcji ma charakter

Postać instrukcji ma charakter

abstrakcyjny, nieczytelny dla człowieka, co

abstrakcyjny, nieczytelny dla człowieka, co

utrudnia proces uczenia i zwiększa możliwość

utrudnia proces uczenia i zwiększa możliwość

popełnienia błędu.

popełnienia błędu.

3.

3.

    

    

Przy programowaniu trzeba uwzględniać

Przy programowaniu trzeba uwzględniać

strukturę elektroniczną procesora

strukturę elektroniczną procesora

4.

4.

    

    

Przy pisaniu trzeba kontrolować położenie

Przy pisaniu trzeba kontrolować położenie

w pamięci komputera zarówno programu, jak i

w pamięci komputera zarówno programu, jak i

danych

danych

5.

5.

    

    

brak widocznego związku pomiędzy

brak widocznego związku pomiędzy

programem a matematycznym lub logicznym

programem a matematycznym lub logicznym

opisem jego funkcji

opisem jego funkcji

6.

6.

    

    

związek asemblera z maszyną utrudnia

związek asemblera z maszyną utrudnia

przenoszenie programów napisanych w tym

przenoszenie programów napisanych w tym

języku na inną maszynę

języku na inną maszynę

Przykład : fragment programu napisanego

Przykład : fragment programu napisanego

w języku niskiego poziomu

w języku niskiego poziomu



ADRES

ADRES

KOD INSTRUKCJI

KOD INSTRUKCJI

KOD ASEMBLERA

KOD ASEMBLERA

000000D3

000000D3

0004

0004

add

add

[si],al

[si],al

000000D5

000000D5

0000

0000

add [bx+si],al

add [bx+si],al

000000D7

000000D7

004801

004801

add

add

[bx+si+0x1],cl

[bx+si+0x1],cl

000000DA

000000DA

0000

0000

add [bx+si],al

add [bx+si],al

000000DC

000000DC

48

48

dec ax

dec ax

000000F8

000000F8

FC

FC

cld

cld

000000F9

000000F9

0B01

0B01

or

or

ax,[bx+di]

ax,[bx+di]

000000FB

000000FB

00FC

00FC

add ah,bh

add ah,bh

000000FD

000000FD

8B05

8B05

mov ax,

mov ax,

[di]

[di]

000000FF

000000FF

08FC

08FC

or ah,bh

or ah,bh

00000101

00000101

8B05

8B05

mov ax,[di]

mov ax,[di]

Model problemu a język programowania

Model problemu a język programowania

.

.

Język programowania reprezentuje abstrakcyjną

Język programowania reprezentuje abstrakcyjną

maszynę, która rozumie występujące w nim

maszynę, która rozumie występujące w nim

terminy, stanowiące wyższy poziom abstrakcji

terminy, stanowiące wyższy poziom abstrakcji

w stosunku do obiektów używanych przez

w stosunku do obiektów używanych przez

rzeczywisty komputer.

rzeczywisty komputer.

Stosowanie języka programowania wyższego

Stosowanie języka programowania wyższego

poziomu jest:

poziomu jest:



wygodne, gdyż łatwiej napisać program stosując

wygodne, gdyż łatwiej napisać program stosując

słowa, liczby, instrukcje niż np. ciągi bitów,

słowa, liczby, instrukcje niż np. ciągi bitów,

ponadto uwalnia programistę od konieczności

ponadto uwalnia programistę od konieczności

wyboru reprezentacji danych np. liczby (o ile

wyboru reprezentacji danych np. liczby (o ile

liczba jest elementarnym obiektem w tym

liczba jest elementarnym obiektem w tym

języku).

języku).



krępujące, bo ogranicza wolność programisty,

krępujące, bo ogranicza wolność programisty,

język narzuca określone pojęcia podstawowe

język narzuca określone pojęcia podstawowe

(elementarne)

(elementarne)

a także reguły, które muszą być przestrzegane

a także reguły, które muszą być przestrzegane

.

.

Translatory-programy do

przetwarzania kodu programu

Kompilator (compiler)

Kompilator (compiler)

-specjalny

program

przetwarzający

-specjalny

program

przetwarzający

polecenia języka wysokiego poziomu

polecenia języka wysokiego poziomu

(kod źródłowy programu) na kod

(kod źródłowy programu) na kod

maszynowy, zrozumiały przez procesor.

maszynowy, zrozumiały przez procesor.

Tłumaczenie

całego

programu

Tłumaczenie

całego

programu

następuje

przed

uruchomieniem

następuje

przed

uruchomieniem

programu.

programu.

Interpreter

Interpreter

-program przetwarzający polecenia języka

-program przetwarzający polecenia języka

wysokiego poziomu w trakcie wykonywania

wysokiego poziomu w trakcie wykonywania

programu (przetwarza rozkaz po rozkazie i

programu (przetwarza rozkaz po rozkazie i

nie tworzy kodu programu jako całości)

nie tworzy kodu programu jako całości)

Języki programowania

wysokiego poziomu

– używają słów języka naturalnego.

Nowoczesne języki są związane z

systemami programowymi (zbiór

narzędzi wspomagających: edycja,

translacja, testowanie).

Realizacja projektu informatycznego:

Realizacja projektu informatycznego:



defini

defini

owanie

owanie

problemu,

problemu,



wybór metody,

wybór metody,



opracowanie algorytmu,

opracowanie algorytmu,



programowanie,

programowanie,



testowanie,

testowanie,



przygotowanie dokumentacji,

przygotowanie dokumentacji,



tworzenie wersji dystrybucyjnej

tworzenie wersji dystrybucyjnej

Elementy

programowania

metodologia

Spróbujmy użyć języka naturalnego do

zaprogramowania naszego problemu.

Najlepiej na początku napisać program

w języku (polskim), którym się

posługujemy na co dzień, czyli w tak

zwanym pseudojęzyku.

Później przeniesiemy nasz tekst na

język formalny, strukturalny,

obiektowy czy inny. Dużo lepiej wtedy

zrozumiemy czego oczekujemy w

rozwiązaniu naszego zadania.

Nie zawsze przeniesiemy treść w

pseudojęzyku na język formalny.

STAR

T

k-
podst.

system

u

i:=1

j:=1

m:=(i*j) DIV k
r:=(i*j) MOD
k
A(i,j):=10*m+
r

j:= j+1

IF

j = k-

1

END

STO
P

Wydrukuj

tabliczkę

mnożenia

IF

i= k-1

i := i

+1

tak

tak

ni
e

ni
e

et1

et1

et3

et3

et2

et2

et4

et4

Program ma nazwę

Program ma nazwę

tabliczka_mnożenia_w_dow_syst ;

tabliczka_mnożenia_w_dow_syst ;

Biblioteki używane w programie

Biblioteki używane w programie

Standartowa ekranu ;

Standartowa ekranu ;

Etykiety

Etykiety

et1, et2, et3, et4, et5 ;

et1, et2, et3, et4, et5 ;

Zmienne w programie

Zmienne w programie

I, j, k, m, r : całkowite ;

I, j, k, m, r : całkowite ;

A : tablica dwuwymiarowa [ 1..9 , 1..9 ] ;

A : tablica dwuwymiarowa [ 1..9 , 1..9 ] ;

blok1

blok1

Drukuj na ekranie ( ‘ tabliczka mnożenia w dowolnym’)

Drukuj na ekranie ( ‘ tabliczka mnożenia w dowolnym’)

;

;

Drukuj na ekranie ( ‘ systemie liczbowym ’) ;

Drukuj na ekranie ( ‘ systemie liczbowym ’) ;

Drukuj na ekranie ( ‘Podaj podstawę systemu k = ? ’) ;

Drukuj na ekranie ( ‘Podaj podstawę systemu k = ? ’) ;

Czytaj z ekranu ( k ) ;

Czytaj z ekranu ( k ) ;

i := 1 ;

i := 1 ;

et1:

et1:

j := 1 ;

j := 1 ;

et2:

et2:

m := ( i * j ) DIV k ;

m := ( i * j ) DIV k ;

r := ( i * j ) MOD k ;

r := ( i * j ) MOD k ;

A ( i , j ) := 10 * m + r ;

A ( i , j ) := 10 * m + r ;

jeżeli

jeżeli

j = k – 1

j = k – 1

wtedy wykonaj

wtedy wykonaj

skok do et3

skok do et3

w przeciwnym

w przeciwnym

przypadku

przypadku

blok2

blok2

j:= j + 1 ; skok do et2

j:= j + 1 ; skok do et2

koniec bloku2

koniec bloku2

et3:

et3:

jeżeli

jeżeli

i = k – 1

i = k – 1

wtedy wykonaj

wtedy wykonaj

blok3

blok3

Drukuj na ekranie ( ‘ tabliczka mnożenia ’) ;

Drukuj na ekranie ( ‘ tabliczka mnożenia ’) ;

dla

dla

i=1

i=1

aż do

aż do

k-1

k-1

wykonuj

wykonuj

dla

dla

j=1

j=1

aż do

aż do

k-1

k-1

wykonuj

wykonuj

blok4

blok4

Drukuj na ekranie (‘ A( ‘, i ,’ , ‘, j ,’ ) = ‘, A ( i , j ): 4:0 ) ;

Drukuj na ekranie (‘ A( ‘, i ,’ , ‘, j ,’ ) = ‘, A ( i , j ): 4:0 ) ;

koniec bloku 4

koniec bloku 4

skok do et4 ;

skok do et4 ;

koniec bloku 3

koniec bloku 3

i:= i + 1 ;

i:= i + 1 ;

Skok do et1 ;

Skok do et1 ;

et4 : czytaj 1 znak z ekranu ; stop ; { zatrzyma ekran }

et4 : czytaj 1 znak z ekranu ; stop ; { zatrzyma ekran }

Koniec bloku 1.

Koniec bloku 1.

***********************

***********************

*****

*****