MATERIAŁY Cz I
Zbiór materiałów i zadań
do
ćwiczeń rachunkowych
z przedmiotu
„Metodyka i techniki programowania1”
Zagadnienia:
Reprezentowanie danych w komputerze. Systemy
kodowania danych. Operacje arytmetyczne
Algorytmy- sposoby prezentacji, rodzaje i złożoność
obliczeniowa algorytmów
WARSZAWA 2011
2
Tematy ćwiczeń rachunkowych
Tematy ćwiczeń:
Temat 1: Konwersje i zapis liczb w różnych systemach
Temat: 2 Kody ZM,U1,U2. Operacje arytmetyczne.
Temat: 3 Analiza problemu i specyfikacja algorytmu
Temat 4 i dalsze. Projektowanie algorytmów.
Temat Końcowy.
Kolokwium
Informacja o kolokwium zawarta jest w końcowej części materiału.
Uwaga 1 :
Liczba godz. ćwiczeń wynosi:
6- dla grup wojskowych;
8- dla niestacjonarnych;
14- dla grup stacjonarnych. Ćwiczenia dla tych grup stacjonarnych
są zaliczane na podstawie kolokwium końcowego realizowanego na
ostatnich ćwiczeniach..
Uwaga 2 :
Studenci grup wojskowych i niestacjonarnych ze względu na małą ilość
ćwiczeń będą rozliczani ze znajomości tej tematyki w ramach egzaminu
końcowego (w czasie sesji).
Warunkiem przystąpienia do egzaminu jest zaliczenie ćwiczeń
rachunkowych i laboratoryjnych
.
3
INFORMACJE
DOSTĘPNOŚĆ MATLABA
MATLAB jest oprogramowaniem płatnym. Oprogramowanie ma
licencję na czas studiów. Dla studentów cena 87 $. Ta wersja
zawiera też SIMULINK z niektórymi ToolBox’ami.
Dystrybucja firma: Oprogramowanie naukowo techniczne.
Kraków
WWW.ont.com.pl
Istnieją zbliżone wersje darmowe o nazwach: FreeMat, SCILAB,
(SCICOS odpowiednik SIMULINKA dla SCILABA)
Literatura
podstawowa:
W. Reichel, M. Stachurski, Matlab dla studentów, Witcom, Warszawa
2009r.
B. Mrozek, Z. Mrozek, Matlab i Simulink. Poradnik użytkownika,
2010
A. Kamińska, B. Pańczyk, Matlab. Przykłady i zadania, Mikon 2002
uzupełniająca:
M. Niedziela, Zbiór zadań z informatyki, Helion 2006
Matlab Help Printable documentation
R. Klempka, A. Stankiewicz, Programowanie z przykładami w języku
Pascal i Matlab, 2002
W. Regel , Przykłady i ćwiczenia w programie SIMULINK.
Wyd. MIKOM 2004
B. Mrozek, Z. Mrozek, MATLAB Leksykon kieszonkowy. Wyd. HELION
4
T1 i T2
REPREZENTACJA DANYCH W KOMPUTERZE
SYSTEMY KODOWANIA DANYCH
OPERACJE ARYTMETYCZNE
5
System pozycyjny zapisu liczb
Liczby w zapisie pozycyjnym (np. 239) są przedstawiane jako łańcuchy
cyfr (c
i
), czyli znaków przypisanych liczbom naturalnym:
c
i
∈
∈
∈
∈
{0,1,.., R-1}
Podstawą R pozycyjnego systemu liczenia jest ilość różnych symboli (cyfr)
dopuszczalnych na każdej pozycji zapisu liczby.
Natomiast rzeczywista wartość cyfry w liczbie zależy od jej pozycji zajmowanej
w łańcuchu cyfr. Np. cyfra 5 w liczbie 535 co innego znaczy na pozycji pierwszej
i ostatniej. Wartość liczby L jest suma cyfr mnożonych przez wagi odpowiednie
dla pozycji, na których te cyfry występują:
i
n
i
i
R
R
c
L
∗
=
∑
=0
)
(
(1)
gdzie: i – numery
pozycji na lewo od przecinka oddzielającego część całkowitą od części
ułamkowej( i=0, 1, ..n),
L
(R)
-wartość liczby w systemie o podstawie R w którym zapisana jest liczba
Jeśli omawiane są reprezentacje liczb w różnych systemach to podając wartość
liczby należy też zaznaczyć notację system np. 101
(d)
. Przy zapisie notacji
używane są litery bądź cyfry np. 8 –ósemkowy(lub litera q), h- heksadecymalny
(szesnastkowy), b-binarny, d-dziesiętny (lub 10) itp.
System dziesiętny-
Podstawa R=10 oraz
10 cyfr: c
i
∈
∈
∈
∈
{0,1,2,. . . ,9 },
Np. korzystając z wzoru (1) liczbę
32 875
10
można zapisać jako:
3x10000 + 2x1000 + 8x100 + 7x10 + 5x1
3 2 8 7 5
10
4
10
3
10
2
10
1
10
0
wagi kolejnych cyfr systemu
W podobny sposób można też przedstawić liczby Lu <1 tzn. liczby ułamkowe:
i
n
i
i
R
R
c
Lu
−
=
∗
=
∑
1
)
(
(2)
gdzie:
pozycje położone na prawo od przecinka mają w tej konwencji ujemne:
-1, -2,-3,... wartości wykładnika określającego wagę cyfry
Np. korzystając z (2) liczbę 0,
625
można przedstawić jako:
6
*10
-1
+
2
*10
-2
+
5
*10
-3
Korzystając z wzoru (1) można zapisać liczbę w dowolnym systemie tzn. o
różnych podstawach R i odczytać jej wartość w systemie dziesiętnym np.:
System „8”
(237)
8
=2*8
2
+ 3*8
1
+ 7*8
0
=159
(10)
System „4”
(233)
4
=2*4
2
+ 3*4
1
+ 3*4
0
= 47
(10)
6
Reprezentacja liczb całkowitych- kod binarny
Podstawą kodu binarnego jest podstawa R=2. W takim kodzie występują 2
cyfry: 0 i 1. Taki kod jest idealny do zapisu informacji w komputerze, bowiem
komputery rozróżniają tylko dwa stany: 0 i 1, które zawiera najmniejszą porcję
informacji nazywaną bitem [b]. Zwykle stosuje się większą jednostkę bajt [B].
Jeden bajt to 8 bitów. Naturalnym dla komputera systemem zapisu danych jest
system dwójkowy (binarny), lecz ze względów technicznych używa się także
systemów: szesnastkowego (heksadecymalny) i rzadziej- ósemkowego
(oktalny).
Każda liczba L może być zapisana na pewnej ilości n bitów a minimalną
ilość n niezbędną do zapisu liczby L (dziesiętnej) można wyznaczyć z
nierówności:
2
n
-1 ≥ L
(3)
Bitów może być oczywiście więcej niż n. Dlatego liczba n może być
zaokrąglona w górę do całkowitej wielokrotności 8- tak, aby była wyrażona
w bajtach. Np. jeśli L= 968 to analizując kolejno np. n=8, 9 spełnienie
relacji (3) nastąpi dopiero dla n=10 bo :
2
10
-1 ≥ 968
Czyli minimalna liczba bitów dla liczby 968 to n=10, zaokrąglając w górę -
potrzeba 2 bajty. Oczywiście może być też więcej bitów, wówczas na
niewykorzystanych bitach znajdują się zera.
W kodzie binarnym inaczej przedstawiane są liczby całkowite
nieujemne, a inaczej ujemne. Inaczej też zapisuje się liczby ułamkowe.
W przypadku liczb rzeczywistych (tzn. posiadających część całkowitą i
ułamkową) ich część całkowita jest zapisywana w postaci jednego ciągu
bitów a część ułamkowa w postaci drugiego ciągu.
W systemie o R=2 (dwójkowym, binarnym) są dwie cyfry: 0 i 1,
a kolejne
pozycje z n-pozycji liczby odpowiadają kolejnym potęgom liczby 2.
Np.: dla n= 4 ciąg 1 1 1 0
(2)
zawiera liczbę l*2
3
+1*2
2
+l*2
1
+0*2
0
= 14
(10)
Zakładając 1 bajt (tzn. n= 8) to oznaczenia i wagi bitów są następujące:
Nr bitu:
b
7
b
6
b
5
b
4
b
3
b
2
b
1
b
0
2
7
…….. 2
3
2
2
2
1
2
0
Wagi bitów: 128 64 32 16 8 4 2 1
Kod o takich wagach jest nazywany naturalnym kodem binarnym – NKB.
Bit b
o
-jest bitem najmniej znaczacym -LSB
(least significant bit),
a bit najstarszy tzn. b
n-1
- MSB
(most significant bit)
Największa liczba zapisana przy pomocy n bitów to Lmax= (2
n
–1)- stąd dla
n=8 Lmax=255 – co oznacza ze jedynki są na wszystkich bitach bajtu.
7
Zamiana liczby dziesiętnej ( całkowitej, dodatniej) na liczbę w
systemie binarnym- algorytm Hornera
Przykład 1.1
Dana jest liczba naturalna np. 108 zapisana w systemie dziesiętnym. Należy
znaleźć jej notację w systemie binarnym.
Sposób rozwiązania (jeden z możliwych):
Należy dzielić całkowicie przez dwa daną liczbę oraz zapisywać resztę
z dzielenia całkowitego. Otrzymane wartości reszt z dzielenia, zapisane w
kolejności odwrotnej dają zapis liczby w systemie binarnym. (na końcu
dzielenia otrzymujemy najbardziej znaczącą cyfrę binarną),
Rozwiązanie
Tabela 1. Zamiana liczby z systemu dziesiętnego na dwójkowy
Działanie
Wynik
Reszta
108:2
54
0
54:2
27
0
27:2
13
1
13:2
6
1
6:2
3
0
3:2
1
1
1:2
0
1
Sprawdzenie:
1101100
(2)
= l*2
6
+l*2
5
+0*2
4
+l*2
3
+l*2
2
+0*2
1
+0*2° = 64+32+8+4 =108
(10)
W podobny sposób można odczytać wartość dziesiętną ciągów
przedstawiających zapis binarny liczby rzeczywistej (nieujemnej) np.:
(101,
101
)
(2)
=1*2
2
+ 0*2
1
+ 1*2
0
+
1*2
-1
+ 0*2
-2
+ 1*2
-3
=5,625
Wynik:
1101100
(2)
8
Zamiana liczby dziesiętnej ( całkowitej, dodatniej) na binarną-
algorytm zachłanny
Liczbę całkowitą z systemu dziesiętnego można zamienić na NKB jeśli właściwie
oszacujemy niezbędną, minimalną liczbę n bitów (na podstawie nierówności (3))
Przedstawiony dalej algorytm dokonuje zamiany liczby X na postać binarną,
dobierając kolejno wagi binarne. Każdorazowo dobiera największą z możliwych
wag (stąd tego typu algorytm nazywa się zachłannym).
Algorytm zamiany metodą doboru wag
1) Nadać wszystkim n- bitom wartość 0.
2) znaleźć najmniejszą wartość n taką, aby zachodziła relacja:
2
n +1
> X ≥2
n
Nadać bitowi b
n
wartość b
n
=1.
3) Obliczyć różnicę Y=X- 2
n
Czy Y=0 ?
TAK: Przejdz do 4.
NIE: Podstaw X:=Y (czyli nowy X jest resztą). Przejdź do punktu 2.
4. Koniec.
Przykład:
Wykorzystując algorytm. Przedstaw w NKB liczbę 88
(10)
.
1. Przyjmujemy początkowo n=8 i X
(NKB)
=
0 0 0 0 0 0 0 0
2. Szukamy największego n aby 2
n+1
> 88 ≥ 2
n
Dla
n=7
jest (2
7
> 88 > 2
6
).
Czyli największą możliwą wagą jest 2
6
. Stąd bit
b
6
=1
;
3. Zostaje różnica Y=88-64=24 Ponieważ Y>0 to nowa wartość X=24
2. Szukamy największego n aby 2
n+1
> 24 ≥ 2
n
. Dla
n=4
jest (2
5
>24> 2
4
).
Czyli największą możliwą wagą jest 2
4
. Stąd
bit
b
4
=1
;
3. Zostaje różnica Y=24-16=8. Ponieważ Y>0 to X=8
2 Szukamy znów największego n aby 2
n+1
> 8 ≥ 2
n
. Dla
n=3
jest (2
4
>8 ≥ 2
3
).
Czyli największą możliwą wagą jest 2
3
. Stąd bit
b
3
=1
;
3. Zostaje różnica Y=8 -8=0
Ponieważ Y=0 to punkt 4.
4. KONIEC
Czyli otrzymujemy: 88
(10)
.= 0 1 0 1 1 0 0 0
9
Reprezentacja binarna- podstawowe operacje logiczne
W operacjach logicznych liczba binarna jest traktowana jako zbiór
pojedynczych cyfr binarnych.
Operacje na bitach
Negacja (NOT)
!1 = 0, !0 = 1 lub zapis (~1 = 0, ~0 = 1)
Koniunkcja (AND)
0 & 0 = 0, 1 & 0 = 0, 0 & 1 = 0,
1 & 1 = 1
Alternatywa (OR)
0 | 0 = 0,
1 | 0 = 1, 0 | 1 = 1, 1 | 1 = 1
Różnica symetryczna
XOR
0 ^ 0 = 0,
1 ^ 0 = 1, 0 ^ 1 = 1
, 1 ^ 1 = 0
Przykłady:
Jest różnica na najmłodszym
bicie!!!
10
Podstawowe operacje arytmetyczne dla liczb binarnych
Dodawanie
Liczby dwójkowe dodajemy podobnie, jak dziesiętne. Gdy po dodaniu dwóch
cyfr uzyskuje się wartość niemożliwą do zapisania pojedynczą cyfrą, zachodzi
tzw.
przeniesienie.
Odejmujemy wtedy od wyniku podstawę systemu, a do
następnej pozycji dodajemy 1 (np. 9+8=17-10) =7
(1)7
W przypadku liczb dwójkowych przeniesienie wystąpi już wtedy, gdy wynik
dodawania dwu cyfr jest większy od 1.
Reguły dodawania
:
Reguły odejmowania:
przeniesienie
pożyczka
11
Mnożenie i dzielenie
Przykłady
Mnożenie przez 2
w układzie binarnym - przesunięcie liczby o jedną pozycję
w lewo i dopisanie zera z prawej strony liczby.
Dzielenie przez 2
w układzie binarnym - przesunięcie liczby o jedną pozycję
w prawo i odrzucenie ostatniej cyfry (jeśli liczba parzysta to tą cyfrą jest
zero).
Przykład:
Mnożenie przez 10 w układzie dziesiętnym i przez 2 w układzie
dwójkowym.
Podobnie mnożenie i dzielenie w układzie dwójkowym przez 4 i inne potęgi
dwójki – można realizować jako przesunięcie w lewo (dla mnożenia) lub w
prawo (dla dzielenia) o odpowiednią liczbę pozycji.
12
System oktalny (ósemkowy)
W systemie ósemkowym (R=8) mamy do dyspozycji osiem cyfr (0, 1, 2,
...,7), a kolejne pozycje odpowiadają kolejnej potędze liczby 8.
Np. 407
(8)
= 4*8
2
+0*8
1
+7*8
0
= 4*64+7 = 256+7 = 263
(10)
Przykład 1.2 :
Dana jest liczba naturalna n = 197 zapisana w systemie dziesiętnym.
Należy znaleźć jej notację w systemie ósemkowym.
Sposób rozwiązania:
Należy daną liczbę dzielić całkowicie przez osiem oraz zapisywać resztę z
dzielenia całkowitego. Wartości reszty z dzielenia, zapisane w kolejności
odwrotnej, dadzą liczbę w systemie oktalnym.
Rozwiązanie
Tabela . Zamiana liczby z systemu dziesiętnego na ósemkowy
Działanie
Wynik
Reszta
197:8
24
5
24: 8
3
0
3:8
0
3
Wynik: 305
(8)
Sprawdzenie: 305
(8)
= 3*8
2
+0*8
1
+5*8° = 3*64+5 = 192+5 = 197
(10)
Przykład 1.3 Zamiana liczby oktalnej na binarną.
Dana jest liczba naturalna n = 604
(8)
zapisana w systemie ósemkowym. Należy
znaleźć jej notację w systemie binarnym.
Sposób rozwiązania:
Ponieważ podstawą systemu oktalnego jest liczba 8 (jej zapis wymaga 3 bitów), a
podstawą systemu binarnego jest 2, można zatem zamieniać reprezentację liczb w
tych systemach, zamieniając odpowiadające sobie cyfry (ciągi cyfr).
Tabela. Tabela konwersji z systemu oktalnego na binarny (i odwrotnie)
cvfra oktalna liczba binarna
0
000
1
001
2
010
3
011
4
100
5
101
6
110
7
111
Rozwiązanie
Należy zamienić cyfry z systemu oktalnego na ciągi cyfr w systemie binarnym.
Zamiana z systemu binarnego na ósemkowy wymaga postępowania odwrotnego
tzn. podziału na grupy 3 bitowe (od najmłodszego bitu) i przyporządkowania
każdej grupie cyfry ósemkowej :
110 000 100
(2)
604
(8)
Wynik: 305
(8)
6 0 4
(8)
110 000 100
Wynik:
110000100
(2)
13
System heksadecymalny
W systemie heksadecymalnym R=16 (szesnastkowym) mamy do dyspozycji 10
cyfr: (0, 1, 2,...,9) oraz sześć liter (A, B, C, D, E, F).
Wartości 10 odpowiada cyfra oznaczana jako A, 11
B, 12 C, 13 D, 14
E, 15
F. Kolejne pozycje liczby w tym systemie odpowiadają kolejnej potędze
liczby 16.
Np. 5C
(h)
= 5*16
1
+12*16° = 80+12 = 92
(l0)
Przykład 1.4. zamiana liczby dziesiętnej na heksadecymalną
Znaleźć notację
heksadecymalną liczby dziesiętnej N
= 107.
Sposób rozwiązania:
Należy daną liczbę dzielić całkowicie przez szesnaście oraz zapisywać resztę z
dzielenia całkowitego (reszty 10 i więcej zapisujemy jako cyfry A,B,C,D,E,F).
Rozwiązanie
Tabela . Zamiana liczby z systemu dziesiętnego na szesnastkowy
Działanie
Wynik
Reszta
107:16
6 (11) czyli B
6:16
0
6
Sprawdzenie:
6 B
(16)
=6*16
1
+
11*16
0
=96+ 11=107
(10)
Przykład 1.5. Zamiana liczby binarnej na heksadecymalną.
Dana jest liczba naturalna n =10010110011 zapisana w systemie binarnym.
Znajdź jej notację w systemie szesnastkowym.
Sposób rozwiązania:
Podstawą systemu jest 16 (2
4
- co wymaga 4 bitów) a binarnego 2, należy
więc podzielić ciąg bitów na grupy 4 bitowe i każdej przyporządkować
odpowiednią cyfrę systemu hex (wg tabeli).
Cyfra heksadec.
Liczba binarna
binarna
0
0000
1
0001
2
0010
3
0011
4
0100
5
0101
6
0110
7
0111
8
1000
9
1001
A
1010
B
1011
C
1100
D
1101
E
1110
F
1111
Na liczbach hex można wykonywać typowe operacje np.:
1B8
440
+ C7
199
2 7 F 639
Wynik:
107
(d)
= 6 B
(h)
Rozwiązanie:
Należy zamienić
czteroelementowe ciągi cyfr
z systemu binarnego na
cyfry w systemie
heksadecymalnym.
0100 1011 0011
4 B 3
4 B 3
4 B 3
4 B 3
Wynik:
4B3
14
Kod BCD(Binary Coded Decimal)
Kod dwójkowo - dziesiętny BCD służy do przedstawiania liczb całkowitych
bez znaku. W kodzie tym każda cyfra dziesiętna jest zakodowana dwójkowo na
4 bitach, według reguł kodowania binarnego (tabela).
Cyfra dziesiętna
Kod BCD
0
0000
1
0001
2
0010
3
0011
4
0100
5
0101
6
0110
7
0111
8
1000
9
1001
Kodowanie liczb ze znakiem
W układach cyfrowych stosowane są elementy dwustanowe, co wystarcza
do odwzorowania zapisu dwójkowego liczb naturalnych bez znaku,
(unsigned).
Dla liczb całkowitych (ze znakiem) trzeba dodatkowej umowy co do zapisu
znaku, a dla liczb rzeczywistych jest konieczność wskazania miejsca przecinka.
Problem liczb całkowitych (integer) rozwiązuje się za pomocą tzw. kodów
liczbowych stałopozycyjnych (fixed point), natomiast liczby rzeczywiste (real)
są zapisywane w specjalnych formatach zmiennopozycyjnych (floating point)
jako para liczb stałopozycyjnych.
Obecnie powszechnie stosowany jest tzw.
kod uzupełnień do 2
–
U2
{two's
complement), choć używano też kodu uzupełnień do 1 –
U1
i kodu znak-
moduł
ZM
{sign-magnitude). We wszystkich tych odwzorowaniach trzeba
brać pod uwagę wielkość kodu n (liczbę bitów), ponieważ od tego zależy postać
zakodowanej liczby - ta sama liczba może mieć różną postać zależn i e od tego, na
ilu bitach jest kodowana.
Kody U1,U2,ZM różnią się sposobem zapisu liczb ujemnych.
Liczby dodatnie mają we wszystkich kodach taki sam zapis.
Kody różnią się też, dla tego samego n, zakresem liczb. Przydatność
poszczególnych kodów wynika z łatwości (szybkości) wykonywania w nich
działań arytmetycznych, a w praktyce - dodawania.
15
Reprezentacja binarna ujemnych liczb całkowitych
Aby poszerzyć zakres liczb trzeba stosować bit znaku. Jest on cyfrą 0 lub 1
poprzedzająca pozostałe bity ciągu.
Przyjęto, że dla liczb ujemnych wartość
bitu znaku wynosi zawsze 1.
Do zapisu liczb ze znakiem stosuje się kody
oznaczane jako: ZM,U1 i U2. Należy podkreślić, że dodatnia liczba dziesiętna
x we wszystkich kodach jest reprezentowana tym samym ciągiem bitów, czyli
jest wyrażana w naturalnym kodzie binarnym (NKB). Bity o wartości 1 tego
ciągu określają wagi, których suma wyraża wartość x.
Natomiast jeśli x jest liczbą ujemną to ciąg bitów przedstawiający x jest w
każdym kodzie inny. Jedynym podobieństwem jest występowanie „1” na
najstarszym bicie (bicie znaku).
Kod znak- moduł (ZM)
Kod znak- moduł dla liczby x zapisywanej na n bitach jest definiowany
następująco:
x
jeśli x ≥ 0 - oznacza zapis x w NKB
x
ZM
=
2
n-1
+|x|
jeśli x < 0 - definicja dla zapisu a ujemnej
Przykład:
Zapisać liczbę –23 w kodzie ZM na n=8 bitach. Korzystając z definicji mamy:
2
n-1
=2
7
=128
1 0000000
|-23|=
+0 0010111
1 0010111
-23
ZM
Po binarnym dodaniu dwu składników otrzymujemy binarny ciąg
1 0010111
przedstawiający liczbę –23 w kodzie ZM.
W kodzie ZM na bicie MSB jest zapisany znak liczby, a na pozostałych bitach jej
moduł. Dla n bitów zakres liczb jest następujący:
[-2
n-1
-1 : 2
n-1
-1]
Przykładowo dla n=8 w kodzie ZM można zapisać liczby z zakresu: [-127: 127]
W kodzie ZM istnieją 2 postacie zera (ujemne i dodatnie)- co jest wadą kodu.
16
Kod z uzupełnieniem do jedynki- U1
Kod U1 dla liczby x zapisywanej na n bitach jest definiowany następująco:
x
jeśli x ≥ 0 - oznacza zapis x w NKB
x
U1
=
(2
n
–1)
-
|x|
jeśli x < 0 - definicja dla zapisu a ujemnej
Przykład:
Zapisać liczbę –23 w kodzie U1 na n=8 bitach. Korzystając z definicji mamy:
2
n
-1 =2
8
-1=255
1 1111111
|-23|=
-
0 0010111
1 1101000
-23
U1
Po binarnym odjęciu modułu od ciągu jedynek reprezentującego wartość (2n -1),
otrzymujemy ciąg 1 1101000
, przedstawiający –23 w kodzie U1.
Wymagane w definicji odejmowanie modułu liczby od ciągu n jedynek jest
niczym innym jak uzupełnieniem poszczególnych bitów modułu do jedynki.
Stąd nazwa kodu. Warto zauważyć, że:
a) zapisując moduł liczby ujemnej a następnie,
b) negując bit po bicie otrzymujemy liczbę ujemną zapisaną w kodzie U1.
Np. dla liczby x=-23 mamy:
Moduł
0 0010111
NOT
1 1101000
- 23
U1
W kodzie U1 na bicie MSB jest zapisany znak liczby, a na pozostałych bitach jej
moduł uzupełniony do „1”. Dla n bitów zakres liczb jest następujący:
[-2
n-1
-1 : 2
n-1
-1]
Przykładowo dla n=8 w kodzie U1 można zapisać liczby z zakresu: [-127: 127]
W kodzie U1 podobnie jak w ZM istnieją 2 postacie zera (ujemne i dodatnie)- co
jest wadą kodu.
17
Reprezentacja binarna ujemnych liczb całkowitych –kod U2
Standardowo w komputerach stosuje się kod U2 (uzupełnienie do 2).
Liczbę całkowitą x zapisuje się w kodzie U2 na n bitach następująco:
Sposób A wg wzoru:
x
jeśli x ≥ 0 - oznacza zapis a w kodzie binarnym (NKB)
x
u2
=
2
n
-
|x|
jeśli x < 0 - definicja dla zapisu a ujemnej
Przykład:
Zakodować na n=8 bitach liczbę -22.
Sposób A wg powyższego wzoru
1 etap
Zamieniamy na postać binarną liczby: 2
n
(czyli 256) i 22.
b
8
b
7
b
6
b
5
b
4
b
3
b
2
b
1
b
0
Wagi bitów:
256
128 64 32 16 8 4 2 1
2
n
=
1
0 0 0 0 0 0 0 0
22
(10)
=
-
0 0 0 1 0 1 1 0
2 etap.
Wykonujemy powyższe odejmowanie czyli
2
n
-|a|
. Sczegółówo zostało to
przedstawione w tabelce poniżej:
Pożyczka
1
1
1
1
1
1
1
Dziesiętnie
2
n
1
0
0
0
0
0
0
0
0
|22|
-
0
0
0
1
0
1
1
0
-22
u2
1
1
1
0
1
0
1
0
256
- 22
234
NKB
b
7
b
6
... ... .... b
2
b
1
b
0
gdzie: kolor zielony bit znaku
Jeśli dane tzn n=8 i a=-22 podstawimy do wzoru to mamy:
2
n
-|a| =2
8
-|22| =256-22=234
(10)
Czyli liczbie –22 w kodzie U2 odpowiada w NKB liczba dziesiętna 234, co
można sprawdzić dekodując ostatni wiersz (potraktowany jako zapis w NKB):
1* 2
7
+ 1* 2
6
+ 1* 2
5
+ 1* 2
3
+ 1*2
1
= 128+64+32+8+2=234
Liczba 234 jest tu uzupełnieniem modułu liczby ujemnej do liczby 256.
Stąd wywodzi się nazwa kodu.
18
Sposób B
Liczbę całkowitą a zapisuje się w kodzie U2 na n bitach następująco:
x jeśli x ≥ 0
-2
(n-1)
+|x| jeśli x < 0 i x >- 2
(n-1)
Przykład zastosowania sposobu B:
Pierwszy składnik dla n=8 wynosi –128 i
jest to waga bitu znaku.
Stąd dla liczby X=-22 mamy: x=
2
(n-1)
+a=2
7
+(-22)=128-22=106.
Liczba 106 powinna być zapisana na bitach
b
6
b
5
b
4
b
3
b
2
b
1
b
0
Nr bitu b
7
b
6
b
5
b
4
b
3
b
2
b
1
b
0
waga
- 128 64 32 16 8
4
2
1
-22
u2
1
1
1
0
1
0
1
0
Interpretacja
-128
106
= -22
(10)
Z ostatniego wiersza wynika:
Sposób C
Liczbę całkowitą a zapisuje się w kodzie U2 na n bitach wg następującego
algorytmu:
I. jeśli a ≥ 0 to liczbę a zapisujemy w NKB,
II. jeśli a < 0 to:
a. zapisujemy w NKB moduł liczby a,
b. negujemy bit po bicie (uzupełnienie do U1),
c. do najmniej znaczącego bitu tzn b
0
dodajemy 1.
Przykład zastosowania sposobu C:
Zakodować na n=8 bitach liczbę -22.
Ponieważ liczba jest ujemna postępujemy wg punktu II.
Nr bitu
b
7
b
6
b
5
b
4
b
3
b
2
b
1
b
0
waga
128
64 32 16 8 4 2 1
| 22
(10)
|
0
0
0 1
0 1 1 0 Punkt IIa
Negacja
1
1
1 0
1 0 0 1 Wynik punktu IIb
+
1 Punkt IIc
Wynik:
1
1
1 0
1 0 1 0 Liczba -22
(u2)
W wyniku postępowania bit znaku
b
7
przyjmuje wartość 1, co oznacza liczbę
ujemną.
X=
19
W tabeli niżej pokazano liczby charakterystyczne dla 8-bitowego U2 oraz
dla porównania ich reprezentacje binarne w kodach: ZM i U1.
n= 8
ZM
U1
U2
-127
1 1111111 1 0000000 1 0000001
-126
1 1111110
1 0000001 1 0000010
…………..
………
-2
1 0000010
1 1111101 1 1111110
-1
1 0000001
1 1111110 1 1111111
Zero
0 0000000
1 0000000
1 1111111
0 0000000
0 0000000 jedna postać
+1
0 0000001
0 0000001 0 0000001
+2
0 0000010
0 0000010 0 0000010
…………..
+126
0 1111110
0 1111110 0 1111110
+127
0 1111111
0 1111111 0 1111111
Dla n bitów zakres liczb w U2 jest następujący:
[-2
n-1
: 2
n-1
-1]
czyli dla n=8 mamy zakres
: [-128, 127]
(zakres niesymetryczny)
Arytmetyka stałoprzecinkowa
W poniższej tabeli przedstawiono operacje dodawania liczb dodatnich
przedstawionych w różnych kodach.
Wartości
dziesiętne
Wartości w ZM,U1,U2
(reprezentacje 8-bitowe)
Wartości w kodzie BCD- 9
bitów: bit znaku + 2 tetrady
89
+ 45
+134
0
1011001
+
0
0101101
(1) 0 0000110
(1)- oznacza przeniesienie,
czyli , że wynik jest > 128
Zatem wynik jest: 128 + 6
0
1000 1001
+
0
0100 0101
0
1100 1110
korekcja +
0110 0110
0
0010 0100
przen. z I tetrady + (1)
(1)
0011 0100
otrzymujemy:
100
+
3 *10 + 4
bo przen. z II tetrady ma wagę 100
Kiedy w kodzie BCD jest
korekcja
– gdy po dodaniu wyniki tetrad(y) są > od
liczby 9.
Trzeba wtedy do każdej tetrady w której przekroczono zakres kodu BCD dodać
liczbę 6
.
20
W kolejnej tabeli przedstawiono odejmowanie liczb w różnych kodach
.
War
-tości
Kod ZM
(5-bitów)
U1
U2
BCD
9
- 7
+ 2
0
1001
-
0
0111
0 0010
0
1001
+1 1000
(1) 0 0001
+ 1
0 0010
0
1001
+1 1001
(1) 0 0010
W U2 przeniesienie
jest ignorowane
0
1001
- 0 0111
0 0010
W kodzie
ZM i BCD
:
• znak liczby wynika ze znaku większego modułu
• od większego modułu odejmujemy mniejszy.
W kodzie U1
operacja odejmowania jest zastąpiona operacją dodawania
wszystkich pozycji łącznie z bitem znaku i uwzględnieniem powstałego
przeniesienia. Oznacza to konieczność korekcji polegającej na dodaniu 1 do
najmniej znaczącej pozycji wyniku.
W kodzie U2
podobnie jak w U1 operacja odejmowania jest zastąpiona
operacją dodawania wszystkich pozycji łącznie z bitem znaku, ale nie ma
potrzeby korekcji. Przeniesienie jest ignorowane. Ten algorytm jest
najszybszy.
21
Operacje na liczbach w kodzie U2- przykłady
Należy zrealizować operacje:
a) 96 –16 co jest tożsame 96 + (-16)
b) 16 – 96
c) –16 +(-96)
Ad a) Zamieniamy liczby 96 i –16 na kod U2 i dodajemy te liczby.
Nr bitu
b
7
b
6
b
5
b
4
b
3
b
2
b
1
b
0
waga
znak 64 32 16 8 4 2 1
Przeniesienie
(1)
1
1
Przeniesienie jest
ignorowane
96
(u2)
0
1
1
0 0 0 0 0
-16
(u2)
+
1
1
1
1 0 0 0 0
Wynik w U2 :
0
1
0
1 0 0 0 0 80
(10)
W wyniku operacji otrzymujemy wartość w NKB – świadczy o tym wartość bitu
b7=0. Przeniesienie
(1)
przekracza przyjęty zakres n=8 bitów i jest ignorowane.
Ad b) Zamieniamy liczby 16 i –96 na kod U2 i dodajemy.
Nr bitu
b
7
b
6
b
5
b
4
b
3
b
2
b
1
b
0
waga
znak 64 32 16 8 4 2 1
Przeniesienie
16
(u2)
0
0
0
1 0 0 0 0
-96
(u2)
+
1
0
1
0 0 0 0 0
Wynik w U2:
1
0
1
1 0 0 0 0 -80
(10)
W wyniku operacji otrzymujemy wartość w U2 bo składniki były w U2. Wartość
jest ujemna, bo świadczy o tym wartość bitu b7=1.
Czyli wynik jest: -2
7
+ (wynik w NKB na 6 bitach)=-128+48=-80
(10).
Lub inaczej określamy moduł:
2
8
- (wynik z 8 bitów interpretowany w NKB)=256-176=80
(10).
Ponieważ o znaku wyniku świadczy b7=1 stąd wynik=-80
(10).
Ad c) Zamieniamy liczby -16 i –96 na kod U2 i dodajemy te liczby.
Nr bitu
b
7
b
6
b
5
b
4
b
3
b
2
b
1
b
0
waga
znak 64 32 16 8 4 2 1
Przeniesienie
(1)
1
1
-16
(u2)
1
1
1
1 0 0 0 0
-96
(u2)
+
1
0
1
0 0 0 0 0
Wynik:
1
0
0
1 0 0 0 0
-112
(10).
W wyniku operacji otrzymujemy wartość ujemną w U2 – świadczy o tym wartość bitu b7=1.
Czyli wynik jest: -2
7
+ (wynik w NKB na 6 bitach)=-128+16=-112
(10).
22
Reprezentacja liczb rzeczywistych
Przy reprezentacji liczb ułamkowych w komputerze nie można formalnie
wykorzystać przecinka (bo mogą być tylko zera i jedynki). W praktyce określa się
ilość miejsc przeznaczoną na część całkowitą i ułamkową liczby, dzięki czemu
wiadomo, jakiej wartości odpowiada dana pozycja. Np. liczba rzeczywista jest
reprezentowana na 4 bajtach z czego:
część całkowita to 2 bajty.
część ułamkowa to 2 bajt
Należy podkreślić, że ułamki z systemu dziesiętnego podaje się w notacji
binarnej najczęściej z określoną dokładnością (jako liczby przybliżone).
Dokładność ta jest większa od wartości ostatniej pozycji przeznaczonej na zapis
liczby. Przedstawiając np. liczbę 0,3 na 5 bitach, zapiszemy ją jako:
0 01001
(2)
= 0,28125
(10)
.
Różnica pomiędzy 0,28125 a 0,3 wynosi 0,01875, co jest mniejsze od
2
-5
= 0,03125.
Ułamki dodatnie w kodzie binarnym
W systemie dziesiętnym kolejne pozycje po przecinku odpowiadają kolejnej,
ujemnej potędze liczby 10.
0.546 = 5*10
-1
+ 4*10
-2
+ 6*10
-3
W systemie binarnym kolejne pozycje po umownej pozycji położenia
przecinka oznaczają kolejne ujemne potęgi liczby 2. Aby w zapisie
uwidocznić, że jest to ułamek stosuje się czasem poprzedzającą spację np:
0 1011 = 1*2
-1
+ 1*2
-3
+ 1*2
-4
=0.5 + 0.125 +0.625=0.6875
Czasami też można spotkać zapis z przecinkiem:
, 1011
Przykład: Zapisać w kodzie binarnym liczbę 0,1875
Algorytm polega na mnożeniu liczby przez 2 i wyodrębnianiu zer i jedynek jako
części całkowitej wyniku. Najstarszy bit wynika z pierwszego mnozenia
Działanie Wynik Cz. Ułamk. Cz. Całk.
0,1875*2 (0),375 0,375
0
0,375*2
(0),75
0,75
0
0,75*2
(1),5
0,5
1
0,5*2
(1)
0
1
0 *2
(0)
0
0
itp
Od chwili gdy mnożymy przez zero zawsze
część całkowita będzie zerem – czyli kolejne bity
nigdy nie będą 1, a to oznacza że nie wnoszą
żadnej informacji
Sprawdzenie: 0 0011 = 1*2
-3
+1*2
-4
= 0,125 +0,0625=0,1875
Liczba ułamkowa jest tu reprezentowana dokładnie.
Wynik:
0,1875 =0 0011
Tu wystarczą 4 bity
na część ułamkową !
23
Przykład: Zapisać w kodzie binarnym liczbę 0,1675
Działanie Wynik Cz. Ułamk. Cz. Całk.
0,1675*2
(0),335 0,335
0
0,335*2
(0),67
0,67
0
0,67*2
(1),34
0,34
1
0,34*2
(0),68
0,68
0
0,68 *2
(1),36
0,36
1
0,36 *2
(0),72
0,72
0
0,72*2
(1),44
0,44
1
0,44*2
(0),88
0,88
0
0,88*2
(1),76
0,76
1
itp
Tu kolejne bity wnoszą dodatkową informację, bo
niektóre z nich są jedynkami
Tu reprezentacja liczby 0,1675 nie jest dokładna i zależy od liczby
uwzględnionych bitów i tak przy uwzględnianiu n bitów różnica ∆ między
wartością zapisaną a rzeczywistą spełnia nierówność:
∆ < 2
-n
np. dla n=4 ∆ = 0.0425 <2
-4
(bo 0.0425 <0,0625)
Liczba bitów
Wartość zapisana
Różnica ∆
4
0,125
0.0425
5
0,15625
0,01125
6
0,15625
0,01125
7
0,16406
0,00344
itp
Wniosek:
1 Liczby ułamkowe mogą nie być dokładnie reprezentowane przez
rozwinięcie binarne,
2 Większa liczba bitów zapewnia generalnie większą dokładność
przybliżenia ułamka.
Np.: Dla liczby
0,1875 =0 0011
Wystarczą 4 bity na dokładne reprezentowanie ułamka.
24
Zapis liczby rzeczywistej bez znaku w kodzie binarnym
Przykład: Zapisać w kodzie binarnym liczbę 34,75
(10)
Tabela Zamiana liczby 34 NKB
Działanie Wynik Reszta
34 :2
17
0
17 : 2
8
1
8 : 2
4
0
4: 2
2
0
2:2
1
0
1:2
0
1
Tabela Zamiana liczby 0,75 na kod bin.
Działanie Wynik Cz. Ułamk. Cz. Całk.
0,75 *1
1,5
0,5
1
0,5 *2
1
0
1
100010 11
Stąd dodatnią liczbę rzeczywistą 34,75
(10)
można zapisać binarnie jako:
34,75
(10) =
100010 11
Sprawdzenie: 2
5
+2
1
+2
-1
+2
-2
=32 +2 +0.5 + 0.25= 34,75
Wynik:
Część całkowita liczby 34,75
(10)
34
(10)
= 1 0 0 0 1 0
Wynik:
Część ułamkowa
liczby 34,75
(10)
0,75= 0 11
,,,,
25
Reprezentacja ułamków w kodzie U2
Kod U2 umożliwia reprezentację zarówno dodatnich jak i ujemnych liczb
rzeczywistych. Stosowany jest powszechnie bowiem ułatwia operacje
matematyczne.
Ułamki dodatnie w kodzie U2 zapisuje się w postaci ciągu bitów o wartościach 0
lub 1 w którym jedynki wskazują na kombinacje wag, które po zsumowaniu
tworzą liczbę ułamkową . Wagi są kolejnymi ujemnymi potęgami liczby 2
zaczynając od n= -1.
Ułamki ujemne w kodzie U2 koduje się wg wzoru:
2 –X
’
gdzie: X
’
– notacja binarna ułamka dodatniego
Przykład: Zapisać w U2 X=-0,1875
Etap 1. Określenie wartości binarnej X
’
Działanie Wynik Cz. Ułamk. Cz. Całk.
0,1875*2 0,375 0,375
0
0,375 *2 0,75
0,75
0
0,75 *2 1,5
0,5
1
0,5 *2 1
0
1
Etap 2 Odjęcie binarne 2 –X
’
Pożyczka
1
1
1
1
1
2
1
0
,
0
0
0
0
X
’
-
0
0
0
1
1
-0,1875
(U2)
1
1
1
0
1
wagi
2
-1
2
-2
2
-3
2
-4
Pola na prawo od pionowej, kolorowej linii oznaczają bity części ułamkowej.
Jak sprawdzić poprawność otrzymanej wyżej reprezentacji tzn. że :
-0,1875
(U2)
=
1
1101 ?.
Można obliczyć 2- |-0. 1875|=1.8125
Czyli jeśli kodujemy liczbę ujemną -0,1875
(U2)
to powinna być zakodowana
w NKB liczba 2- 0,1875= 1.8125. Część całkowita jest tu równa 1, a w
interpretacji zapisu jako liczby w U2 ta „1” symbolizuje znak.
X
’
=0 0011
26
Można też sprawdzić poprawność otrzymanej wyżej reprezentacji tzn. że :
-0,1875
(U2)
=
1
1101
wykonując binarne odejmowanie 2 –X
’’
(gdzie X
’’
jest otrzymanym zapisem
binarnym ułamka X w kodzie U2)
Pożyczka
Operacja
1
1
1
1
1
2
1
0
,
0
0
0
0
X
’
-
1
1
1
0
1
|-0,1875|
=
0
0
0
1
1
Sprawdzenie: 1* 2
-3
+ 1*2
-4
= 0,125 +0,0625 = 0, 1875
Czyli otrzymany tu wynik jest modułem kodowanego ułamka.
Reprezentacja liczb rzeczywistych w kodzie FP2
W kodzie FP2 (floating point– kod zmiennoprzecinkowy) liczba jest zapisywana
w postaci w2ykłaqdniczej tzn. wg wzoru:
L=(–1)
S
•
m
•
P
C
gdzie: P– podstawa systemu liczenia, m– mantysa, c– cecha
s– wartość bitu znaku („1” -oznacza +, „0”- znak -)
Poniższa tabela przedstawia strukturę 16 bitowego kodu FP2:
znak
cecha
mantysa
bit
15
14
13 12 11 10
9
8
7
6
5
4
3
2
1
0
waga
s
-16 8
4
2
1
2
-1
2
-2
2
-3
2
-4
2
-5
2
-6
2
-7
2
-8
2
-9
2
-10
27
Przykład 1
Przedstawić liczbę 125.75 w kodzie FP2.
Szukamy n takiego, że 125.75<2
n
i mnożymy liczbę przez 2
n
i bierzemy
część całkowitą liczby.
125.75 * 2
7
= 125.75*128=16096
(liczba parzysta)
16 096 : 2
0
8 048 : 2
0
4 024 : 2
0
2 012 : 2
0
1 006 : 2
0
503 : 2
1
251 : 2
1
125 : 2
1
62 : 2
0
31 : 2
1
15 : 2
1
7 : 2
1
3 : 2
1
1 : 2
1
0
Otrzymujemy:
1 1 1 1 1 0 1 , 1 1 0 0 0 0 0 czyli 125,75
Przesuwamy przecinek w lewo, tak aby był po najbardziej znaczącej
jedynce – tu o 6 miejsc :
1 ,
1 1 1 1 0 1 1 1 0 0 0 0 0
cecha będzie
2
6
Czyli mamy:
L= (1 + 0.96484375)* 2
6
=125,75
Czyli liczbę w FP2 możemy zapisać następująco:
125,75 = (
0
00110 1111011100) FP2
L=
(1 +
0.96484375
)
*
2
6
=125,75
Wartość liczby L jest w tym przypadku dokładna, ale w ogólnym przypadku
liczba jest przedstawiana z pewnym przybliżeniem.
Pierwsze 7 bitów – to część całkowita,
dalsze 7 ułamkowa
Ale to jest dopiero reprezentacja binarna
liczby ułamkowej a nie liczby w kodzie
FP2!!!
Po przesunięciu o 6
pozycjiczęść ułamkowa to:
0.96484375
mantysa=0.96484375
cecha= 6
28
Dekodowanie liczby zapisanej w kodzie FP2
Rozkodujemy teraz z powrotem liczbę w kodzie FP2 np:
(
0
01010
1111000000
)
FP2
Posłuży do tego przedstawiona wcześniej w tabelce struktura kodu FP2.
L=(–1)
S
•m • P
C
gdzie: podstawa P=2
m– mantysa,
c– cecha
s– wartość bitu znaku
Rozpatrując kolejne elementy, otrzymujemy:
s = 0
, a więc mamy: (-1)
0
m = 1111000000
, a więc mamy: 2
-1
+ 2
-2
+ 2
-3
+ 2
-4
c = (01010)
U2
= 10
, a więc mamy
2
10
Składając to razem zgodnie z wzorem, otrzymujemy:
(-1)
0
* (
2
0
+ 2
-1
+ 2
-2
+ 2
-3
+ 2
-4
) *
2
10
=2
10
+ 2
9
+ 2
8
+ 2
7
+ 2
6
= 1024 + 512 +
256 + 128 + 64 = 1984
Widać tu, że zakodowanie liczby w takim a nie innym systemie FP2, za pomocą
określonej ilości bitów przeznaczonych na cechę i na mantysę spowodowało
ograniczenie dokładności do pewnej liczby miejsc po przecinku (tym już
przesuniętym). Stąd utrata dalszej części liczby.
Składnik
2
0
odpowiada jedynce przed przecinkiem, którą
zapamiętaliśmy i nie zapisaliśmy w zakodowanej liczbie,
oszczędzając jeden bit. Nie wolno o niej zapomnieć podczas
rozkodowania liczby.
Precyzja liczby zapisanej w kodzie FP2 zależy od ilości bitów
przeznaczonych na mantysę
Zakres liczby zależy od ilości bitów przeznaczonych na cechę.
29
Arytmetyka zmiennoprzecinkowa
Operacje arytmetyczne na liczbach zmiennoprzecinkowych wykonywane są
zgodnie z regułami, z tym że wynik zapisywany jest również w postaci cecha –
mantysa.
Jeżeli (np. w systemie dziesiętnym P=10) określimy dwie liczby A i B tak, że :
A
c
A
m
A
10
∗
=
oraz
B
c
B
m
B
10
∗
=
oraz przyjmiemy, że
B
A
c
c
d
−
=
to:
B
A
c
B
d
A
c
c
m
m
B
A
B
≥
∗
±
∗
=
±
dla
10
)
10
(
A
B
c
d
B
A
c
c
m
m
B
A
A
≥
∗
∗
±
=
±
−
dla
10
)
10
(
)
(
10
B
A
c
c
B
A
m
m
AB
+
∗
=
B
A
c
c
B
A
m
m
B
A
−
∗
=
10
Np.: A=2230 = 0,223E
4
B=125 =0,125E
3
C
A
> C
B
d= C
A
-C
B
=4-3=1
A+B=(0,223E
4
+0.125)E
3
=(2,23+0,125)E
3
=2,355E
3
=0,2355 E
4
W podobny sposób możemy zapisywać operacje dodawania, odejmowania,
mnożenia i dzielenia jeśli przyjmiemy, że podstawą jest P=2 a nie 10 –jak
powyżej.
30
Kodowanie informacji tekstowej
Do kodowania informacji tekstowej wykorzystuje się
kod
ASCII (American Standard Code for Information Interchange).
W tym kodzie znaki są:
•
zapisywane w jednym bajcie, można w ten sposób zakodować 256 różnych
znaków
•
ASCII obejmuje:
– 26 małych liter alfabetu łacińskiego
– 26 dużych liter alfabetu łacińskiego
– 10 cyfr
– spacje
– znaki specjalne, np. ! "#$% &
– znaki sterujące (kody ASCII od 0 do 31), np. przejdź do nowego wiersza
(oznaczenie LF od Line Feed), powrót karetki do początku wiersza (CR, od słów
Carriage Return), tabulator, koniec tekstu (EOT, od słów End of Text)
•
kody ASCII powyżej 127 to tzw. zestaw rozszerzony; zapisuje się w nim znaki
narodowe i znaki semigrafiki symbole np. pozwalające tworzyć na ekranie ramki
itp.)
Obecnie do użytku wprowadzany jest nowy sposób kodowania znaków o nazwie
UNICODE. Jest to 16-bitowy standard, w którym jest miejsce na wszystkie alfabety
narodowe, dotychczas jeszcze niezbyt powszechny. W przyszłości pozwoli on na
uniknięcie niedogodności związanych z ograniczoną pojemnością kodu ASCII i
koniecznością instalowaniem stron kodowych.
31
Tabela. Kody znakowe ASCII
Dec Hex Bin Znak
Dec Hex Bin Znak
Dec Hex Bin Znak
0
00 0000000 NUL ' 0'
1 01 0000001 SOH
2 02 0000010 STX
3 03 0000011 ETX
4 04 0000100 EOT
5 05 0000101 ENQ
6 06 0000110 ACK
7 07 0000111 BEL '\a'
8 08 0001000 BS '\b'
9 09 0001001 HT '\t'
10 0A 0001010 LF '\n'
11 0B 0001011 VT '\v'
12 0C 0001100 FF '\f'
13 0D 0001101 CR '\r'
14 0E 0001110 SO
15 0F 0001111 SI
16 10 0010000 DLE
17 11 0010001 DC1
18 12 0010010 DC2
19 13 0010011 DC3
20 14 0010100 DC4
21 15 0010101 NAK
22 16 0010110 SYN
23 17 0010111 ETB
24 18 0011000 CAN
25 19 0011001 EM
26 1A 0011010 SUB
27 1B 0011011 ESC
28 1C 0011100 FS
29 1D 0011101 GS
30 1E 0011110 RS
31 1F 0011111 US
32 20 0100000 spacja
33 21 0100001 !
34 22 0100010 ``
35 23 0100011 #
36 24 0100100 $
37 25 0100101 %
38 26 0100110 &
39 27 0100111 '
40 28 0101000 (
41 29 0101001 )
42 2A 0101010 *
43 2B 0101011 +
44 2C 0101100 ,
45 2D 0101101 -
46 2E 0101110 .
47 2F 0101111 /
48 30 0110000 0
49 31 0110001 1
50 32 0110010 2
51 33 0110011 3
52 34 0110100 4
53 35 0110101 5
54 36 0110110 6
55 37 0110111 7
56 38 0111000 8
57 39 0111001 9
58 3A 0111010 :
59 3B 0111011 ;
60 3C 0111100 <
61 3D 0111101 =
62 3E 0111110 >
63 3F 0111111 ?
64 40 1000000 @
65 41
1000001 A
66 42 1000010 B
67 43 1000011 C
68 44 1000100 D
69 45 1000101 E
70 46 1000110 F
71 47 1000111 G
72 48 1001000 H
73 49 1001001 I
74 4A 1001010 J
75 4B 1001011 K
76 4C 1001100 L
77 4D 1001101 M
78 4E 1001110 N
79 4F 1001111 O
80 50 1010000 P
81 51 1010001 Q
82 52 1010010 R
83 53 1010011 S
84 54 1010100 T
85 55 1010101 U
86 56 1010110 V
87 57 1010111 W
88 58 1011000 X
89 59 1011001 Y
90 5A 1011010 Z
91 5B 1011011 [
92 5C 1011100 \ '\\'
93 5D 1011101 ]
94 5E 1011110 ^
95 5F 1011111 _
96 60 1100000 `
97
61 1100001 a
98 62 1100010 b
99 63 1100011 c
100 64 1100100 d
101 65 1100101 e
102 66 1100110 f
103 67 1100111 g
104 68 1101000 h
105 69 1101001 i
106 6A 1101010 j
107 6B 1101011 k
108 6C 1101100 l
109 6D 1101101 m
110 6E 1101110 n
111 6F 1101111 o
112 70 1110000 p
113 71 1110001 q
114 72 1110010 r
115 73 1110011 s
116 74 1110100 t
117 75 1110101 u
118 76 1110110 v
119 77 1110111 w
120 78 1111000 x
121 79 1111001 y
122 7A 1111010 z
123 7B 1111011 {
124 7C 1111100 |
125 7D 1111101 }
126 7E 1111110 ~
127 7F 1111111 DEL
32
Reprezentacja kolorów i kodowanie grafiki
Reprezentacja kolorów
•
Różne częstości światła widzialnego mają różne barwy.
•
Każdą z nich można uzyskać łącząc 3 kolory: czerwony, zielony i niebieski
(
system RGB
).
•
RGB jest stosowany w telewizji, monitorach komputerowych.
•
Do druku stosuje się system odbiciowy.
•
Biały papier odbija wszystkie barwy, czarny pochłania wszystkie.
•
Barwniki pochłaniają wybrane barwy, odbijają pozostałe.
•
System CMY: barwniki cyan (sinoniebieski), magenta (purpurowy), yellow żółty).
•
Suma C+M+Y teoretycznie daje barwę czarną, w praktyce nieładny,
ciemnobrązowy kolor.
•
Dlatego: CMYK (dodatkowo czarny barwnik), ale obrazy kodowane w CMYK’u nie
wyglądają ładnie monitorze.
Kodowanie grafiki 2D
•
Grafika rastrowa:
• obraz złożony z kropek (pikseli), zwany bitmapą,
• barwa każdego piksela kodowana na określonej ilości bitów,
• 8 bitów – 256 kolorów, 16 bitów – 65536 kolorów, 24 bity – 16.8 milionów kolorów
(tzw. true color),
• większa ilość bitów stosowana wtedy, gdy obraz ma podlegać obróbce (np.
wydobyciu niewidocznych szczegółów)
• przy powiększaniu rozmiarów bitmapy jakość się pogarsza,
•
formaty rastrowe:
GIF, PNG, JPEG, TIFF,
GIF (Graphics Interchange Format), 8 bitów, bezstratna kompresja
umożliwia animację, (ale tylko 256 kolorów),
tworzenie GIF-ów wymaga opłat licencyjnych, dlatego stworzono format
zastępczy: PNG (Partable Network Graphics)
• PNG koduje obrazy na 1-49 bitach, bezstratna kompresja
• JPEG (Joint Photographic Experts Group)-zaletą jest 24 bitowe kodowanie oraz
kompresja z utratą danych (im gorsza jakość, tym mniejszy plik wynikowy; w
praktyce stosuje się parametr jakości 75, JPEG może zapisać kolory w systemie
RGB lub CMYK;
33
•
Grafika wektorowa:
– Obraz złożony z wektorów (odcinek kodują współrzędne początku, końca
i barwa),
– okrąg: współrzędne środka, promień i barwa
– grafikę wektorowa można przeskalowywać bez utraty jakości,
– rysunek w formacie wektorowym zajmuje znacznie mniej miejsca, niż w postaci
bitmapy, ale zdjęcia lepiej zapisywać jako bitmapy,
– programy pracujące z bitmapami często nazywają się malarskimi (np.
PaintShopPro), grafiką wektorową - rysunkowymi (np. CorelDraw);
•
Grafika 3D
- przedstawiana na płaszczyźnie jako rzut 3 wymiarowej sceny;
zaawansowane techniki pozwalają na zmianę projekcji, na „poruszanie się” w
prezentowanej przestrzeni (np. gry komputerowe, standardem w Internecie jest
format VRML (Virtual Reality Markup Language);
•
Animacja
- formaty MPEG, QuickTime, AVI.
34
T3
ALGORYTMY- SPOSOBY PREZENTACJI
RODZAJE ALGORYTMÓW
ZŁOZONOŚĆ OBLICZENIOWA
PRZYKŁADY PROJEKTOWANIA ALGORYTMÓW
35
Algorytm
Algorytm to sposób (schemat) postępowania prowadzący do rozwiązania danego,
problemu. Lub mówiąc inaczej algorytm to skończony ciąg operacji na obiektach (mogą
to być np. liczby, relacje między liczbami typu a>b, teksty) ze ściśle ustalonym
porządkiem wykonywania, dający możliwość realizacji zadania z określonej klasy.
Algorytm w sensie informatycznym wykorzystuje określone dane o zdefiniowanych
strukturach (np. liczby całkowite, rzeczywiste, zespolone, tablice jedno i wielowymiarowe,
rekordy itp ) i daje określone wyniki.
Algorytm powinien posiadać cechy:
Poprawność – dla każdego zestawu poprawnych danych wyniki powinny być
poprawne;
Skończony- dla każdego zestawu poprawnych danych algorytm powinien dawać
poprawne wyniki po skończonej liczbie kroków,
Określoność – z algorytmu musi wynikać jednoznacznie jaka ma być realizowana
następna operacja,
Efektywność- algorytm powinien realizować zadanie przy możliwie najmniejszej
liczbie kroków,
Uniwersalność- powinien rozwiązywać nie tylko specyficzne zadanie ale całą
klasę zadań.
Algorytm można zapisać w postaci:
Opisu słownego,
Listy kroków,
Schematu blokowego (flow diagram, flow chart),
Pseudokodu
Opis słowny
algorytmu jest ogólną ale mało precyzyjną formą prezentacji . Niesie ona
ryzyko niejednoznaczności przy złożonych algorytmach. Stosuje się ją dla
zasugerowania rozwiązania. Popularnym sposobem jest lista kroków postępowania.
Kroki stanowią opis operacji i są zazwyczaj mieszaniną sformułowań matematycznych i
języka naturalnego. Kolejność kroków jest zgodna z opisem. Wyjątkiem jest operacja
przejścia do wskazanego kroku lub też zakończenia algorytmu.
Schemat blokowy
(sieć działań) składa się z symboli graficznych w których opisywane
są operacje algorytmu. np.
zmiany kolejności kroków.
Kształty figur oraz strzałek do
rysowania
schematów
blokowych można znaleźć w
Wordzie (rys. ) na pasku
Rysowanie
wybierając
Autoksztalty (jeśli pasek nie
jest
widoczny
można
go
aktywować
z
menu
WidokPaski Narzędzi
Rysowanie).Stosuje się różne kształty symboli dla rozróżnienia operacji. Następstwo
operacji określają strzałki. Jest doskonałą komunikacją między „zleceniodawcą” a
programistą. Jednak złożone problemy trudno jest przedstawić przy pomocy tego typu
schematów. Dlatego stosuje się różne poziomy szczegółowości (od ogółu do szczegółu-
schemat zstępujący ).
36
Pseudokod
jest wygodną formą prezentacji algorytmów. Bazuje na opisie w języku
zbliżonym do bardzo ogólnej formy języka programowania (np. typu Pascal). Występują
tu bardzo uproszczone formy opisu operacji wprowadzania i wyprowadzania danych. W
opisach algorytmów przy wykorzystaniu pseudokodu stosuje się typowe nazwy instrukcji
występujące w niektórych językach wysokopoziomowych jak np:
If (warunek) then instrukcja1
else instrukcja2
for zmienna:=war_poczatkowa step war_kroku until war_koncowa do
instrukcja lub blok instrukcji,
W powyższym zapisie pierwsza konstrukcja zmienia sterowanie kolejności wykonywania
instrukcji (kroków). Drugi z zapisów określa tzw. pętlę, która pozwala na wielokrotne
powtarzanie wykonania określonych instrukcji. Pętla for jest stosowana jęśli dokładnie
wiadomo ile razy ma nastąpić powtarzanie. Jeśli liczba powtórzeń nie jest znana to
stosowane są inne konstrukcje pętli np. pętla typu:
while (warunek) do
instrukcja lub blok instrukcji
. Wówczas badany jest pewien warunek logiczny i tylko w przypadku jego prawdziwości
następuje kolejne wykonanie pętli.
Wśród algorytmów wyróżnia się:
sekwencyjne – instrukcje wykonywane kolejno, ale mogą też wystąpić ewentualne
rozgałęzienia,
iteracyjne- to algorytmy w których pewne grupy instrukcji są wykonywane
wielokrotnie (ściśle zadaną liczbę razy lub wynikającą z przebiegu obliczeń),
rekurencyjne- to algorytmy które wywołują same siebie dla zmieniających się
danych
Algorytm powinien posiadać specyfikację gdzie określamy dane z jakich algorytm
korzysta oraz wyniki które powinien dawać, a także niezbędne zmienne pomocnicze.
W algorytmach mogą również występować wyrażenia które są zbudowane ze
zmiennych, stałych, operatorów (np. +, - , *, /) i funkcji matematycznych. Wyrażenia
mogą też przybierać postać wyrażeń warunkowych. Wówczas do ich budowy
wykorzystywane są operatory relacyjne (np. =, >, <, <=, >=, <>).
W algorytmach występują często tzw. operacje przypisania (np. x:=x +5), określające,
że obliczona wartość wyrażenia z prawej strony zostanie podstawiana pod zmienną ze
strony lewej.
37
Przykład sformułowania prostego algorytmu:
Zadanie
Sformułuj algorytm obliczający pole prostokąta. Zapisz algorytm w postaci listy
kroków, schematu blokowego i pseudokodu.
ETAPY
a) Specyfikacja algorytmu:
Dane wejściowe:
a-
pierwszy bok, liczba rzeczywista dodatnia- w cm,
b-
drugi bok, liczba rzeczywista dodatnia- w cm.
Wynik
: p –pole prostokąta (w cm
2
)
Lista kroków:
K1: Wczytaj wartość pierwszego boku i podstaw pod zmienną a,
K2: Wczytaj wartość drugiego boku i podstaw pod zmienną b,
K3: Oblicz pole wg wzoru p=a*b i podstaw pod zmienną p
K4: Wyświetl wynik p
b) Pseudokod:
Program pole {nagłówek}
zmienne
a,b,p: real {deklaracja zmiennych}
begin {początek właściwego programu}
czytaj (a) {wczytanie danych}
czytaj(b)
p:=a*b {obliczenia}
wyświetl( p) {wyświetl wynik}
end {koniec właściwego programu}
c) Schemat blokowy:
d) Zapis w języku programowania
( np. Pascal)
Start
Wprowadź: a
Wprowadź: b
Oblicz: p :=a*b
Pisz:”Pole wynosi P=” p
Stop
program pole
var
a, b, p: real;
begin
readln(a);
readln(b);
p:=a*b;
write(’Pole P= ’,p:4:2,’ cm2’)
end.
38
Rozwiązanie danego problemu przy zastosowaniu odpowiednio przygotowanego
programu komputerowego wymaga realizacji wielu etapów projektowych i
uruchomieniowych. Problem ten przedstawiono na poniższym rysunku, zakładając, że
dotyczy to programu komputerowego obliczającego pole prostokąta.
Na rysunku pokazano drogę od problemu, który wymaga rozwiązania do programu
komputerowego rozwiązującego problem, przy założeniu, że potrafimy poprawnie
sformułować algorytm. Pętle sugerują, że niektóre etapy będą powtarzane z powodu
różnego rodzaju błędów, których trudno uniknąć przy bardziej złożonych problemach.
Pierwsza grupa błędów wynika zwykle z błędnych zapisów algorytmu w języku
programowania. Druga grupa dotyczy błędów wykonania wynikających z
niepoprawności algorytmu lub niewłaściwego kodowania w danym języku. Aby
skompilować program (tzn. przetłumaczyć go na ciąg rozkazów w zapisie zero-
jedynkowym zrozumiałym dla komputera) to musi on być całkowicie zgodny ze
standardem danego języka (tu Pascala). Ale uzyskanie programu poprawnego
językowo nie musi oznaczać, że poprawnie rozwiązuje problem. Stąd może ponownie
wynikać konieczność zmiany jego wersji źródłowej – co pokazuje większa pętla.
Czasami również będzie konieczność jej rozszerzenia tzn. zmiany algorytmu.
Program
komputerowy
2. Testowanie –
usuwanie błędów
logicznych
Algorytm
Algorytm
Algorytm
Algorytm
rozwiązania
rozwiązania
rozwiązania
rozwiązania
Problem !
Wykonanie programu
Program
źródłowy
Wyniki
Dane
Start
Wprowadź: a
Wprowadź: b
Oblicz: P:=a*b
Pisz:”Pole i P=” P
Stop
program pole
var
a, b, p: real;
begin
readln(a);
readln(b);
p:=a*b;
write(’Pole P= ’,p:4:2,’ cm2’)
end.
Kompilacja
1
. Uruchamianie
(usuwanie błędów
językowych)
39
Prezentacja algorytmów i ich analiza
W niżej przedstawionym algorytmie pokazano iteracyjne powtarzanie niektórych
kroków oraz sposób jego analizy.
Przykład:
Znaleźć największy wspólny dzielnik (NWD(n,m) ) liczb całkowitych m i n
Najbardziej znanym algorytmem rozwiązującym ten problem jest algorytm Euklidesa (ok.
300r p.n.e.).
Specyfikacja
Dane: m, n – liczby całkowite, Założenie: n
≥ m
Wynik: NWD(n,m)
Algorytm:
K1. Podziel n przez m. Niech r będzie resztą z dzielenia.
K2. jeśli r=0 to wynikiem jest m. KONIEC.
K3. Wykonaj:
n:=m m:=r
Przejdz do K1
Przykład: 1 NWD(n=12, m=6)
K1. n/m=12/6= 2 r=0
K2 r=0 . Stąd m=6 jest poszukiwaną liczbą tzn. NWD(12,6)=6
Przykład: 2 NWD(n=12, m=8)
K1. n/m=12/8= 1 r=4
K2 r≠0 .
K3 n:= 8 m:=4
K1 n/m=8/4=2 r=0
K2 r=0 . Stąd m=4 jest . czyli NWD(12,8)=4
Przykład: 3 Określ NWD(n=44, m=16)
K1. n/m=44/16= 2 r=12
K2 r≠0 .
K3 n:= 16 m:=12
K1 n/m=16/12=1 r=4
K2 r≠0 .
K3 n=12 m=4
K1 n/m=3 r=0
Dla dobranych wariantów danych algorytm daje poprawne wyniki.
40
Reprezentacja blokowa algorytmu NWD
Na poniższym rysunku przedstawiono schemat blokowy algorytmu NWD(n,m) z
iteracyjnym powtarzaniem kroków. Na rysunku przedstawiono typowe oznaczenia
graficzne stosowane w schematach blokowych dla zaznaczenia:
Początku i końca algorytmu,
Operacji związanych z wprowadzaniem danych i wyprowadzaniem wyników,
Wykonywania operacji obliczeniowych i przypisywania wartości,
Sterowaniem kolejnością wykonania instrukcji,
Powtarzaniem wybranych działań w algorytmie.
Wykorzystana tu operacja n mod m jest wyjaśniona dalej.
NIE
TAK
W Wordzie elementy graficzne
występują w zakładce :Rysuj
Autokształty: Schematy blokowe,
Strzałki blokowe
START
KONIEC
Wprowadz: n,m
a := n
b:=m
r≠0
n := m
m := r
Wypisz:
NWD(
a,b
)= m
r:= n mod m
Kształty Wejścia/
Wyjścia
Instrukcje
przypisania
Podjęcia decyzji
(sterowanie)
41
Operacja „MODULO”
Można zdefiniować dodawanie, odejmowanie i inne operacje, tzw. "modulo". Są one
istotne w w teorii algorytmów i metodach szyfrowania. Niech n mod m oznacza
standardową „operację modulo. Z definicji:
n mod m =n-((n div m)*m)
gdzie: div- dzielenie całkowite np. 365 div 7 =52
( zwykłe dzielenie daje 365/7= 52.14285)
stąd np: 365 mod 7 = 365 – 52*7 = 365 – 364= 1
Inny zapis:
m
m
n
n
m
n
−
=
mod
gdzie:
m
n
- podłoga z dzielenia liczb n i m.
Zapis
x
czytamy: Dla dowolnej liczby rzeczywistej x
x
(czytaj: „podłoga x” ) oznacza
największą liczbę całkowitą mniejszą lub równą x. Zapis
x
(czytamy „sufit x”) oznacza
najmniejszą liczbę całkowitą większą lub równą x. Dla wszystkich liczb rzeczywistych:
1
1
+
<
≤
≤
<
−
x
x
x
x
x
Dla każdej liczby całkowitej n:
n
n
n
=
+
2
/
2
/
Dzielenie modulo
Jeżeli dzielimy dwie liczby całkowite to często wynikiem jest
ułamek.
Część ułamkowa wynika z reszty dzielenia całkowitego dwu dzielonych liczb.
Aby określić jaka zostanie reszta (jako liczba integer) stosuje się dzielenie modulo.
Np wynikiem operacji modulo 7/2 będzie liczba 1, bo część całkowita dzielenia [7/2]=3 a
reszta r = 7 – 3* 2= 1.
. Jeżeli wynikiem dzielenia jest liczba całkowita np: 4/2=2, to wynikiem dzielenia modulo
jest 0 (4 % 2=0). W ten sposób bada się np. parzystość liczby.
Przykłady operacji modulo .
16 mod 16 = 0 10 mod 16 = 10 17 mod 16= 1 20 mod 16 = 4
42
Czas wykonania programu a złożoność obliczeniowa.
Niech będzie dany pewien algorytm A o którym przyjmiemy założenia:
•
czas wykonania operacji elementarnej wynosi 1µs,
•
czas wykonania algorytmu (liczba operacji) jest proporcjonalny do
pewnej funkcji matematycznej
W tabeli przedstawiono czasy wykonania programów dla algorytmów różnej
klasy
.
Rozmiar danych (wartość n w algorytmie)
Klasa
algorytmu
10
20
30
40
50
n
0,000 01s
0,000 02s
0,000 03s
0,000 04
0,000 05
n
2
0,000 1s
0,000 4s
0,000 09s
0,001 6s
0,002 5s
n
3
0,001s
0,008s
0,027s
0,064s
0,125s
2
n
0,001s
1,0s
17,9min
12,7dni
35,7
lat
3
n
0,59s
58min
6,5
lat
3855
wieków
2*10
6
wieków
n
!
3,6s
756
wieków
8,4*10
6
wieków
9,6*10
48
wieków
2,6*10
66
wieków
Algorytmy ocenia się na podstawie różnych kryteriów zależnych od okoliczności ich
stosowania. Zazwyczaj istotna jest prostota i „elegancja”, czas działania, dokładność
obliczeń (dla algorytmów numerycznych). Często wybór algorytmu jest kompromisem
między np. prostotą a efektywnością. Algorytmy prostsze są łatwiejsze do
zrozumienia, implementacji programowej i testowania, ale zwykle ich czas realizacji
jest dłuższy. Bardziej efektywne algorytmy są zwykle bardziej skomplikowane.
Wymagają stosowania bardziej złożonych technik programowania np. rekurencji.
Podstawowymi zasobami każdego algorytmu są :
czas wykonania,
wielkość zajmowanej pamięci
.
Analiza algorytmu polega na określeniu niezbędnych zasobów do jego wykonania.
Należy uwzględnić też jego poprawność, prostotę i użyteczność praktyczną. Analiza
kilku algorytmów dla danego problemu pozwala zwykle na wybór najlepszego pod
względem czasu jak i pamięci.
Wielkość zasobów komputerowych potrzebnych do wykonania algorytmu
określa się mianem
złożoności obliczeniowej.
Dla wielu algorytmów czas ich
wykonania i wielkość pamięci powiększa się gdy wzrasta wielkość zestawu danych.
Dlatego często złożoność obliczeniowa traktowana jest jako funkcja zależna od
rozmiaru danych wejściowych, nazywanego rozmiarem problemu lub zadania, który
jest liczbą całkowitą wyrażającą wielkość zestawu danych. Na przykład w problemie
sortowania za rozmiar problemu przyjmuje się liczbę elementów ciągu wejściowego,
a przy wyznaczaniu wyznacznika macierzy- liczbę wierszy i kolumn.
Pozostaje jeszcze kwestia określania jednostki złożoności obliczeniowej. W
przypadku złożoności pamięciowej za jednostkę przyjmuje się komórkę pamięci.
W zależności od kontekstu może to być bajt lub inna jednostka pamięci zajmowanej
przez wartość typu prostego. Np. dla algorytmów działających na zmiennych typu
real, jest to zwykle 8 bajtów.
W przypadku złożoności czasowej w algorytmie wyróżnia się charakterystyczne
operacje o tej własności, że całość wykonanej przez algorytm pracy jest
proporcjonalna do liczby tych operacji. Są to operacje dominujące. Np. w algorytmie
sortowania liczb taką operacją jest porównanie dwu elementów ciągu wejściowego i
ich ewentualne przestawienie, a w algorytmach obliczania wyznacznika macierzy-
operacje arytmetyczne +,*,- /.
43
Jednostką miary złożoności czasowej jest wykonanie jednej operacji dominującej.
Zaletą tak zdefiniowanej złożoności jest jej uniwersalność i niezależność od:
szybkości procesora,
cech języka programowania i umiejętności programisty.
Złożoność czasowa staje się miarą jego efektywności czasowej, a własności
algorytmu zależą tylko od niego i rozmiaru danych.
W rzeczywistości nie jest zupełnie prawdą ponieważ czas wykonania algorytmu np.
sortowania może się różnić dla danych o tym samym rozmiarze. Np.
w posortowanym ciągu wejściowym nie wystąpią przestawienia elementów, a gdy
jest odwrotnie posortowany liczba przestawień jest największa. Stąd czasami bierze
się pod uwagę tylko operacje porównania.
Do oceny złożoności czasowej algorytmów wykorzystuje się pewne notacje, które
mówią jak wygląda ta złożoność obliczeniowa jeśli liczba danych „n” rośnie.
Najczęściej stosowaną jest notacja O duże
. Celem stosowania tej notacji jest
pokazanie charakteru wzrostu złożoności obliczeniowej (np. liniowa, kwadratowa,
logarytmiczna).
Oto przykłady najważniejszych rodzajów złożoności algorytmów
n
Rodzaj złożoności
Przykład
O(1)
Stała
Dostęp do elementu tablicy
O(logn)
logarytmiczna
Przeszukiwanie binarne
0(n)
liniowa
Przeszukiwanie sekwencyjne
O(nlogn)
Liniowo-logarytmiczna
Sortowanie kopcowe
0(n
2
)
kwadratowa
Sortowanie bąbelkowe
O(n
3
)
sześcienna
Mnożenie macierzy
O(2
n
)
wykładnicza
Algorytm plecakowy
Wieże Hanoi
O(n
!
)
wykładnicza
Generowanie permutacji
Gdzie: O(…) tzw notacja O duże określająca złożoność
obliczeniową algorytmu
Jest oczywistym, że złożoność obliczeniowa przekłada się na czas
obliczeń na konkretnej platformie sprzętowej (komputerze).
44
Analiza algorytmu przeszukiwania sekwencyjnego
Problem przeszukiwania ( lub też wyszukiwanie) jest określany następująco:
Dane:
x
element
i
a
tablicy
w
a
a
a
liczb
n
Ciąi
n
[]
,
,
,
2
1
K
Wynik: Należy stwierdzić czy liczba x jest w tablicy a. Inaczej mówiąc należy
znależć
Indeks „k” taki, że x=a
k
lub przyjąć ze k=–1, gdy x nie ma w ciągu
Najprostszy algorytm zwany jest przeszukiwaniem sekwencyjnym (sequential
search), polega na przeglądaniu kolejnych elementów ciągu i kończy się, gdy
poszukiwany element zostanie znaleziony lub cały ciąg zostanie przeszukany.
Algorytm można zapisać następująco:
Function SEQUENTIAL-SEARCH(a[1..n],x)
1
for k:=1 to n do
2
if x=a[k] then
3
return k
4
return –1
Można powiedzieć złożoność algorytmu zależy gdzie w tablicy znajduje się
szukany element” – jeśli w ogóle jest!
Operacjami dominującymi w algorytmie są porównania. Ich liczba jest równa
liczbie wykonań pętli for. Najlepszy przypadek jest jeśli x jest pierwszym
elementem ciągu, a najgorszy gdy ostatnim lub nie występuje. Zatem:
W(n)=T(n)=n -(przypadek Worst)
B(n)=T(1)=1 (przypadek Best)
Stosując notację O duże:
T(n)=W(n)=O(n)
W ocenie algorytmów bardziej istotne są oceny pesymistyczne,
czyli najdłuższe czasy działania dla dowolnych danych rozmiaru n z
powodu, że:
•
Algorytm nie będzie działał dłużej,
•
Przypadek pesymistyczny jest częsty np. brak inf. w bazie,
Przypadek „średni” - często zbliżony do pesymistycznego
Przeanalizujmy przypadek średni. Założymy że prawdopodobieństwo zdarzenia ,
że
x
występuje w ciągu wynosi
p
, oraz że jeśli w nim występuje to
prawdopodobieństwo zdarzenia, że występuje na pozycji
k
wynosi
p/n
, a
prawdopodobieństwo zdarzenia, że nie występuje w ciągu wynosi
(1-p)
.
Zatem p-stwo
p
k
zdarzenia
ω
k,
że algorytm wykona
k
porównań przy poszukiwaniu
wartości
x
wynosi:
W każdym obiegu pętli
for
sprawdza się czy element
tablicy jest równy
szukanemu elementowi
x
(wiersz2) . Jeśli tak jest
zwracana jest wartość
indeksu
k
(wiersz 3)
45
)
(
)
1
(
1
,
,
2
,
1
(
n
k
p
n
p
n
k
n
p
p
k
=
−
+
−
=
=
K
Przypadek
k=n
oznacza:
• Element x jest na pozycji n (ostatniej),
• Lub element x nie występuje, ale żeby to stwierdzić trzeba przejrzeć
wszystkie elementy od 1 do n.
Stąd p
k
dla k=n jest sumą zdarzeń.
Niech
X
n
oznacza zmienną losową, której wartościami są liczby porównań
wykonywanych przez algorytm dla danych rozmiaru
n:
( )
)
,
,
2
,
1
(
n
k
k
X
k
n
K
=
=
ω
Jej wartość oczekiwana wynosi:
( )
( )
(
)
(
)
(
) ( )
2
2
1
1
2
1
1
1
1
1
1
p
p
n
p
n
n
n
n
p
p
n
k
n
p
p
n
n
p
k
p
X
X
E
n
k
n
k
n
k
k
k
n
n
+
−
=
−
+
+
=
=
−
+
=
−
+
=
=
∑
∑
∑
=
=
=
ω
Ostatecznie średnia A(n) (Average) liczba porównań w algorytmie przy założeniu,
że p-stwo wystąpienia poszukiwanego elementu wynosi
p
, jest określona
zależnością:
( )
( )
2
2
1
p
p
n
X
E
n
A
n
+
−
=
=
Na podstawie tej zależności rozpatrzmy przypadki:
Jeśli
p=1,
tzn.
x
na pewno występuje - to
A(n)=(n+1)/2
. Czyli średnio
przeszukuje się połowę ciągu,
Jeśli
p=1/2
, to
A(n)=(3n+1)/4
Czyli średnio przeszukuje się 3/4 elementów
ciągu,
Jeśli
p jest bliskie zera
to
A(n)
jest bliski
n.
Czyli średnio trzeba przeszukać
cały ciąg.
X –nie wystąpi w ciągu
Ale taka suma =n(n+1)/2
46
Algorytmy iteracyjne
W sytuacjach praktycznych często występuje konieczność powtarzania pewnych
obliczeń. W algorytmach i programowaniu służą do tego pętle. Algorytmy i programy
wykorzystujące mechanizm pętli nazywamy iteracyjnymi. Dla każdej pętli muszą być
określone:
-
warunki początkowe (rozpoczęcia pętli);
-
operacje wykonywane w pętli;
-
warunek zakończenia pętli
Np. w przypadku sumowania n liczb kolejną liczbę dodajemy do dotychczasowego
wyniku dodawania. Wielokrotne dodawanie zastępujemy wówczas jedną, powtarzaną
wielokrotnie operacją dodawania. Oczywiście liczba powtórzeń operacji dodawania musi
wynosić dokładnie n, a pierwszy istniejący wynik musi mieć wartość 0 nadaną mu przed
zainicjowaniem pętli. Ten wynik spełnia rolę pewnego akumulatora kumulującego
dodane wartości.
Warunek zakończenia pętli jest bardzo istotny. Złe jego określenie może spowodować,
że pętla nigdy się zakończy (pętla nieskończona).
Warunek zakończenia pętli może występować:
na początku pętli- wówczas decyduje czy instrukcje pętli będą wykonane czy
pominięte.
na końcu pętli - wówczas decyduje czy instrukcje pętli będą powtórzone kolejny
raz, czy też nastąpi realizacja dalszej części algorytmu (programu).
Jako ciekawostkę można podać, że pętle nieskończone są czasami stosowane
świadomie i odgrywają istotną rolę w programowaniu.
Są stosowane wtedy gdy nie można przewidzieć ile razy pętla ma być powtórzona.
Fizyczną interpretację można podać obserwując kasjerkę w sklepie, która nie wie ile jest
artykułów w koszyku. Przed przystąpieniem do obsługi musi ona wyzerować rachunek
(nadanie wartości początkowej). Następnie pobiera z koszyka kolejny towar, odczytuje
jego cenę i dodaje do dotychczasowej sumy. Tę czynność powtarza dotąd dopóki
koszyk nie jest pusty. Tu stwierdzenie że koszyk jest pusty jest warunkiem logicznym.
Jeśli ten warunek jest prawdą to następuje zakończenie realizację pętli.
Inny przykład to oczekiwanie na włączenie pewnego urządzenia (drukarki itp).
Takie oczekiwanie może być czasami bardzo długie a program cierpliwie sprawdza w
pętli pewien bajt pamięci (rejestr stanu urządzenia) którego zawartość świadczy o
dostępności do urządzenia.
47
Przykłady przedstawiania algorytmów i programów
Zadanie 1.
Przedstaw algorytm i napisz program w Matlabie, który będzie wielokrotnie powtarzał
wykonywanie pewnego ciągu poleceń Matlaba . O kolejnym powtórzeniu programu
powinien zadecydować operator odpowiadając twierdząco lub przecząco na pytanie
zadane przez program.
Np. pytanie może być sformułowane następująco:
Czy zakończyć ? (Podaj: tak/nie)
Dopóki w odpowiedzi będzie wprowadzany przez operatora tekst „nie” program będzie
wielokrotnie powtarzał obliczenia i drukował komunikat o liczbie powtórzeń np:
„Jest to n=….. powtorzenie”.
Specyfikacja algorytmu programu:
Dane wejściowe:
koniec- zmianna znakowa (string) mogąca przyjmować wartości „tak” lub
„nie”
Dane wejściowe:
- n - liczba całkowita oznaczająca ilość wykonań programu,
- komunikat: - „Jest to n=.....powtorzenie programu”.
Lista kroków:
1. Nadaj zmiennym wartości: n:=0, koniec=’nie’
2. Jeśli zmienna koniec = ’tak’ to przejdź do punktu 7.
(w przeciwnym razie kontynuacja tzn. przejście do następnego punktu).
3. Zwiększ n tzn. n:=n+1
4. Wyświetl komunikat i wstaw wartość n w odpowiednie m-ce tekstu:
„Jest to n =.....powtorzenie programu”.
5. Poproś o odpowiedz: czy kontynuować wykonanie wyświetlając
komunikat: Czy zakończyć ? (Podaj: t=tak / n=nie)
6. Pobierz wpisany przez operatora tekst z klawiatury do zmiennej koniec.
Przejdz do punktu 2.
7. Koniec
Powyższy algorytm zawiera pętlę, a liczba jej wykonań jest nieznana. Stąd
wynika, że w praktycznej realizacji powinna być zastosowana pętla while.
Na rys. 1a przedstawiono obraz okna edytora Matlaba. W oknie widoczne są
instrukcje programu realizujące postawione zadanie. Program jest zapisany jako
m-plik o nazwie PowtarzajObl1 w katalogu work (domyślnym) systemu Matlab.
Na rys. 1b przedstawiono przykład wprowadzanych danych i wyników
wyświetlanych przez program PowtarzajObl1. Komunikacja operatora z
programem odbywa się przy pomocy klawiatury, a wyniki dialogu oraz wyniki
wyjściowe są wyświetlane w oknie konsoli (inaczej Command Window)
48
>> PowtarzajObl1
POWTARZANIE OBLICZEN
JEST TO
n=1
POWTORZENIE
Czy zakończyć? (Podaj: tak / nie)
nie
JEST TO
n=2
POWTORZENIE
Czy zakończyć? (Podaj: tak / nie)
nie
JEST TO
n=3
POWTORZENIE
Czy zakończyć? (Podaj: tak / nie)
tak
>>
Matlaba. W zakresie pętli umieszczono tylko polecenie wydruku informujące o
numerze powtórzenia pętli.
Rys. 1a Program realizujący
zadanie (wygląd okna
edytora Matlaba) :
Rys. 1b. Przykład wyników
testowania programu
Uwaga:
Program drukuje na ekranie (w oknie Command Window) wyniki tylko czarną
czcionką. Dla wyróżnienia istotnych elementów w powyższym przykładzie
wyników zmieniono kolor czcionki i tak:
Liczbę n powtórzeń komunikatu, drukowaną i zmienianą przez program,
zaznaczono kolorem zielonym,
Wprowadzane przez operatora odpowiedzi zaznaczono kolorem
niebieskim.
Dodatkowo w celu zwiększenia przejrzystości wprowadzono też puste
wiersze.
49
Zadanie 2.
Sformułuj algorytm obliczający sumę ciągu n liczb wprowadzanych do komputera.
Ilość liczb jest pierwszą wprowadzaną wartością.
Specyfikacja algorytmu:
Dane wejściowe:
- n- liczba całkowita określająca ilość wprowadzanych liczb;
- ciąg n liczb rzeczywistych
Wynik:
Sum- liczba rzeczywista określająca sumę wprowadzonych dotychczas liczb.
Zmienne pomocnicze:
i - liczba całkowita (licznik powtórzeń);
liczba- liczba rzeczywista przyjmująca wartość kolejno wprowadzanych liczb
Lista kroków:
1.
Wczytaj z klawiatury liczbę określającą ilość wprowadzanych
liczb i zapisz ją w zmiennej
n
.
2.
Zmiennej
Sum
przypisz wartość początkową
0
.
3.
Zmiennej
i
przypisz wartość początkową
0
.
4.
Wczytaj wartość liczby wprowadzonej z klawiatury
i zapamiętaj ją w zmiennej
liczba
.
5.
Zwiększ wartość licznika
i
o
jeden
.
6.
Do dotychczasowej sumy (
Sum
) dodaj wczytaną liczbę (
liczba
).
7.
Jeśli
i <n
to wróć do kroku 4.
8.
Wyświetl wartość zmiennej
Sum
. Koniec
Rys. 2 Schemat blokowy
Wczytaj: n
i :=0
Sum=0.0
i < n
Wyświetl:
Sum
Początek
Koniec
i :=i+1
Sum :=Sum +liczba
Wczytaj: liczba
Tak/True
Nie/False
Pseudokod programu:
Program SumaLiczb
zmienne:
n, i - całkowite
liczba, Sum- rzeczywiste
początek
czytaj(n)
i:=0
Sum:=0
powtarzaj dopóki i < n
czytaj(liczba)
i:=i+1
Sum:=Sum +liczba
pisz(Sum)
koniec
50
Poniżej przedstawiono różne formy zapisu tego algorytmu w pseudokodzie.
a)
b)
c)
d)
Pseudokod programu:
Program SumaLiczb
zmienne
n, i- całkowite
liczba, Sum- rzeczywiste
początek
czytaj(n)
i:=0
Sum:=0
powtarzaj dopóki i < n
czytaj(liczba)
i:=i+1
Sum:=Sum +liczba
pisz(Sum)
koniec
Pseudokod programu:
Program SumaLiczb
zmienne
n, i- całkowite
liczba, Sum- rzeczywiste
begin
read(n)
i:=0
Sum:=0
while i < n do
read(liczba)
i:=i+1
Sum:=Sum +liczba
write(Sum)
end
Pseudokod programu:
Program SumaLiczb
zmienne
n, i- całkowite
liczba, Sum- rzeczywiste
begin
read(n)
Sum:=0
for i:=1 step 1 until n do
begin
read(liczba)
Sum:=Sum +liczba
end
write(Sum)
end
Pseudokod programu:
Program SumaLiczb
zmienne
n, i- całkowite
liczba, Sum- rzeczywiste
begin
read(n)
i:=0
Sum:=0
do
read(liczba)
i:=i+1
Sum:=Sum +liczba
while i < n
write(Sum)
end
51
Zadanie 3
Opracuj algorytm programu który wczytuje ciąg liczb. Liczby mogą być dodatnie i
ujemne lub tylko dodatnie albo tylko ujemne. Wczytywanie liczb kończy się, jeżeli
wprowadzono już 99 liczb lub podano liczbę zero. Program ma wyznaczyć ile było
liczb dodatnich oraz najmniejszą z wprowadzonych liczb dodatnich (jeśli były).
Dane wejściowe:
-
ciąg n liczb rzeczywistych (n-nieznane, n<100)
Wynik:
-
n- liczba całkowita określająca ilość wprowadzonych liczb;
-
m- liczba całk. określająca ilość wprowadzanych liczb dodatnich (m≤n);
-
min- liczba rzeczywista określająca najmniejszą wprowadzoną liczbę
dodatnią
Zmienne pomocnicze:
i - liczba całkowita (licznik powtórzeń);
x-
liczba rzeczywista przyjmująca wartość kolejno wprowadzanych liczb
Przykład wyników:
Wprowadzono n=27 liczb Liczb dodatnich m= 12 min = 0.75
lub
Wprowadzono n=18 liczb Brak liczb dodatnich
Lista kroków (wersja 1):
Lista kroków (wersja 2):
Wersja 1 jest krótsza bo narzucono tu wstępną wartość min=999999 (aby ustrzec
się błędów wartość ta powinna być największą możliwą liczbą !). W wersji 2 nie
jest wymagane podanie wstępnej wartości min ale algorytm jest bardziej złożony.
Wprowadzanie danych oraz
określenie n oraz m
1. Nadaj zmiennym wartości:
n :=0 m:=0
2. Wczytaj liczbę do zmiennej
x
.
3. Zapamiętaj x jako min:
min:=x
4. Jeśli
x=0 lub n=99
to pkt.
11
5. Aktualizuj ilość wczytanych
:
n:=n+1
6. Jeśli
x>0
to
m=m+1
7. Jeśli
min<0
to
min=x
8. Jeśli
x >0
and x < min
to:
min:= x
9. Wczytaj liczbę do zmiennej
x
10. Przejdź do kontynuacji od punktu.
4
Wydruki wyników
11. Jeśli
m>0
to drukuj wartości:
n=..... m=.......min=........
W przeciwnym razie drukuj:
Brak Liczb dodatnich
n=.......
12. Koniec
Wprowadzanie danych oraz
określenie n oraz m
1. Nadaj zmiennym wartości :
n :=0 m:=0 min=999999
2. Wczytaj liczbę do zmiennej
x
.
3. Jeśli
x=0 lub n=99
to pkt.
8.
4. Aktualizuj ilość wczytanych liczb
:
n:=n+1
5. Jeśli
x>0
to
m=m+1
6. Jeśli
x >0
and x < min
to:
min:= x
7. Przejdź do kontynuacji od pktu
2.
Wydruki wyników
8. Jeśli
m>0
to drukuj wartości:
n=..... m=.......min=........
W przeciwnym razie drukuj:
Brak Liczb dodatnich
n=.......
9. Koniec
52
Poniżej, dla ułatwienia analizy po lewej stronie powtórzono algorytm dla
zadania 3 w postaci listy kroków i przedstawiono (po prawej stronie) 2
inne formy jego zapisu w pseudokodzie.
Lista kroków (wersja 2):
1. Nadaj zmiennym wartości:
n :=0 m:=0
2. Wczytaj liczbę do zmiennej
x
.
3.
min:=x
4. Jeśli
x=0 lub n=99
to pkt. 11
5. Aktualizuj ilość wczytanych
: n:=n+1
6. Jeśli
x>0
to
m=m+1
7. Jeśli
min<0
to
min=x
8. Jeśli
x >0
and x < min
to:
min:= x
9. Wczytaj liczbę do zmiennej
x
10. Przejdź do kontynuacji od punktu.4
Wydruki wyników
11. Jeśli
m>0
to drukuj wartości:
n=..... m=.......min=........
W przeciwnym razie drukuj:
Brak Liczb dodatnich
n=.......
12. Koniec
Pseudokod programu (wersja 2):
:
Program MAX
zmienne
n,m - całkowite
x, min- rzeczywiste
begin
n:=0, m:=0
read(x)
min:=x
while (n < 99 & x ≠ 0 ) do
begin
n:=n+1
if x>0 then m:=m+1
if nin<0 then min:=x
if (x>0 & x<min) then min:=x
read(x)
end
if m>0 then
write(n, m, min)
else
write(n, Brak liczb dodatnich)
end
Pseudokod programu(Wersja 1):
Program MAX
zmienne
n,m - całkowite
x, min- rzeczywiste
begin
n:=0, m:=0 min=999999
read(x)
while (n < 99 & x ≠ 0) do
begin
n:=n+1
if x>0 then m:=m+1
if (x>0 & x<min) then min:=x
read(x)
end
if m>0
write(n, m, min)
else
write(n, Brak liczb dodatnich)
end
Lista kroków(wersja 1):
Wprowadzanie danych oraz
określenie n oraz m
1. Nadaj zmiennym wartości początkowe:
n :=0 m:=0 min=999999
2. Wczytaj liczbę do zmiennej
x
.
3. Jeśli
x=0 lub n=99
to przejdź do
pkt. 8.
4. Aktualizuj ilość wczytanych liczb
:
n:=n+1
5. Jeśli
x>0
to
m=m+1
6. Jeśli
x >0
and x < min
to wykonaj
operacje:
min:= x
7. Przejdź do kontynuacji od punktu.2.
Wydruki wyników
8. Jeśli
m>0
to drukuj wartości:
n=..... m=.......min=........
W przeciwnym razie drukuj:
Brak Liczb dodatnich
n=.......
9. Koniec
53
Zadanie 4
Opracuj algorytm programu, który wczytuje i zapamiętuje w tablicy o nazwie A ciąg
liczb. Wprowadzane liczby mogą być dodatnie i ujemne lub tylko dodatnie albo
tylko ujemne. Wczytywanie liczb kończy się, jeżeli wprowadzono już 99 liczb lub
podano liczbę zero. Program powinien wyznaczyć i poinformować jaka była
najmniejsza z wprowadzonych liczb dodatnich (jeśli były liczby dodatnie) oraz ile
było liczb dodatnich.
Dane wejściowe:
-
ciąg n liczb rzeczywistych (n- nieznane, n<100)
Wynik: n- liczba całkowita określająca ilość wprowadzanych liczb;
-
m- liczba całkowita określająca ilość wprowadz. liczb dodatnich (m≤n);
-
min- najmniejsza wprowadzona liczba dodatnia (liczba rzeczywista ).
Zmienne pomocnicze:
-
i - liczba całkowita (licznik powtórzeń);
-
x - liczba rzeczywista przyjmująca wartość kolejno wprowadzanych liczb
-
A[1:99]- tablica zapamiętująca ciąg n liczb rzeczywistych
Przykład wyników:
Wprowadzono n=27 liczb Liczb dodatnich m= 12 MIN = 0.75
lub
Wprowadzono n=18 liczb Brak liczb dodatnich
Lista kroków
Wprowadzanie danych oraz określenie n oraz m
1. Nadaj zmiennym wartości początkowe:
n :=0 m:=0 i=0
2. Wczytaj liczbę do zmiennej
x
.
3. Jeśli
x=0 lub n=99
to przejdź do
pkt.7
.
4. Zapamiętaj
x
w tablicy:
n:=n+1
A[n]:=x
5. Jeśli
x>0
to
m=m+1 min:=x
6. Przejdź do kontynuacji od punktu.
2
Wyszukiwanie min (jeśli były liczby dodatnie)
7. Jeśli
m=0
lub
n=0
to przejdź do pkt.
12
8. Zwiększ
i:=i+1
9. Jeśli
A[i] > 0
and
A[i] < min
to wykonaj:
min:= A[i]
11
Jeśli
i < n
to kontynuuj od pkt
8.
Wydruki wyników
12. Jeśli
m>0
to drukuj wartości:
n=..... m=.......min=........
W przeciwnym razie drukuj:
Brak Liczb dodatnich
n=.......
13. Koniec
Pseudokod programu
Program MIN DODATNIA
zmienne
n,m, i- całkowite
x, min- rzeczywiste
begin
n:=0, m:=0, i=0
read(x)
while (n <99 & x ≠ 0) do
begin
n:=n+1 A[n]:=x
if x>0 then
begin
m:=m+1 min:=x;
end
read(x)
end
for i:=1 step 1 until n do
begin
if A[i]>0 & A[i] < min then
min:=A[i]
end
if (m>0 and n>0) then
write(n, m, min)
else
write(n, Brak Liczb dodatnich )
end
54
Zadanie 5
Opracuj algorytm programu który sprawdza czy podana liczba jest liczbą pierwszą.
Uwaga: Liczba pierwsza to liczba naturalna podzielna przez 1 i samą siebie np. 1,3
Dane wejściowe:
n – analizowana liczba całkowita >2
Wynik:
Komunikat postaci np.: „Podana liczba jest liczbą pierwszą”
Zmienne pomocnicze:
podz - liczba całkowita, aktualny podzielnik
Lista kroków (wersja 1):
1.
Wczytaj wartość n.
2.
podz:=2
3.
Jeśli n mod podz =0 to:
Pisz(To nie pierwsza)
Przejdz do punktu 7
4.
podz:=podz+1
5.
Jeśli podz < n to przejedz do 3
6.
Pisz (To liczba pierwsza)
7.
Koniec
Pseudokod programu:
Program CZY_PIERWSZA
Zmienne
n, podz- całkowite
pierwsza: logiczna
begin
read(n)
pierwsza=true podz:=2
while (pierwsza=true) and (podz < n)
begin
if (n mod podz =0) then
pierwsza=false
else
podz:=podz+1
end
if (pierwsza=true)
write(n, To liczba pierwsza)
else
write(n, To nie pierwsza)
end
True
True
True
True
Wczytaj
: n
podz :=2
podz < n
Wyświetl: Licz. Pierwsza
Początek
podz :=podz+1
False
False
False
False
n mod
podz
Koniec
Wyświetl: To nie
jest Licz. Pierwsza
False
False
False
False
True
True
True
True
n mod
podz- to działanie
wyznacza resztę z
dzielenia całkowitego
n/podz
np.: 11 mod 2=1
10 mod 2=0
55
Algorytmy rekurencyjne
W programowaniu często zagadnienia większe są dzielone na pewne ściśle określone
fragmenty i są one poddawane odrębnie algorytmizacji i programowaniu. Wówczas
program rozwiązujący całościowo zagadnienie składa się z kilku (co najmniej 2)
elementów, które są określane jako:
program główny (zwykle krótki)
podprogramy
Podprogramy są wywoływane z programu głównego, a miejsce ich wywołania wynika z
algorytmu rozwiązania problemu. Program główny komunikuje się z programami w
następujący sposób:
przekazuje do podprogramu niezbędne dla obliczeń dane (liczby, tablice liczb
zmienne logiczne itp.)
odbiera z podprogramów wyniki obliczeń
Podprogramy są realizowane w postaci:
funkcji
procedur
W niektórych językach (np. w Matlabie) procedury formalnie nie występują, ale z jednego
skryptu może być wywołany inny skrypt w którym jest realizowana wydzielona część
obliczeń, co przypomina wywołanie procedury.
Najczęściej funkcje są tak konstruowane, że w wyniku ich wykonania otrzymuje się jedną
wartość liczbową lub np. tablicę wartości. Są 2 rodzaje funkcji:
- standardowe pisane przez producentów oprogramowania np. funkcja sin(alfa)
obliczająca wartość sinusa dla zadanego kąta alfa.
- własne pisane na użytek rozwiązywania określonego problemu.
Funkcje wymagają ściśle określonych danych i są w programie wywoływane przez
użycie ich nazwy i podanie parametru (lub parametrów). Np. zapis x=sin(alfa) wywołuje
ciąg instrukcji realizujący algorytm obliczania wartości sinus dla zadanego kąta alfa
podawanego w radianach. Obliczona wartość jest podstawiana pod zmienną x.
Podobnie jest z funkcjami własnymi.
Czyli funkcje inaczej mówiąc są oddzielnymi programami o nadanej im nazwie, najlepiej
takiej, żeby kojarzyła się z przeznaczeniem. Zwykle w ich definicji występuje na początku
słowo kluczowe
function.
Algorytmy rekurencyjne są konstruowane tak by można było je zapisać w postaci
funkcji. Cechą charakterystyczną jest to, że dla uzyskania wyników obliczeń wywołują
one same siebie.
Wykorzystanie rekurencji jest wygodne w rozwiązywaniu wielu problemów ze
względu na krótki kod. Oczywiście zagadnienia rozwiązywane rekurencyjnie dają się
rozwiązywać z zastosowaniem metod wykorzystujących iterację.
56
2
2
2
1
2
1
0
*
−
=
=
n
n
Zadanie 6
Opracuj rekurencyjny algorytm programu który oblicza wartość 2
n
, gdzie n jest
dowolną liczbą całkowitą.
Rozwiązanie
Jednym ze sposobów jest skorzystanie z definicji: n-tej potęgi liczby 2 można
zdefiniować następująco:
dla n=0
n-ta potęga liczby 2=
dla n>0
Specyfikacja algorytmu:
Dane wejściowe:
n – wykładnik (n≥0) jest liczbą przekazywaną do funkcji przez tzw. wartość.
Wynik:
np2- liczba całkowita, wartość n-tej potęgi liczby 2 (tzn. 2
n
).
Zmienne pomocnicze:
Nie występują .
Lista kroków:
1. Jeśli n=0 to potega:=1
2. Jeśli n>0 to potega:=2*potega(n-1)
Pseudokod:
function np2=potega(n)
begin
if n=0 then
np2:=1
else
np2:= 2*potega(n-1)
end
Działanie:
Funkcja wywoływana jest następująco np. dla n=3
X= potega(3)
Po wykonaniu obliczeń wartość X=8
Wykonanie przebiega następująco:
Etap 1
2* potega(2)
2*4=8 Wynik
Etap 2
2* potega(1)
…(2*2)=4
Etap 3
2*potega(0)
… (2* 1)=2
Etap 4
potega(0)=1
Aktualne wyniki
są odkładane na
stosie (zejście w
głąb stosu)
„Obrazy wyników” są
pobierane ze stosu i
uzupełniane (cofanie
rekurencji)
Wartość już znana !
Można już cofać się
wyznaczając potega(1),
potega(2) itp. aż do
potega(3)
57
Formularz kolokwium zaliczającego ćwiczenie rachunkowe
Przykład
58
GRUPA B
B
B
B
………………..……………………………………..Grupa E0X………
Wpisz wyżej: Nazwisko i imię, grupę (drukowanymi - wyraźnie! ) Data:…
30.11.2010.
.
Podpis studenta:
………….…………….……………………………
Tabela cen:
1
2
3
4
5
6
7
8
9
10 11
zad. tekstowe
Razem
pkt.
Uwaga: Cz I max 18 pkt + Cz II max 17pkt = 35 pkt. Zaliczenie: od 18 pkt.
Część I- Reprezentacja liczb. Kody ( max 18 pkt. )
1.
(1pkt) a) Napisz po znaku równości wartość dziesiętną liczby zapisanej w naturalnym kodzie binarnym (NKB).
(NKB oznacza zapis liczby całkowitej bez znaku w kodzie binarnym ) .
0 1 1 0 1 0 1 1 =…….
D
b) Zapisz w NKB liczbę dziesiętną.
= 113
D
.
2.
(1pkt) Zapisz w kodzie ZM podaną liczbę.
= -112
D
3.
(1pkt) Zapisz w kodzie U1 podaną liczbę.
= -112
D
4.
(1pkt) Zapisz w kodzie U2 podaną liczbę
= -112
D
5.
(1pkt) Liczba jest zapisana w U2. Jaka to liczba dziesiętna?
1 0 0 0 0 1 1 1 =…….
D
6.
(5pkt) Wykonaj działanie: 65 – 32= ? stosując kod U2.
……………..( )
……………..( )
Znak operacji :
………………..
……………..( )
Wpisz wyżej, z prawej strony, jaka jest wartość liczb i wyniku
i w jakim są kodzie. Z lewej wpisz znak operacji.
7.
(3pkt) a) Zamień liczbę zapisaną w NKB na postać heksadecymalną.
1 1 1 0 1 1 1 0 =…….
h
b) zamień na postać hex:
108
D
= …….
h
c) zamień na postać dziesiętną: B6A
h
=………..
d
8.
(2pkt) Dodaj liczby heksadecymalne: DAE
+ 5A5
9.
(1pkt) Liczba jest zapisana w kodzie BCD. Jaka to liczba dziesiętna?:
0 1 0 1 0 1 1 1 =……
D
10.
(2pkt) Zapisz binarnie liczbę rzeczywistą przyjmując,
że umowne położenie przecinka jest jak w tabelce.
,
=12,375
D
Zadanie tekstowe. (17 pkt)
(3- za specyfikację, 10 –wartość merytoryczna, 4- za staranność)
Opracuj algorytm, który wczyta liczbę N wskazującą na ilość pobieranych liczb z klawiatrury,
a następnie wczyta N dowolnych liczb oraz obliczy i wyświetli ich średnią arytmetyczną.
59
Zadania
Zadanie 1
Przedstaw algorytm i wykonaj program, który wczytuje liczbę x i informuje czy
to liczba dodatnia, ujemna czy równa zero.
Zadanie 2
Przedstaw algorytm i wykonaj program, który dla zadanych dowolnych liczb a
oraz b zapewni sprawdzenie czy spełniają one relację a ≤ b.
Zadanie 3
Sformułuj algorytm i wykonaj program, który dla podanych dwu wartości a i b
obliczy ich średnią arytmetyczną i geometryczną (jeśli to możliwe).
Zadanie 4
Sformułuj algorytm który dla podanych dwu wartości a i b obliczy ich iloraz
(jeśli to możliwe).
Zadanie 5
Przedstaw algorytm i wykonaj program, który dla zadanych dowolnych trzech
liczb zapewni wyznaczenie wartości a, b ,c tak by spełniały one relację
a ≤ b ≤ c.
Zadanie 6
Przedstaw algorytm i wykonaj program, który dla zadawanych wartości
typowych ocen: 2, 3, 3.5, 4, 4.5, 5 przyporządkuje oznaczenie słowne: ndst., dst,
dst plus, db, db plus, bdb).
Zadanie 7
Zmienna x jest oceną którą otrzymałeś z Mtp1 (2, 3, 3.5,4,4.5, 5). Zaprojektuj
algorytm i wykonaj program, który poprosi o podanie oceny i interpretując ją
odpowie:
Nie zaliczyłeś. Przykro mi!
Wybrnąłeś, ale słabo!
No, nieźle!
No dobrze. Tak trzymaj!
Super!
Zadanie 8
Sformułuj algorytm i napisz program, który dla podanej wartości x (w stopniach)
sprawdzi i poinformuje, czy funkcja sin(x):
Ma miejsce zerowe (tzn. sin(x)=0)
Przyjmuje wartość max,
Przyjmuje wartość min.
60
Zadanie 9
Przedstaw algorytm i wykonaj program, który dla zadawanych wartości a , b
oraz c określi która z tych zmiennych określa wartości najmniejszą, a która
największą ( np. min=b, max=a);
Zadanie 10
Przedstaw algorytm i wykonaj program, który dla zadawanych wartości a , b oraz
c (długości boków trójkąta) sprawdzi i poinformuje czy z zadanych boków można
utworzyć trójkąt.
Wskazówka: Sprawdzić relacje boków.
Zadanie 11
Wartości a , b oraz c są współczynnikami równania kwadratowego typu:
a*x^2 +b*x +c=0
Podać algorytm i napisać program, który w zależności od wartości a,b,c określi:
czy równanie ma pierwiastki (np. Brak pierwiastków rzeczywistych),
Ile istnieje pierwiastków (np. Równanie ma 1 pierwiastek).
Zadanie 11
Wartości a , b oraz c są współczynnikami równania kwadratowego typu:
a*x^2 +b*x +c=0
Podać algorytm i napisać program, który w zależności od wartości a,b,c określi:
czy równanie ma maksimum i ile ono wynosi bądź też,
czy równanie ma maksimum i ile ono wynosi.
Zadanie 12
Wartości a , b oraz c są współczynnikami równania kwadratowego:
a*x^2 +b*x +c=0
Podać algorytm i napisać program, który w zależności od wartości a,b,c określi
wartości liczbowe jego pierwiastków.
Zadanie 13
Dane są liczby całkowite a i b (a,b>0) i takie, ze a<b. Zaprojektuj algorytm i
wykonaj program, który oblicza sumę i iloczyn liczb całkowitych z przedziału [a,b].
Zadanie 14
Dane są dwie liczby całkowite a i b (a,b>0) i takie, ze a<b. Zaprojektuj algorytm i
wykonaj program, który oblicza sumę i iloczyn liczb parzystych z przedziału [a,b].
Zadanie 15
Dane są dwie liczby całkowite a i b (a,b>0) i takie, ze a≠b. Zaprojektuj algorytm i
wykonaj program, który oblicza sumę i iloczyn liczb nieparzystych z przedziału
[a,b].
61
Zadanie 16
Zaprojektuj algorytm i wykonaj program, który dla wprowadzanych liczb będzie
określał, czy są one całkowite czy nie
.
Zadanie 17
Wartości a , b oraz c są długościami boków trójkąta. Należy zaprojektować
algorytm i wykonać program sprawdzający czy z zadanych boków można utworzyć
trójkąt. Rozwiąż problem tak aby wykorzystać wzór Herona.
Zadanie 18
Wartości a , b oraz c są długościami boków trójkąta. Należy zaprojektować
algorytm i wykonać program sprawdzający czy z zadanych boków można utworzyć
trójkąt prostokątny.
Zadanie 19
Wartości a , b oraz c są długościami boków trójkąta. Należy zaprojektować
algorytm i wykonać program sprawdzający czy z tych boków można zbudować
trójkąt prostokątny jeśli tak to należy poinformować, która z wartości określa
przeciwprostokątną a które są przyprostokątnymi.
Zadanie 20
Wartości boków trójkąta prostokątnego mogą być wprowadzane w dowolnej
kolejności i są pamiętane jako: b1 , b2 oraz b3. Zaprojektuj algorytm i wykonaj
program obliczający pole trójkąta (nie korzystać z wzoru Herona).
Zadanie 21
Sformułuj algorytm napisz program kalkulatora, który dla podanych dwu
dowolnych wartości liczbowych a i b oraz znaku operacji Zn (dopuszczalne
wartości Zn to: +, -, *, /, s, g (gdzie: s- średnia arytmetyczna, g- średnia
geometryczna) wykona stosowne działanie i poda jego wynik lub zasygnalizuje
przyczynę błędu.
Zadanie 22
Przedstaw algorytm i napisz program wczytujący n liczb i informujący czy
kolejna, podana liczba jest:
Całkowita
Pierwsza,
Parzysta czy nie
Zadanie 23
Przedstaw algorytm i napisz program wczytujący liczby i informujący czy
kolejna, podana liczba jest:
Całkowita
Pierwsza,
Parzysta czy nie
Ilość badanych liczb nie jest znana.
62
Wyszukiwarka
Podobne podstrony:
więcej podobnych podstron