Etapy rozwiązywania

problemu

1. Sformułowanie zadania
2. Określenie danych wejściowych
3. Określenie celu, czyli wyniku
4. Poszukiwanie metody rozwiązania, czyli

algorytmu

5. Przedstawienie algorytmu w postaci:

 opisu słownego
 listy kroków
 schematu blokowego

 języka programowania

6. Analiza poprawności rozwiązania
7. Testowanie rozwiązania dla różnych danych.

Ocena efektywności przyjętej metody.

Algorytm

dokładny przepis podający sposób

rozwiązania określonego zadania w

skończonej liczbie kroków;

zbiór poleceń odnoszących się do pewnych

obiektów, ze wskazaniem porządku, w

jakim mają być realizowane.

Algorytmika

podstawowy dział informatyki poświęcony

poszukiwaniom, konstruowaniu i badaniom

algorytmów, zwłaszcza w kontekście ich

przydatności do rozwiązywania problemów za

pomocą komputerów.

Algorytm liniowy

1. Wlać do garnka zimną wodę
2. Zapalić gaz
3. Gotować wodę do wrzenia
4. Włożyć jajko
5. Odczekać trzy minuty
6. Zgasić gaz
7. Wyjąć jajko

Gotowanie jajka

Algorytm z warunkiem

1. Wlać do garnka zimną wodę
2. Zapalić gaz
3. Gotować wodę do wrzenia
4. Włożyć jajko
5. Czy jako na twardo?

TAK: Odczekać 10 minut
NIE: Odczekać 6 minut

6. Zgasić gaz
7. Wyjąć jajko

Gotowanie jajka

Algorytm z warunkiem

1. Wlać do garnka zimną wodę
2. Zapalić gaz
3. Gotować wodę do wrzenia
4. Włożyć jajko
5. Włożyć jajko
6. Włożyć jajko
7. Czy jako na twardo?

TAK: Odczekać 10 minut
NIE: Odczekać 6 minut

8. Zgasić gaz
9. Wyjąć jajko

Gotowanie trzech jajek

Iteracja ograniczona

1. Wlać do garnka zimną wodę
2. Zapalić gaz
3. Gotować wodę do wrzenia
4. Wykonać trzy razy:

Włożyć jajko

5. Czy jako na twardo?

TAK: Odczekać 10 minut
NIE: Odczekać 6 minut

6. Zgasić gaz
7. Wykonać trzy razy:

Wyjąć jajko

Gotowanie trzech jajek

Iteracja nieograniczona

1. Wlać do garnka zimną wodę
2. Zapalić gaz
3. Gotować wodę do wrzenia
4. Włożyć ziemniaki
5. Odczekać 15 minut
6. Odczekać 1 minutę
7. Czy twarde?

TAK: powrócić do 6
NIE: przejść do 8

8. Zgasić gaz
9. Wyjąć ziemniaki

Gotowanie ziemniaków

Elementy schematu

blokowego

Skrzynki
graniczne:

START

STOP

Skrzynka
operacyjna:

x := 5

Skrzynka
wprowadzająca:

Podaj

x1, x2

Skrzynka
warunkowa:

x1 > 0

N

T

Schemat blokowy - sumowanie

dwóch liczb

START

STOP

wynik := a
+ b

Podaj

a , b

Drukuj

wynik

Wyliczanie reszty z dzielenia x przez

y

r < y

N

T

START

STOP

r := x

Podaj

x , y

Wypisz r

r :=
r-y

Sumowanie n

dowolnych

liczb

gdzie n > 0

i = n

N

T

START

STOP

s := s +
x

Wypisz s

i := i +
1

s := 0
i := 1

Podaj x

Podaj n

Programowanie

• projekt programu - konstrukcja

algotytmu,

• zapis programu w dowolnym języku

programowania,

• testowanie programu.

Język programowania

• zbiór zasad składni, instrukcji, dzięki

