INFORMATYKA
Programowanie
strukturalne
Dr Zdzisław Szczepanik
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,
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.
***********************
***********************
*****
*****