Część I Metodyka i Techniki Programowania

MATERIAAY 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
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.
2
INFORMACJE
DOSTPNOŚĆ 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
3
T1 i T2
REPREZENTACJA DANYCH W KOMPUTERZE
SYSTEMY KODOWANIA DANYCH
OPERACJE ARYTMETYCZNE
4
System pozycyjny zapisu liczb
Liczby w zapisie pozycyjnym (np. 239) są przedstawiane jako łańcuchy
cyfr (ci), czyli znaków przypisanych liczbom naturalnym:
ci " {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ą:
n
= " Ri
"ci (1)
L
( R)
i=0
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ądz 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: ci " {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
104 103 102 101 100 wagi kolejnych cyfr systemu
W podobny sposób można też przedstawić liczby Lu <1 tzn. liczby ułamkowe:
n
= " R-i
"ci (2)
Lu
( R)
i=1
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*82 + 3*81 + 7*80=159(10)
System 4 (233) 4 =2*42 + 3*41 + 3*40= 47(10)
5
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:
2n -1 e" 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 :
210 -1 e" 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*23+1*22+l*21+0*20 = 14(10)
Zakładając 1 bajt (tzn. n= 8) to oznaczenia i wagi bitów są następujące:
Nr bitu: b7 b6 b5 b4 b3 b2 b1 b0
27 & & .. 23 22 21 20
Wagi bitów: 128 64 32 16 8 4 2 1
Kod o takich wagach jest nazywany naturalnym kodem binarnym NKB.
Bit bo -jest bitem najmniej znaczacym -LSB (least significant bit),
a bit najstarszy tzn. bn-1 - MSB (most significant bit)
Największa liczba zapisana przy pomocy n bitów to Lmax= (2n 1)- stąd dla
n=8 Lmax=255 co oznacza ze jedynki są na wszystkich bitach bajtu.
6
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
znalezć 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
Wynik:
13:2 6 1
6:2 3 0
1101100(2)
3:2 1 1
1:2 0 1
Sprawdzenie:
1101100(2)= l*26+l*25+0*24+l*23+l*22+0*21+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*22 + 0*21 + 1*20 + 1*2-1 + 0*2-2 + 1*2-3 =5,625
7
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) znalezć najmniejszą wartość n taką, aby zachodziła relacja:
2n +1 > X e"2n
Nadać bitowi bn wartość bn =1.
3) Obliczyć różnicę Y=X- 2n Czy Y=0 ?
TAK: Przejdz do 4.
NIE: Podstaw X:=Y (czyli nowy X jest resztą). Przejdz 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 2n+1 > 88 e" 2n Dla n=7 jest (27 > 88 > 26).
Czyli największą możliwą wagą jest 26 . Stąd bit b6=1;
3. Zostaje różnica Y=88-64=24 Ponieważ Y>0 to nowa wartość X=24
2. Szukamy największego n aby 2n+1 > 24 e" 2n . Dla n=4 jest (25>24> 24 ).
Czyli największą możliwą wagą jest 24 . Stąd bit b4=1;
3. Zostaje różnica Y=24-16=8. Ponieważ Y>0 to X=8
2 Szukamy znów największego n aby 2n+1 > 8 e" 2n . Dla n=3 jest (24>8 e" 23 ).
Czyli największą możliwą wagą jest 23 . Stąd bit b3=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
8
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
0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, 1 ^ 1 = 0
XOR
Przykłady:
Jest różnica na najmłodszym
bicie!!!
9
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:
przeniesienie
Reguły odejmowania:
pożyczka
10
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.
11
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*82+0*81+7*80 = 4*64+7 = 256+7 = 263(10)
Przykład 1.2 :
Dana jest liczba naturalna n = 197 zapisana w systemie dziesiętnym.
Należy znalezć 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
Wynik: 305(8)
3 0
24: 8
3:8 0 3
Wynik: 305(8)
Sprawdzenie: 305(8) = 3*82+0*81+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
znalezć 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.
6 0 4 (8)
Wynik:
110000100(2)
110 000 100
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)
12
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*161+12*16� = 80+12 = 92(l0)
Przykład 1.4. zamiana liczby dziesiętnej na heksadecymalną
Znalezć 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
Wynik:
107:16 6 (11) czyli B
107(d) = 6 B (h)
6:16 0 6
Sprawdzenie: 6 B (16) =6*161 + 11*160 =96+ 11=107 (10)
Przykład 1.5. Zamiana liczby binarnej na heksadecymalną.
Dana jest liczba naturalna n =10010110011 zapisana w systemie binarnym.
Znajdz jej notację w systemie szesnastkowym.
Sposób rozwiązania:
Podstawą systemu jest 16 (24 - 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
Rozwiązanie:
1 0001
2 0010
Należy zamienić
3 0011
czteroelementowe ciągi cyfr
4 0100
5 0101 z systemu binarnego na
6 0110
cyfry w systemie
7 0111
heksadecymalnym.
8 1000
0100 1011 0011
9 1001
A 1010
B 1011
4 B 3
4 B 3
4 B 3
4 B 3
C 1100
D 1101
Wynik:
E 1110
4B3
F 1111
Na liczbach hex można wykonywać typowe operacje np.:
1B8 440
+ C7 199
2 7 F 639
13
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żnie 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.
14
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 e" 0 - oznacza zapis x w NKB
xZM =
2n-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:
2n-1 =27 =128 1 0000000
|-23|= +0 0010111
1 0010111 -23ZM
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:
[-2n-1 -1 : 2n-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.
15
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 e" 0 - oznacza zapis x w NKB
xU1 =
(2n 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:
2n -1 =28 -1=255 1 1111111
|-23|= - 0 0010111
1 1101000 -23U1
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 - 23U1
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:
[-2n-1 -1 : 2n-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.
16
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 e" 0 - oznacza zapis a w kodzie binarnym (NKB)
xu2 =
2n -|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: 2n (czyli 256) i 22.
b8 b7 b6 b5 b4 b3 b2 b1 b0
Wagi bitów: 256 128 64 32 16 8 4 2 1
2n = 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 2n -|a| . Sczegółówo zostało to
przedstawione w tabelce poniżej:
Pożyczka 1 1 1 1 1 1 1 Dziesiętnie
2n 1 0 0 0 0 0 0 0 0 256
- 22
|22| - 0 0 0 1 0 1 1 0
234NKB
-22u2 1 1 1 0 1 0 1 0
b7 b6 ... ... .... b2 b1 b0
gdzie: kolor zielony bit znaku
Jeśli dane tzn n=8 i a=-22 podstawimy do wzoru to mamy:
2n -|a| =28 -|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* 27 + 1* 26 + 1* 25 + 1* 23 + 1*21 = 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.
17
Sposób B
Liczbę całkowitą a zapisuje się w kodzie U2 na n bitach następująco:
x jeśli x e" 0
X= -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=27+(-22)=128-22=106.
Liczba 106 powinna być zapisana na bitach b6 b5 b4 b3 b2 b1 b0
Nr bitu b7 b6 b5 b4 b3 b2 b1 b0
waga
- 128 64 32 16 8 4 2 1
-22u2 1 1 1 0 1 0 1 0
-128 106 = -22(10)
Interpretacja
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 e" 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 b0 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 b7 b6 b5 b4 b3 b2 b1 b0
128 64 32 16 8 4 2 1
waga
| 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 b7 przyjmuje wartość 1, co oznacza liczbę
ujemną.
18
W tabeli niżej pokazano liczby charakterystyczne dla 8-bitowego U2 oraz
dla porównania ich reprezentacje binarne w kodach: ZM i U1.
ZM U1 U2
n= 8
-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 1111111 0 0000000 jedna postać
1 0000000 0 0000000
+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:
[-2n-1 : 2n-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 Wartości w ZM,U1,U2 Wartości w kodzie BCD- 9
dziesiętne (reprezentacje 8-bitowe) bitów: bit znaku + 2 tetrady
89 0 1011001 0 1000 1001
+ 45 +0 0101101 +0 0100 0101
+134 (1) 0 0000110 0 1100 1110
korekcja + 0110 0110
0 0010 0100
(1)- oznacza przeniesienie,
przen. z I tetrady + (1)
czyli , że wynik jest > 128
(1) 0011 0100
Zatem wynik jest: 128 + 6
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.
19
W kolejnej tabeli przedstawiono odejmowanie liczb w różnych kodach.
War Kod ZM U1 U2 BCD
-tości (5-bitów)
9 0 1001 0 1001 0 1001 0 1001
- 7 - 0 0111 +1 1000 +1 1001 - 0 0111
+ 2 0 0010 (1) 0 0001 (1) 0 0010 0 0010
+ 1
W U2 przeniesienie
0 0010
jest ignorowane
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.
20
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 b7 b6 b5 b4 b3 b2 b1 b0
waga znak 64 32 16 8 4 2 1
Przeniesienie jest
Przeniesienie (1) 1 1
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 b7 b6 b5 b4 b3 b2 b1 b0
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: -27+ (wynik w NKB na 6 bitach)=-128+48=-80(10).
Lub inaczej określamy moduł:
28- (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 b7 b6 b5 b4 b3 b2 b1 b0
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
-112(10).
Wynik: 1 0 0 1 0 0 0 0
W wyniku operacji otrzymujemy wartość ujemną w U2 świadczy o tym wartość bitu b7=1.
Czyli wynik jest: -27+ (wynik w NKB na 6 bitach)=-128+16=-112
(10).
21
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
Wynik:
0,75*2 (1),5 0,5 1
0,5*2 (1) 0 1
0,1875 =0 0011
0 *2 (0) 0 0
Tu wystarczą 4 bity
itp
na część ułamkową !
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.
22
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.
23
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
Wynik:
17 : 2 8 1
Część całkowita liczby 34,75(10)
8 : 2 4 0
4: 2 2 0
34(10)= 1 0 0 0 1 0
2:2 1 0
1:2 0 1
Tabela Zamiana liczby 0,75 na kod bin.
Wynik:
Działanie Wynik Cz. Ułamk. Cz. Całk.
Część ułamkowa
liczby 34,75(10)
0,75 *1 1,5 0,5 1
0,5 *2 1 0 1
0,75= 0 11
100010 11
Stąd dodatnią liczbę rzeczywistą 34,75(10) można zapisać binarnie jako:
34,75(10) = 100010 11
,
,
,
,
Sprawdzenie: 25 +21 +2-1 +2-2 =32 +2 +0.5 + 0.25= 34,75
24
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
X =0 0011
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.
25
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 " PC
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
26
Przykład 1
Przedstawić liczbę 125.75 w kodzie FP2.
Szukamy n takiego, że 125.75<2n i mnożymy liczbę przez 2n i bierzemy
część całkowitą liczby.
125.75 * 27 = 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
Pierwsze 7 bitów to część całkowita,
251 : 2 1
dalsze 7 ułamkowa
125 : 2 1
62 : 2 0
Ale to jest dopiero reprezentacja binarna
31 : 2 1
liczby ułamkowej a nie liczby w kodzie
15 : 2 1
FP2!!!
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 26
Po przesunięciu o 6
pozycjiczęść ułamkowa to:
0.96484375
Czyli mamy:
L= (1 + 0.96484375)* 26 =125,75
Czyli liczbę w FP2 możemy zapisać następująco:
125,75 = (0 00110 1111011100) FP2
mantysa=0.96484375
cecha= 6
L= (1 + 0.96484375)* 26 =125,75
Wartość liczby L jest w tym przypadku dokładna, ale w ogólnym przypadku
liczba jest przedstawiana z pewnym przybliżeniem.
27
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 " PC
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 210
Składając to razem zgodnie z wzorem, otrzymujemy:
(-1)0 * (20 + 2-1 + 2-2 + 2-3 + 2-4) * 210 =210 + 29 + 28 + 27 + 26 = 1024 + 512 +
256 + 128 + 64 = 1984
Składnik 20 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.
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.
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ę.
28
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 B
A = mA "10c oraz B = mB "10c
d = cA - cB
oraz przyjmiemy, że
to:
B
A ą B = (mA "10d ą mB) "10c dla cA e" cB
A
A ą B = (mA ą mB "10-d ) "10c dla cB e" cA
A
AB = mAmB "10(c +cB )
A mA
A
= "10c -cB
B mB
Np.: A=2230 = 0,223E4
B=125 =0,125E3
CA > CB d= CA -CB =4-3=1
A+B=(0,223E4+0.125)E3 =(2,23+0,125)E3 =2,355E3 =0,2355 E4
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.
29
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. przejdz 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.
30
Tabela. Kody znakowe ASCII
Dec Hex Bin Znak Dec Hex Bin Znak Dec Hex Bin Znak
0 00 0000000 NUL ' 0' 43 2B 0101011 + 86 56 1010110 V
1 01 0000001 SOH 44 2C 0101100 , 87 57 1010111 W
2 02 0000010 STX 45 2D 0101101 - 88 58 1011000 X
3 03 0000011 ETX 46 2E 0101110 . 89 59 1011001 Y
4 04 0000100 EOT 47 2F 0101111 / 90 5A 1011010 Z
5 05 0000101 ENQ 48 30 0110000 0 91 5B 1011011 [
6 06 0000110 ACK 49 31 0110001 1 92 5C 1011100 \ '\\'
7 07 0000111 BEL '\a' 50 32 0110010 2 93 5D 1011101 ]
8 08 0001000 BS '\b' 51 33 0110011 3 94 5E 1011110 ^
9 09 0001001 HT '\t' 52 34 0110100 4 95 5F 1011111 _
10 0A 0001010 LF '\n' 53 35 0110101 5 96 60 1100000 `
11 0B 0001011 VT '\v' 54 36 0110110 6 97 61 1100001 a
12 0C 0001100 FF '\f' 55 37 0110111 7 98 62 1100010 b
13 0D 0001101 CR '\r' 56 38 0111000 8 99 63 1100011 c
14 0E 0001110 SO 57 39 0111001 9 100 64 1100100 d
15 0F 0001111 SI 58 3A 0111010 : 101 65 1100101 e
16 10 0010000 DLE 59 3B 0111011 ; 102 66 1100110 f
17 11 0010001 DC1 60 3C 0111100 < 103 67 1100111 g
18 12 0010010 DC2 61 3D 0111101 = 104 68 1101000 h
19 13 0010011 DC3 62 3E 0111110 > 105 69 1101001 i
20 14 0010100 DC4 63 3F 0111111 ? 106 6A 1101010 j
21 15 0010101 NAK 64 40 1000000 @ 107 6B 1101011 k
22 16 0010110 SYN 65 41 1000001 A 108 6C 1101100 l
23 17 0010111 ETB 66 42 1000010 B 109 6D 1101101 m
24 18 0011000 CAN 67 43 1000011 C 110 6E 1101110 n
25 19 0011001 EM 68 44 1000100 D 111 6F 1101111 o
26 1A 0011010 SUB 69 45 1000101 E 112 70 1110000 p
27 1B 0011011 ESC 70 46 1000110 F 113 71 1110001 q
28 1C 0011100 FS 71 47 1000111 G 114 72 1110010 r
29 1D 0011101 GS 72 48 1001000 H 115 73 1110011 s
30 1E 0011110 RS 73 49 1001001 I 116 74 1110100 t
31 1F 0011111 US 74 4A 1001010 J 117 75 1110101 u
32 20 0100000 spacja 75 4B 1001011 K 118 76 1110110 v
33 21 0100001 ! 76 4C 1001100 L 119 77 1110111 w
34 22 0100010 `` 77 4D 1001101 M 120 78 1111000 x
35 23 0100011 # 78 4E 1001110 N 121 79 1111001 y
36 24 0100100 $ 79 4F 1001111 O 122 7A 1111010 z
37 25 0100101 % 80 50 1010000 P 123 7B 1111011 {
38 26 0100110 & 81 51 1010001 Q 124 7C 1111100 |
39 27 0100111 ' 82 52 1010010 R 125 7D 1111101 }
40 28 0101000 ( 83 53 1010011 S 126 7E 1111110 ~
41 29 0101001 ) 84 54 1010100 T 127 7F 1111111 DEL
42 2A 0101010 * 85 55 1010101 U
31
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;
32
" 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łaszczyznie 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.
33
T3
ALGORYTMY- SPOSOBY PREZENTACJI
RODZAJE ALGORYTMÓW
ZAOZONOŚĆ OBLICZENIOWA
PRZYKAADY PROJEKTOWANIA ALGORYTMÓW
34
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 znalezć w
Wordzie (rys. ) na pasku
Rysowanie wybierając
Autoksztalty (jeśli pasek nie
jest widoczny można go aktywować z menu Widok Paski 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 ).
35
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.
36
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 cm2)
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)
program pole
Start
var
a, b, p: real;
Wprowadz: a
begin
Wprowadz: b
readln(a);
readln(b);
p:=a*b;
Oblicz: p :=a*b
write( Pole P= ,p:4:2, cm2 )
end.
Pisz: Pole wynosi P= p
Stop
37
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.
Problem !
Start
Wprowadz: a
Wprowadz: b
program pole
var
a, b, p: real;
Algorytm begin
Algorytm
Algorytm
Algorytm
Oblicz: P:=a*b readln(a);
rozwiązania
rozwiązania
rozwiązania
rozwiązania
readln(b);
p:=a*b;
write( Pole P= ,p:4:2, cm2 )
Pisz: Pole i P= P
end.
Program
zródłowy
Stop
Kompilacja
1. Uruchamianie
(usuwanie błędów
językowych)
Program
komputerowy
2. Testowanie
usuwanie błędów
logicznych
Dane Wykonanie programu Wyniki
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 zródłowej co pokazuje większa pętla.
Czasami również będzie konieczność jej rozszerzenia tzn. zmiany algorytmu.
38
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:
Znalezć 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 e" 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.
39
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.
START
Wprowadz: n,m
Kształty Wejścia/
Wyjścia
a := n
b:=m
Instrukcje
przypisania
r:= n mod m
Podjęcia decyzji
(sterowanie)
NIE
r`"0
TAK
n := m
m := r
Wypisz:
NWD(a,b)= m
W Wordzie elementy graficzne
występują w zakładce :Rysuj
KONIEC
Autokształty: Schematy blokowe,
Strzałki blokowe
40
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:
n mod m = n - m
�łn m�ł
gdzie: - podłoga z dzielenia liczb n i m.
�łn 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:
x - 1< d" x d" < x + 1
�łx�ł �łxłł
+ = n
Dla każdej liczby całkowitej n:
�łn / 2�ł �łn / 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
41
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 10 20 30 40 50
algorytmu
n 0,000 01s 0,000 02s 0,000 03s 0,000 04 0,000 05
n2 0,000 1s 0,000 4s 0,000 09s 0,001 6s 0,002 5s
n3 0,001s 0,008s 0,027s 0,064s 0,125s
2n 0,001s 1,0s 17,9min 12,7dni 35,7
lat
3n 0,59s 58min 6,5 3855 2*106
lat wieków wieków
n! 3,6s 756 8,4*106 9,6*1048 2,6*1066
wieków wieków wieków 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 +,*,- /.
42
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(n2) kwadratowa Sortowanie bąbelkowe
O(n3) sześcienna Mnożenie macierzy
O(2n) 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).
43
Analiza algorytmu przeszukiwania sekwencyjnego
Problem przeszukiwania ( lub też wyszukiwanie) jest określany następująco:
Dane:
Ciąi n liczb a1, a2,K, an w tablicy a[] i element x
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)
W każdym obiegu pętli for
1 for k:=1 to n do
sprawdza się czy element
2 if x=a[k] then
tablicy jest równy
3 return k
szukanemu elementowi x
(wiersz2) . Jeśli tak jest
4 return 1
zwracana jest wartość
indeksu k (wiersz 3)
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 zdarzenia � że algorytm wykona k porównań przy poszukiwaniu
k k,
wartości x wynosi:
44
p
(k = 1,2,K, n - 1
n
pk =
p
+ (1 - p) (k = n)
n
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 pk dla k=n jest sumą zdarzeń.
Niech X oznacza zmienną losową, której wartościami są liczby porównań
n
wykonywanych przez algorytm dla danych rozmiaru n:
X (�k )= k (k =1,2,K,n)
n
X nie wystąpi w ciągu
Jej wartość oczekiwana wynosi:
n n n
p p
E(Xn)=
"X (�k )pk = "k n + n(1- p)= n "k + n(1- p)=
n
k =1 k =1 k =1
p n(n +1) p p
�ł
= + n(1- p)= n�ł1- +
�ł �ł
Ale taka suma =n(n+1)/2
n 2 2 2
�ł łł
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ą:
p p
�ł
A(n)= E(Xn)= n�ł1- +
�ł �ł
2 2
�ł łł
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.
45
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.
46
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 przejdz 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)
47
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) :
>> PowtarzajObl1
Rys. 1b. Przykład wyników
POWTARZANIE OBLICZEN
testowania programu
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
>>
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.
48
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 8. Wyświetl wartość zmiennej Sum. Koniec
Rys. 2 Schemat blokowy
Pseudokod programu:
Początek Program SumaLiczb
zmienne:
n, i - całkowite
Wczytaj: n
liczba, Sum- rzeczywiste
początek
i :=0
czytaj(n)
Sum=0.0
i:=0
Sum:=0
powtarzaj dopóki i < n
Wczytaj: liczba
czytaj(liczba)
i:=i+1
Sum:=Sum +liczba
i :=i+1
pisz(Sum)
koniec
Sum :=Sum +liczba
Nie/False
Wyświetl:
i < n
Sum
Tak/True
Koniec
49
Poniżej przedstawiono różne formy zapisu tego algorytmu w pseudokodzie.
a) b)
Pseudokod programu: Pseudokod programu:
Program SumaLiczb Program SumaLiczb
zmienne zmienne
n, i- całkowite n, i- całkowite
liczba, Sum- rzeczywiste liczba, Sum- rzeczywiste
początek begin
czytaj(n) read(n)
i:=0 i:=0
Sum:=0 Sum:=0
powtarzaj dopóki i < n while i < n do
czytaj(liczba) read(liczba)
i:=i+1 i:=i+1
Sum:=Sum +liczba Sum:=Sum +liczba
pisz(Sum) write(Sum)
koniec end
c) d)
Pseudokod programu:
Pseudokod programu:
Program SumaLiczb
Program SumaLiczb
zmienne
zmienne
n, i- całkowite
n, i- całkowite
liczba, Sum- rzeczywiste
liczba, Sum- rzeczywiste
begin
begin
read(n)
read(n)
i:=0
Sum:=0
Sum:=0
for i:=1 step 1 until n do
do
begin
read(liczba)
read(liczba)
i:=i+1
Sum:=Sum +liczba
Sum:=Sum +liczba
end
while i < n
write(Sum)
write(Sum)
end
end
50
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 (md"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):
Wprowadzanie danych oraz Wprowadzanie danych oraz
określenie n oraz m określenie n oraz m
1. Nadaj zmiennym wartości : 1. Nadaj zmiennym wartości:
n :=0 m:=0 min=999999 n :=0 m:=0
2. Wczytaj liczbę do zmiennej x. 2. Wczytaj liczbę do zmiennej x.
3. Jeśli x=0 lub n=99 to pkt. 8. 3. Zapamiętaj x jako min: min:=x
4. Aktualizuj ilość wczytanych liczb: 4. Jeśli x=0 lub n=99 to pkt. 11
n:=n+1 5. Aktualizuj ilość wczytanych:
5. Jeśli x>0 to m=m+1 n:=n+1
6. Jeśli x >0 and x < min to: 6. Jeśli x>0 to m=m+1
min:= x 7. Jeśli min<0 to min=x
7. Przejdz do kontynuacji od pktu 2. 8. Jeśli x >0 and x < min to:
Wydruki wyników min:= x
8. Jeśli m>0 to drukuj wartości: 9. Wczytaj liczbę do zmiennej x
n=..... m=.......min=........ 10. Przejdz do kontynuacji od punktu. 4
W przeciwnym razie drukuj: Wydruki wyników
Brak Liczb dodatnich 11. Jeśli m>0 to drukuj wartości:
n=....... n=..... m=.......min=........
9. Koniec W przeciwnym razie drukuj:
Brak Liczb dodatnich
n=.......
12. Koniec
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.
51
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 1): Pseudokod programu(Wersja 1):
Wprowadzanie danych oraz Program MAX
określenie n oraz m zmienne
1. Nadaj zmiennym wartości początkowe: n,m - całkowite
n :=0 m:=0 min=999999
x, min- rzeczywiste
2. Wczytaj liczbę do zmiennej x. begin
3. Jeśli x=0 lub n=99 to przejdz do n:=0, m:=0 min=999999
pkt. 8.
read(x)
4. Aktualizuj ilość wczytanych liczb: while (n < 99 & x `" 0) do
n:=n+1 begin
5. Jeśli x>0 to m=m+1
n:=n+1
6. Jeśli x >0 and x < min to wykonaj if x>0 then m:=m+1
operacje: min:= x if (x>0 & x7. Przejdz do kontynuacji od punktu.2.
read(x)
Wydruki wyników end
8. Jeśli m>0 to drukuj wartości: if m>0
n=..... m=.......min=........
write(n, m, min)
W przeciwnym razie drukuj: else
Brak Liczb dodatnich write(n, Brak liczb dodatnich)
n=.......
end
9. Koniec
Lista kroków (wersja 2):
Pseudokod programu (wersja 2)::
1. Nadaj zmiennym wartości:
Program MAX
n :=0 m:=0
zmienne
2. Wczytaj liczbę do zmiennej x.
n,m - całkowite
3. min:=x
x, min- rzeczywiste
4. Jeśli x=0 lub n=99 to pkt. 11
begin
5. Aktualizuj ilość wczytanych: n:=n+1
n:=0, m:=0
6. Jeśli x>0 to m=m+1
read(x)
7. Jeśli min<0 to min=x
min:=x
8. Jeśli x >0 and x < min to:
while (n < 99 & x `" 0 ) do
min:= x
begin
9. Wczytaj liczbę do zmiennej x
n:=n+1
10. Przejdz do kontynuacji od punktu.4
if x>0 then m:=m+1
Wydruki wyników
if nin<0 then min:=x
11. Jeśli m>0 to drukuj wartości:
if (x>0 & xn=..... m=.......min=........
read(x)
W przeciwnym razie drukuj:
end
Brak Liczb dodatnich
if m>0 then
n=.......
write(n, m, min)
12. Koniec else
write(n, Brak liczb dodatnich)
end
52
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 (md"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
Pseudokod programu
Lista kroków
Program MIN DODATNIA
Wprowadzanie danych oraz określenie n oraz m
zmienne
1. Nadaj zmiennym wartości początkowe:
n,m, i- całkowite
n :=0 m:=0 i=0
x, min- rzeczywiste
2. Wczytaj liczbę do zmiennej x.
begin
3. Jeśli x=0 lub n=99 to przejdz do pkt.7.
n:=0, m:=0, i=0
4. Zapamiętaj x w tablicy:
read(x)
n:=n+1 A[n]:=x
while (n <99 & x `" 0) do
5. Jeśli x>0 to m=m+1 min:=x
begin
6. Przejdz do kontynuacji od punktu. 2
n:=n+1 A[n]:=x
Wyszukiwanie min (jeśli były liczby dodatnie)
if x>0 then
7. Jeśli m=0 lub n=0 to przejdz do pkt.12 begin
m:=m+1 min:=x;
8. Zwiększ i:=i+1
end
9. Jeśli A[i] > 0 and A[i] < min to wykonaj:
read(x)
min:= A[i]
end
11 Jeśli i < n to kontynuuj od pkt 8.
for i:=1 step 1 until n do
Wydruki wyników
begin
12. Jeśli m>0 to drukuj wartości:
if A[i]>0 & A[i] < min then
n=..... m=.......min=........
min:=A[i]
W przeciwnym razie drukuj: end
Brak Liczb dodatnich
if (m>0 and n>0) then
n=.......
write(n, m, min)
13. Koniec
else
write(n, Brak Liczb dodatnich )
end
53
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
Pseudokod programu:
Lista kroków (wersja 1):
Program CZY_PIERWSZA
Zmienne
1. Wczytaj wartość n.
n, podz- całkowite
2. podz:=2 pierwsza: logiczna
begin
3. Jeśli n mod podz =0 to:
read(n)
Pisz(To nie pierwsza)
pierwsza=true podz:=2
Przejdz do punktu 7
while (pierwsza=true) and (podz < n)
4. podz:=podz+1
begin
5. Jeśli podz < n to przejedz do 3
if (n mod podz =0) then
6. Pisz (To liczba pierwsza)
pierwsza=false
else
7. Koniec
podz:=podz+1
end
if (pierwsza=true)
Początek
write(n, To liczba pierwsza)
else
Wczytaj: n
write(n, To nie pierwsza)
end
podz :=2
True
True
True
True
n mod podz- to działanie
n mod podz
wyznacza resztę z
dzielenia całkowitego
False
False
False
False
n/podz
np.: 11 mod 2=1
podz :=podz+1
10 mod 2=0
True
True
True
True
podz < n
Wyświetl: To nie
False
False
False
False
jest Licz. Pierwsza
Wyświetl: Licz. Pierwsza
Koniec
54
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ę.
55
Zadanie 6
Opracuj rekurencyjny algorytm programu który oblicza wartość 2n , 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:
0
=
2 1 dla n=0
n-ta potęga liczby 2=
n n-1
= *
2 2 2
dla n>0
Specyfikacja algorytmu:
Dane wejściowe:
n wykładnik (ne"0) jest liczbą przekazywaną do funkcji przez tzw. wartość.
Wynik:
np2- liczba całkowita, wartość n-tej potęgi liczby 2 (tzn. 2n).
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
Obrazy wyników są
Aktualne wyniki
pobierane ze stosu i
są odkładane na
uzupełniane (cofanie
Etap 4 potega(0)=1
stosie (zejście w
rekurencji)
głąb stosu)
Wartość już znana !
Można już cofać się
wyznaczając potega(1),
potega(2) itp. aż do
potega(3)
56
Formularz kolokwium zaliczającego ćwiczenie rachunkowe
Przykład
57
GRUPA B
B & & & & & & ..& & & & & & & & & & & & & & ..Grupa E0X& & &
B
B
Wpisz wyżej: Nazwisko i imię, grupę (drukowanymi - wyraznie! ) 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ą.
= 113D.
2. (1pkt) Zapisz w kodzie ZM podaną liczbę.
= -112D
3. (1pkt) Zapisz w kodzie U1 podaną liczbę.
= -112D
4. (1pkt) Zapisz w kodzie U2 podaną liczbę
= -112D
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: 108D = & & . h
c) zamień na postać dziesiętną: B6Ah =& & & ..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,375D
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ą.
58
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 d" 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 d" b d" 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, niezle!
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.
59
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ądz 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 awykonaj 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 awykonaj 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].
60
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.
61
62

Wyszukiwarka

Podobne podstrony:
program przedmiotu metody i techniki reklamy?ukacja studia niestacjonarne
Metody i techniki stosowane w biologii molekularnej
MS Access 2000 PL Zaawansowane techniki programowania
metody i techniki terapeutyczne
Metody i techniki pobudzania kreatywnosci w organizacji i zarzadzaniu
metody i techniki reklamy?ukacja 1
Metody, techniki i narzedzia
Rozmowy telefoniczne Metody i techniki

więcej podobnych podstron