którym powstaje program możliwy do
wykonania,

• języki programowania ze względu na

sposób złożoności dzieli się na:



niskiego (asembler),



wysokiego (Turbo Pascal, C/C++, Java, Fortran,
Visual Basic)

poziomu.

Translatory

• interpretery
• kompilatory

• Pascal - strukturalny język programowania

stworzony przez N. Wirtha na początku lat
70,

• Turbo Pascal - opracowana przez firmę

Borland w połowie lat osiemdziesiątych XX w.
realizacja języka programowania Pascal,
wzbogacona o elementy niezbędne przy
wytwarzaniu oprogramowania, m. in.
możliwość modularyzacji i programowania
obiektowego oraz zaopatrzona w graficzną
bibliotekę wejścia-wyjścia.

Symbole podstawowe

• litery:

– A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q R, S, T,

U, V, W, X, Y, Z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p,
q r, s, t, u, v, w, x, y, z, _

• cyfry:

– 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

• znaki specjalne:

– odstęp (znak niewidoczny)

+ - * / = ^ < > ( ) [ ] { } . , : ; ‘
# $ @

• znaki sterujące: znaki o kodach ASCII od 0 do 31

małe i wielkie litery nie są rozróżniane (Pascal =

PASCAL)

Dwuznaki

• operator przypisania: :=
• operatory relacji: <>

<= >=

• zakres: ..
• nawiasy kwadratowe: (. .)
• nawiasy klamrowe: (* *)

Operatory

• arytmetyczne

+, -, *, /, DIV, MOD

• logiczne:

and, or, not

• relacyjne:

= , < , > , <> , <= , >= , in (jest

elementem)

Słowa kluczowe

and

file

nil

shr

array

for

not

string

asm

function

object

then

begin

goto

of

to

case

if

or

type

const

implementation packed

unit

constructor

in

procedure

until

destructor

inherited

program

uses

div

inline

record

var

do interface

repeat

while

downto

label

set

with

else

mod

shl

xor

end

Struktura programu

PROGRAM Nazwa_programu; {Nagłówek}
USES { Deklaracja Modułów }
{ Początek części opisowej }
LABEL

{ Deklaracja etykiet }

CONST

{ Deklaracja stałych }

TYPE

{ Deklaracja typów }

VAR

{ Deklaracja zmiennych }

PROCEDURE

{ Procedury }

FUNCTION {

Funkcje }

{ Koniec części opisowej }
BEGIN
Instrukcje { Część wykonawcza programu }:
END

.

Nagłówek programu

program identyfikator;

Przykłady:

program Funkcja;
program nasz_program;

Deklaracje modułów

uses lista-nazw-modułów

Przykłady:

uses Crt;
uses Dos, Printer;

Moduły standardowe

•

System - wszystkie procedury
standardowe),

•

Crt - obsługa ekranu, klawiatury,
głośnika),

•

Dos - wywołania systemowe MS-DOS,

•

Printer - obsługa drukarki,

•

OverLay - obsługa tzw. nakładek,

•

Graph - grafika,

•

Turbo3 - moduł "uzgadniający" z Turbo
Pascalem 3.0,

•

Graph3 - tzw. grafika żółwia, używana w
Turbo Pascalu 3.0.

Deklaracje etykiet

label lista-etykiet;

Przykłady:

label etykieta1;
label alfa, beta;

Deklaracje stałych

const identyfikator =
wyrażenie-stałe;

Przykłady:

const tekst = ‘komputer’;
const e = 2,718;

nazwisko = ‘Nowak’

Zmienna

dana, która może przyjmować różne

wartości w ramach typu przypisanego

lub określonego tej zmiennej

• globalne
• lokalne
nazwa zmiennej - ciąg liter lub cyfr

zaczynający się od litery

Np. a, kod_ucznia, x2, x_2

Deklaracje zmiennych

var lista-identyfikatorów : opis-
zmiennej;
Przykład:
var

i,j,k : Integer;

x,y : Real;

koniec : Boolean;
tab : array [1..10] of Real;

c a łk o w it y

z n a k o w y

lo g ic z n y

w y lic z e n io w y

o k r o jo n y

p o r z ą d k o w y

r z e c z y w is t y

p r o s ty

ta b lic o w y

r e k o r d o w y

p lik o w y

z b io r o w y

s t r u k t u r a ln y

w s k a ź n ik o w y

ła ń c u c h o w y

p r o c e d u r a ln y

o b ie k t o w y

T y p d a n y c h

Typy danych

Typy całkowite

Nazwa typu

Zakres

Liczba bajtów

– Byte

0..255

1

– ShortInt

-128..127

1

– Word

0..65535

2

– Integer

-32768..32767

2

– LongInt

-2147483648..2146483647 4

Przykład:
var x,y

: Integer;

i : Byte;

Typy rzeczywiste

Nazwa typu

Zakres

Liczba

bajtów

– Real

2.9E-39

.. 1.7E38

6

– Single

1.5E-45..4.0E38

8

– Double

5.0E-324..1.7E308

8

– Extended

3.4E-4932..1.1E4932

10

– Comp

-9.2E18..9.2E18

8

Przykład:
var x,y : Real;

Typ znakowy

Elementami tego typu są znaki ASCII, z
których każdy jest pamiętany w jednym bajcie
pamięci

identyfikator-zmiennej : Char;

Przykład:
var znak : Char;

Typ łańcuchowy

ciągi znaków (w tym spacje)

identyfikator-zmiennej : string [rozmiar]
rozmiar 0 .. 255 (gdy nie podano rozmiar =
255)

Przykład:
var nazwisko : string [20]

Typ logiczny

Elementami tego typu są dwie predefiniowane
stałe:

False - fałsz
True - prawda

identyfikator-zmiennej : Boolean;

Przykład:
var czy_koniec : Boolean;

Typ tablicowy

Tablica - ustalona liczba elementów tego samego typu

identyfikator-zmiennej = array [typy-indeksowe] of

typ-składowy

Przykłady:
var tab : array [0..20] of Integer;
var macierz : array [1..3,1..5] of Real;
(3 wiersze x 5 kolumn)

Typ rekordowy

Rekord - złożona struktura danych, której składowe zwane
polami mogą być różnych typów

identyfikator-typu : record [lista-deklaracji-pól] end;

Odwołanie do pola

zmienna-rekordowa.identyfikator-pola

Typ rekordowy

Przykład:
var data : record
rok

: Integer;

miesiac

: 1 .. 12;

dzien

: 1 .. 31;

end;
begin

data.rok:=3;
data.miesiac:=7;
data.dzien:=5

end.

Deklaracje typów

type identyfikator-typu = opis-
typu;

Przykłady:

type tekst = String;
type znak1 = Char;
i = Integer;

Typ wyliczeniowy

zbiory o małej liczbie elementów na których
nie dokonuje się operacji arytmetycznych

type identyfikator-typu

=

(lista_identyfikatorów);

Przykłady:
type pora_roku = (wiosna, lato, jesien, zima);
type student = (Adam, Ania, Wojtek);

Typ okrojony

ograniczenie zakresu wartości typów porządkowych

type identyfikator-typu

=

stała .. stała;

Przykład:
type tydzien = (poniedziałek, wtorek, środa,
czwartek,

piątek, sobota, niedziela);

dni_robocze = poniedziałek .. piątek;
type zakres = 0 .. 20;
type zakres = ‘A’ .. ‘K’;

Typ zbiorowy

zbiór wszystkich podzbiorów danego typu
porządkowego

type identyfikator-typu = set of typ-porządkowy;

Przykład:
type dni_robocze = set of (poniedzialek, wtorek,
sroda,

czwartek, piątek);

Typ rekordowy

type identyfikator-typu = record [lista-deklaracji-pól]

end;

Przykład:
type data = record
rok

: Integer;

miesiac

: 1 .. 12;

dzien

: 1 .. 31;

end;

var data_ur : data;

Typ plikowy

ciąg elementów tego samego typu, przy czym
liczba jego składowych jest zmienna

type identyfikator-typu = file of opis-typu-
elementów-pliku;

Przykład:
type dane = file of Integer;

wyniki = file of Real;

Zgodność typów

• zmiennej rzeczywistej można przypisać wartość

dowolnej zmiennej całkowitej lub rzeczywistej,

• zmiennej typu LongInt można przypisać dowolną

wartość typu całkowitego,

• zmiennej typu Integer, Word, Byte oraz ShortInt

można przypisać dowolną wartość całkowitą pod
warunkiem, że mieści się ona w zakresie danego
typu (obowiązek kontroli zakresu wyrażenia
spoczywa na programiście),

• zmiennej typu String można przypisać wartość

typu String lub Char.

Procedury i funkcje

Są to wyodrębnione części programu, stanowiące pewną

całość, posiadające jednoznaczną nazwę i ustalony

sposób wymiany informacji z pozostałymi częściami

programu

• Procedura - wykonanie pewnej sekwencji czynności,

polegających zwykle na obliczaniu jednej lub wielu
wartości.

• Funkcja - obliczenie jednej wartości (typu prostego lub

wskaźnikowego).

Instrukcje

• proste

– przypisania

{nadanie zmiennej nowej wartości}

– skoku {zmiana kolejności wykonywania instrukcji}
– pusta {brak działania}
– wywołania procedury {wywołanie procedury}
– „inline”{wywołanie instrukcji w kodzie maszyn.}

• strukturalne

– złożona{grupowanie instrukcji}
– iteracyjna

{wielokrotne wykonanie grupy instrukcji}

– warunkowa

{wybranie jednej z kilku instrukcji}

– wiążąca

{odwołania do pól rekordów}

Instrukcja przypisania

odwołanie-do-zmiennej :=
wyrażenie

Przykłady:
a:=1;
war_log:=True;
dane:='Jan'+'Nowak';
i:=i+1;
y:=2*x+(5-k)*i;

Instrukcja skoku

goto

etykieta

Przykład:

program skok;
label etyk1;
...
begin

...
goto etyk1;
...

etyk1: a:=a+1;

...

end.

Instrukcja złożona

begin

instrukcja-1;
...
instrukcja-n

end;

Przykład:

begin

x:=x+1;
y:=2;
a:=abs(x)

end;

Instrukcja warunkowa

„JEŚLI”

if wyrażenie then instrukcja1

if wyrażenie then instrukcja1

else instrukcja2

Przykład:

if a<b

then x:=1

else x:=2;

if x=y then a:=‘zero’
else if x>y then a:=‘dodatnia’

else a:=‘ujemna’;

czy

wyrażenie

prawdziwe

N

T

instrukcja
_2

instrukcja
_1

Instrukcja wyboru

case wyrażenie of

sekwencja-instrukcji
wyboru

end

lub

case wyrażenie of

sekwencja-instrukcji
wyboru

else instrukcja
end

Przykłady:

case znak of

‘+’ : x:=x+a;
‘-’ : x:=x-a

end

case wartosc of

1..4 : x:=‘malo’;
5..9 : x:=‘duzo’

end

Instrukcja iteracyjna

„DLA”

for zmienna:=wyrażenie_1 to wyrażenie_2 do instrukcja;
for zmienna:=wyrażenie_1 downto wyrażenie_2 do instrukcja;

Przykład:
{Suma liczb od 1 do 100}

suma:=0;
for i:=1 to 100 do suma:=suma+i;

{Wypełnienie tablicy 4 x 5 liczbą 10}

for i:=1 to 4 do
for j:=1 to 5 do
tab[i,j]:=10;

i <= w2

N

T

instrukc
ja

i := i +
1

i := w1

Instrukcja iteracyjna

„DOPÓKI”

while wyrażenie do instrukcja;

(najpierw sprawdza warunek, gdy spełniony powtarza)

Przykład:
{Pięć razy tekst

„Pascal”}
i:=1;
while i<6 do
begin
writeln(‘Pascal);
i:=i+1

end;

czy

wyrażenie

prawdziwe

N

T

instrukc
ja

Instrukcja iteracyjna

„POWTARZAJ”

repeat
instrukcja-1;
.......
instrukcja-n;
until wyrażenie;

(najpierw wykonuje, następnie sprawdza warunek; gdy spełniony kończy)

Przykład:

repeat

k:=k*k

until k>100

czy

wyrażenie

prawdziwe

N

T

instrukc
ja

Procedury wejścia-wyjścia

wczytywanie danych

Read (lista-zmiennych);
Readln (lista-zmiennych);

Przykłady:
Read (a);
Readln (k);
Read (a,b,c);

Procedury wejścia-wyjścia

wyprowadzanie wyników

Write (lista-argumentów-wyjściowych);
Writeln (lista-argumentów-wyjściowych);

Przykłady:
Write (a);
Writeln (‘x=‘,x);
Write (y:8:3);

program funkcja;
uses crt;
var a,b,x :real;
begin

clrscr;
write('a=');
read(a);
write('b=');
read(b);
if a=0

then write('Brak pierwiastków)

else begin

x:=-b/a;
writeln('x=',x);
end;

repeat until keypressed;

end.

PROGRAM NWP; { Największy wspólny podzielnik 2 liczb }
uses Crt;
var a, b

: Integer;

NWP : Integer;

begin
ClrScr;
repeat
writeln('Podaj 2 liczby naturalne');
readln(a,b);
until (a>0) and (b>0);
write('Najwiekszy wspolny podzielnik ',a,' i ',b,' = ');
while a<>b do { algorytm Euklidesa na NWP }
if a>b then a:=a-b
else b:=b-a;
writeln(a);
readln
end.

Funkcje arytmetyczne

• Abs

- wartość bezwzględna

• ArcTan

- arcus tangens

• Cos

- cosinus

• Exp - e do potęgi danej przez

argument

• Frac - część ułamkowa argumentu
• Int

- część całkowita argumentu

• Ln

- logarytm naturalny

• Pi

- 3,1415926535...

• Sin

- sinus

• Sqr

- kwadrat argumentu

• Sqrt - pierwiastek kwadratowy

Funkcje i procedury

porządkowe

• Dec (x,n) - zmniejszenie x o n lub o 1 gdy brak

n

• Inc (x,n) - zwiększenie x o n lub o 1 gdy brak n
• Odd (x) - test nieparzystości (wynik: True gdy

nieparzysta)

• Pred (x) - wartość poprzedzająca x w danym

typie

• Succ (x) - wartość następująca po x w danym

typie

Funkcje i procedury

łańcuchowe

• Concat (lista-łańcuchów) - łączenie łańcuchów,
• Copy (łańcuch,indeks,licznik)- wartością jest

łańcuch o

długości licznik wycięty z łańcucha

począwszy od znaku określonego przez indeks,

• Length (łańcuch)- długość łańcucha,
• Pos (podłańcuch,łańcuch) - pozycja podłańcucha w

łańcuchu,

• Delete (łańcuch,indeks,licznik) - usunięcie w

łańcuchu

liczby znaków określonych przez

licznik począwszy

od pozycji podanej przez

indeks,

• Insert (podłańcuch,łańcuch,indeks)- wstawienie

podłańcucha w łańcuch,

Funkcje i procedury

łańcuchowe

• Str (argument-numeryczny,zmienna-

łańcuchowa) - zamiana wartości numerycznej
na łańcuch,

• Val (łańcuch,zmienna-numeryczna,kod) -

zamiana wartości łańcuchowej na numeryczną
(jeżeli łańcuch nie przedstawia poprawnej
liczby to kod=pozycja pierwszego błędnego
znaku)

Przykłady:

x:=‘Jan Nowak’;
y:=Delete (x,6,6);

{y= Jan}

z:=Copy (x,5,5);
{z=Nowak}

Procedury i funkcje

Są to wyodrębnione części programu, stanowiące pewną

całość, posiadające jednoznaczną nazwę i ustalony

sposób wymiany informacji z pozostałymi częściami

programu

• Procedura - wykonanie pewnej sekwencji czynności,

polegających zwykle na obliczaniu jednej lub wielu
wartości.

• Funkcja - obliczenie jednej wartości (typu prostego lub

wskaźnikowego).

Funkcje i procedury

standardowe

• System - dostępny automatycznie, zawiera mi.in.

funkcje i procedury obsługi zbiorów, funkcje
konwertujące, arytmetyczne, wskaźnikowe,
porządkowe i sterujące

przydziałem pamięci;

• Dos - funkcje systemu operacyjnego (sterowanie

datą, czasem, wykonywanie programów);

• Crt - obsługa klawiatury i ekranu;
• Graph - obsługa grafiki ekranowej;
• Overlay - moduł umożliwiający dzielenie programu

na tzw. segmenty;

• Printer - moduł ułatwiający dostęp do drukarki;
• Turbo3, Graph3 - funkcje i procedury związane z

wersją 3.0;

Funkcje arytmetyczne

Abs - wartość bezwzględna

typ argumentu: rzeczywisty, całkowity
typ wyniku: rzeczywisty, całkowity
Przykład: x = Abs(-3) x=3

ArcTan - arcus tangens

typ argumentu: rzeczywisty, całkowity
typ wyniku: rzeczywisty
Przykład: x = ArcTan(1)

x=7,8539816340E-1 (radiany)

Cos - cosinus kąta podanego w radianach

typ argumentu: rzeczywisty, całkowity
typ wyniku: rzeczywisty
Przykład: x = Cos(1) x=5,4030230587E-1

Funkcje arytmetyczne

Exp - e do potęgi danej przez argument

typ argumentu: rzeczywisty, całkowity
typ wyniku: rzeczywisty
Przykład: x = Exp(2) x=7.3890560989E+00

Frac - część ułamkowa argumentu

typ argumentu: rzeczywisty, całkowity
typ wyniku: rzeczywisty
Przykład: x = Frac(-2.5)

x=-5.0000000000E-01

Int - część całkowita argumentu

typ argumentu: rzeczywisty, całkowity
typ wyniku: rzeczywisty
Przykład: x = Exp(-2.5)

x=-2.0000000000E+00

Funkcje arytmetyczne

Ln - logarytm naturalny

typ argumentu: rzeczywisty, całkowity (dodatni)
typ wyniku: rzeczywisty
Przykład: x = Ln(1)

x=0.0000000000E+00

Pi - Liczba Pi

typ argumentu: brak
typ wyniku: rzeczywisty
Przykład: x = Pi

x= 3,1415926536E+00

Sin - sinus kąta podanego w radianach

typ argumentu: rzeczywisty, całkowity
typ wyniku: rzeczywisty
Przykład: x = Sin(Pi/2)

x=1.0000000000E+00

Funkcje arytmetyczne

Sqr - kwadrat argumentu

typ argumentu: rzeczywisty, całkowity

(dodatni)

typ wyniku: rzeczywisty, całkowity
Przykład: x = Sqr(2,5)

x=6.2500000000E+00

Sqrt - pierwiastek kwadratowy z argumentu

typ argumentu: rzeczywisty, całkowity

(dodatni)

typ wyniku: rzeczywisty
Przykład: x = Sqrt(4)

x=2.0000000000E+00