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:
Temat 1: Konwersje i zapis liczb w różnych systemach (2godz.)
Temat: 2 Kody ZM,U1,U2. Operacje arytmetyczne. (2 godz.)

Temat: 3 Analiza problemu i specyfikacja algorytmu

(2 godz.)

Temat 4. Projektowanie algorytmów. (2 godz.)

Temat 5.

Kolokwium z tematów 1-4 (2 godz)

Informacja o kolokwium zawarta jest w końcowej części materiału.
(dołączyć przykład testu)

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:

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

Konwersja liczb pomiędzy różnymi systemami

Dla znalezienia wartości dziesiętnej liczby zapisanej w innym systemie

pozycyjnym wygodnie jest skorzystać z definicji. W systemie dwójkowym jest
to proste, gdyż cyfry 0 lub 1 występujące jako mnożniki wag dają 0 lub wagę,
która jest odpowiednią potęgą 2).

Np.: liczba

1 1 0 1 0 1

b

ma jedynki na poz. o wagach 1,4,16 i 32, a jej

wartość dziesiętna wynosi 1+4+16+32 = 53

Cyfry dwójkowe

1

1

0

1 0 1

Wagi

2

5

2

4

2

3

2

2

2

1

2°

Liczba

0,1101b

ma jedynki na pozycjach o wagach równych ½, ¼, i

1/16,

- jej wartość dziesiętna wynosi ½+ ¼ + 1/16 =13/16

Cyfry dwójkowe:

0 , 1 1 0 1

Wagi  2

0

, 2

-1

2

-2

2

-3

2

-4

W systemach innych niż dwójkowy trzeba wykonać mnożenie; np.

Np. dla liczby:

1BC5

h mamy:

Cyfry szesnastkowe

1

B

C

5

Wartość cyfr

11

12

5

Wagi

16

3

=4096

16

2=

256

16

1

=16

16°=1

Czyli liczba

1BC5h =

1x4096 +11x256 +12x16 + 5x1 =

7109(

10)

Przydatność zapisu szesnastkowego polega głównie na tym, że pozwala on

zapisywać w zwięzłej postaci łańcuchy dwójkowe (nie zawsze reprezentujące
liczby), które to łańcuchy w sposób naturalny opisują stan urządzeń cyfrowych.

Z faktu, że 16 = 2

4

wynika, że 4 cyfry dwójkowe mogą być zastąpione przez 1

cyfrę szesnastkową.

Konwersja z systemu hexsadesymalnego na binarny lub odwrotnie jest

bardzo prosta. To duża zaleta systemu hexsadesymalnego. Wymaga jedynie
zastąpienia poszczególnych cyfr szesnastkowych czwórkami bitów (tetradami)
lub odwrotnie np.:

1 1 0 1

0 0 1 1

1 0 0 1

0 1 0 1

D

3

9

5

15

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.

16

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.

17

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.

18

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 powyzszego 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|

:

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.

19

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)

, gdzie x ≥ 0

Przykład zastosowania sposobu B:

Pierwszy składnik dla n=8 wynosi –128 i

jest to waga bitu znaku.

Stąd dla liczby a=-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

-128 106

= -22

(10)

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=

20

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

.

21

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

-

1

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

- 1 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.

22

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).

23

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ą !

24

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.

25

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

,,,,

26

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

27

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

28

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

29

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ę.

30

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.

31

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.

32

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

33

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;

34

•

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.

35

T3

ALGORYTMY- SPOSOBY PREZENTACJI

RODZAJE ALGORYTMÓW

ZŁOZONOŚĆ OBLICZENIOWA

PRZYKŁADY PROJEKTOWANIA ALGORYTMÓW

36

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 ).

37

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.

38

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 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.

39

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)

40

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.

41

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)

42

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

43

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 +,*,- /.

44

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).

45

Analiza algorytmu przeszukiwania sekwencyjnego

Problem przeszukiwania określony jest też jako wyszukiwania. Jego specyfikacja
jest następująca:
Dane:

x

element

i

a

tablicy

w

a

a

a

liczb

n

Ciąi

n

[]

,

,

,

2

1

K

Wynik:

Indeks „k” taki, że x=a

k

lub –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 prawdopodo-bień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

prawdopodo-bień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)

46

)

(

)

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

47

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.

48

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)

49

>> 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.

50

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ść 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

51

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

52

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

53

Poniżej, dla ułatwienia analizy powtórzono algorytm dla zadania 3 w
postaci listy kroków i przedstawiono 2 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

54

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

55

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

56

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ę.

57

Istotę rekurencji i jej zaletę przedstawiono poniżej.
Mamy obliczyć wartość 2N . Jak to zrobić aby nie użyć operacji potęgowania ?


Sposób 1. – Skorzystanie ze wzoru:

A

N

= e

N*ln(A)

czyli 2

N

= e

N*ln(2)

Zakładając dostępność funkcji e

x

oraz ln(x) są dostępne we wspomnianym

języku to wydaje się, że obliczenie nie sprawi problemu (dotyczy tu liczb A, N>0).
Ale wynik powinien być liczbą całkowitą a obliczenie wg wzoru tego nie zapewnia.

Sposób 1. – Skorzystanie ze wzoru:
2

N

=( 2

N-1

)*2

i iteracyjnie obliczamy kolejno:
2

0

= 1

2

1

= ( 2

0

)* 2

2

2

=( 2

1

)* 2

2

3

=( 2

2

)* 2

2

4

=( 2

3

)* 2

2

5

=( 2

4

)* 2

....................
2

N

=( 2

N-1

)* 2

Sposób 2. - Rekurencyjnie stosując
tzw. metodę „dziel i zwyciężaj”

( )

 

( )

e

nieparzyst

N

gdy

parzyste

N

gdy

N

gdy

N

N

N

−

−

=

=

2

2

2

2

2

2

2

*

2

0

1

gdzie:└ ┘-oznacza zaokrąglenie w dół do najbliższej liczby całkowitej

Powyższy algorytm jest logarytmicznym.
Np. dla N=1000 2

N

= ok. 10

301

– niewyobrażalnie dużo obliczeń !!!.

Uwaga: Np. dla

N=1000

w

kolejnych krokach
wykładnik „x” wynosi:

- X= 1000/2=

500

-

X= 500/2=

250

-

X= 250/2=

125

-

X= 125/2=

62

- X= 62/2=

31

- X= 31/2=

15

itd.

Aby wykonać obliczenia
trzeba wykonać rekurencję
10 razy a to:

lg

2

1000=9.97≈ 10

Ale liczba obliczeń jest i tak

duża, ale zależy ona tylko od N

(liniowo)

Oczywiście można obliczyć to

obliczyć rekurencyjnie:

2

N

= ( 2

N-1

)* 2 zstępująco

2

N-1

= ( 2

N-2

)* 2 itp.

58

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)

59

Formularz kolokwium zaliczającego ćwiczenie rachunkowe

Przykład

60

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ą.

61

SPRAWOZDANIE Z WYKONANIA ĆWICZENIA LABORATORYJNEGO

Przykład

Temat: ……… Wykonywanie obliczeń z wykorzystaniem pętli typu for.

Nazwisko i imię:
(drukowane)

KOWALSKI

MICHAŁ

Data wykonania:

30.10.2008

Grupa: E8X3S1
Podgrupa: A

Prowadzący:

Mgr inż. Wójcik

Jerzy

1. Treść zadania

Zadanie

1

Sformułuj algorytm i napisz program obliczający sumę ciągu n liczb

wprowadzanych do komputera. Ilość liczb jest pierwszą wprowadzaną wartością.

Wyświetl wyniki podając w jednym wierszu ilość sumowanych liczb i wynik. To

wyświetlanie zrealizuj dwoma sposobami: stosując instrukcje sprintf i disp.

Przedstaw algorytm obliczeń w postaci listy kroków, schematu blokowego i zapisu

w pseudokodzie.

2.

Specyfikacja algorytmu. Lista kroków.

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:

9.

Wczytaj z klawiatury liczbę określającą ilość liczb i zapisz ją w zmiennej

n

.

10.

Zmiennej

Sum

przypisz wartość początkową

0

.

11.

Zmiennej

i

przypisz wartość początkową

0

.

12.

Wczytaj wartość liczby wprowadzonej z klawiatury

i zapamiętaj ją w zmiennej

liczba

.

13.

Zwiększ wartość licznika

i

o

jeden

.

14.

Do dotychczasowej sumy (

Sum

) dodaj wczytaną liczbę (

liczba

).

15.

Jeśli

i <n

to wróć do kroku 4.

16.

Wyświetl wartość zmiennej

Sum

. Koniec

62

3. Schemat blokowy algorytmu.

3. Program w Matlabie

4. Przykład wyników testowania

Poniżej zamieściłem przykład testowania programu.
Widoczne są tu dwa podstawowe okna:

 Command
 Workspace

Przedstawiają one treść konwersacji przy wprowadzaniu danych i wyprowadzaniu wyników
oraz typu zmiennych i zajętość pamięci (okno Workspace).

Wczytaj: n

i :=0

Sum=0.0

i < n

Wyświetl:
n, Sum

Początek

Koniec

i :=i+1

Sum :=Sum

+liczba

Wczytaj: liczba

Tak/True

Nie/False

63

2. Sposób realizacji zadania. Wnioski

Celem było sumowanie liczb. Ponieważ z treści wynika, ilość liczb
jest znana to jest ona pobierana jako pierwsza dana i podstawiana do zmiennej n.
Następnie program powtarza n razy iterację:

 Pobiera liczbę do sumowania;
 Dodaje liczbę do dotychczasowej sumy.

Ponieważ ilość powtórzeń jest znana to zastosowałem pętlę for- jako najprostsze
rozwiązanie.
Wyprowadzanie wyników wymagało wyprowadzenia informacji w postaci
komunikatu wyświetlonego w jednym wierszu. Zrealizowałem to następująco:
I-sposób

Wstawiam dane w odpowiednie miejsca tekstu, który ma być

wydrukowany. W programie do przechowywania tekstu użyłem zmiennej
komunikat. Tekst reprezentowany zmienną takstową jest macierzą wierszową
zawierającą ciąg znaków ASCII. Jest to widoczne w oknie Work Space.
Kody ASCII można podejrzeć wykorzystując instrukcję konwersji double w
sposób jak niżej:

>> kody=double(komunikat)
kody =

Columns 1 through 17

83 117 109 97 32 53 32 108 105 99 122 98 32 119 121 110 111
Columns 18 through 33

115 105 58 32 83 117 109 61 32 51 55 46 53 54 57 55

Odwrotną zamianę realizuje funkcja char jak pokazałem poniżej:

>> char(kody)
ans =

64

Suma 5 liczb wynosi: Sum= 37.5697

>>

Instrukcja sprintf umożliwia wstawienie danych w odpowiednie m-ca tekstu.
Instrukcja zawiera tekst (‘...........’) i listę wartości zmiennych wstawianych w
tym tekście. Miejsca wstawiania są zaznaczone znakami % ( np. wiersz 21), po
których jest określenie formatu (tu całościowo określają go litery %d i %f
stosownie do typu zmiennych.)
II – sposób

Użycie tylko instrukcji disp wymaga łączenia stringów. Można to

zrealizować używając tej instrukcji w postaci disp([teksty laczone]).
Lączone teksty składowe muszą być oddzielone przecinkami. Wstawienie liczby
jako elementu tekstu wymaga konwersji liczby na tekst. I tak:

 int2str(n)- zamienia liczbę całkowitą n na ciąg znaków ASCII;
 num2str(Sum)- zamienia liczbę rzeczywistą na ciąg znaków ASCII.

Reasumując, mogę powiedzieć, ze napisany program działa poprawnie i
realizuje postawione zadanie

.

65

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 chyba nie jesteś orłem.
 No, nieźle!
 Brawo. 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.

66

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].

67

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.

68

Zadanie 24

Sformułuj algorytm napisz program, który dla zadawanej wartość x (powinna to
być liczba całkowita <1000) określi jej strukturę np. dla liczby 73 w postaci:

 Setek- 0
 Dziesiątek- 7
 Jedności 3

Zadanie 25

Sformułuj algorytm napisz program, który dla podawanych zarobków osób A i
B (wynoszących np. 1183 zł i 834 zł) określi jakie nominały (200, 100, 50, 20,
10, 5, 2, 1zł) i w jakiej liczbie trzeba posiadać, żeby bez potrzeby rozmieniania
wypłacić obu osobom dokładnie należne kwoty.

Zadanie 26

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 określi wartość ekstremalną funkcji w
przedziale [wd,wg]. Wartości a, b, c oraz wd i wg są wczytywanymi danymi
(wd<wg).
Uwaga: Ekstremum wyznaczyć metodą poszukiwania.

Zadanie 27

Sformułuj algorytm i napisz program, który pobierze n liczb i zapamięta je w
wektorze A[1:n], a następnie tak przestawi liczby w wektorze A tak, by były one
uporządkowane niemalejąco tzn: najmniejsza wartość powinna znaleźć się w
A[1] a największa w A[n], a dla każdej pary A[i-1] i A[i] powinna zachodzić
relacja A[i-1] ≤ A[i].

Wskazówka:
Szukaj max elementu i zamień jego wartość z ostatnim n-tym elementem tablicy. Następnie
ponownie szukaj w tablicy max elementu (ale spośród n-1 elementów) i zamień go z
elementem n-1 itp. Np.
Dla n=6 mamy przykładowo dane: A=[3, 7, 1,11,6,4]- dane wejściowe

Kolejno otrzymamy: A=[3, 7, 1, 4,6,11]

A=[3, 6, 1, 4,7,11]
itp. aż do:
A=[1, 3, 4, 6,7,11]- dane uporządkowane!

Zadanie 28

Sformułuj algorytm i napisz program, który pobierze n liczb i zapamięta je w
wektorze A[1:n], a następnie tak przestawi liczby w wektorze A tak, by były one
uporządkowane malejąco tzn: największa wartość powinna znaleźć się w A[1] a
najmniejsza w A[n], a dla każdej pary A[i-1] i A[i] powinna zachodzić relacja
A[i-1] ≥ A[i].

69

Zadanie 29

Sformułuj algorytm i napisz program, który:

 Pobierze dwie nieujemne wartości xa oraz xb takie, że 0≤ xa< xb oraz xb

≤ 180 stop.



obliczy pole powierzchni wyznaczone przebiegiem funkcji sin(x) w

przedziale [xa, xb]

.

Wskazówka:
W przedziale [xa,xb] możesz narysować prostokąt o małej wartości boku (np. 1/100
długości przedziału) na osi x i wysokości takiej jaką przyjmuje wartość funkcji sin w
miejscu wrysowania. Jeśli pokryjesz przedział [xa,xb] dużą liczbą kolejno po sobie
wrysowanych prostokątów o ustalonej wartości boku na osi x to sumując ich pola
możesz w przybliżeniu wyznaczyć pole powierzchni pod krzywą sin w zadanym
przedziale.

Zadanie 30

Sformułuj algorytm i napisz program, który:

 Pobierze liczby a,b,c (współczynniki równania kwadratowego),



obliczy pole powierzchni położonej między osią x a krzywą wyznaczoną

przez równanie.

Zadanie 31

Sformułuj algorytm i napisz program, który będzie wczytywał liczby całkowite,
nieujemne i informował ile bitów jest niezbędne aby przedstawić daną liczbę w
naturalnym kodzie binarnym (NKB).

Zadanie 32

Sformułuj algorytm i napisz program, który będzie zamieniał liczbę dziesiętną
N, całkowitą i bez znaku na liczbę w naturalnym kodzie binarnym (NKB) i w
zależności od wielkości zadanej liczby przedstawiał ją na 8 lub 16 bitach.
Przyjmij, że max zadawana liczba N to 65536.

Wskazówka:
Dzieląc zadaną liczbę przez podstawę systemu binarnego (tzn. 2) otrzymujemy pewien wynik
całkowity i resztę 0 lub 1. Reszta to kolejna cyfra zapisu binarnego. W dalszym postępowaniu
wynik traktujemy jako liczbę i kontynuujemy postępowanie, aż do chwili gdy wynik ma
wartość 0. Otrzymane cyfry reszt zapisane w kolejności odwrotnej przedstawiają zapis
binarny liczby N.

Zadanie 33

Sformułuj algorytm i napisz program, który dla podawanych ciągów binarnych
będzie określał jaką liczbę dziesiętną one określają.

Zadanie 34

Sformułuj algorytm i napisz program, który będzie zamieniał liczbę dziesiętną
N, całkowitą i bez znaku na liczbę heksadecymalną.

Zadanie 35

Sformułuj algorytm i napisz program, który będzie zamieniał liczbę
heksadecymalną na liczbę dziesiętną. Przyjmij, że ilość cyfr liczby
heksadecymalnej nie przekracza 8.

Wskazówka:

70

W ogólnym przypadku liczba heksadecymalna jest zmienną tekstową. Zastosuj stosowne funkcje
Matlaba umożliwiające analizę tekstu.

Zadanie 36

Sformułuj algorytm i napisz program, który będzie zamieniał liczbę dziesiętną
N, całkowitą i bez znaku na liczbę w naturalnym bodzie binarnym (NKB) i w
zależności od wielkości zadanej liczby przedstawiał ją na 8 lub 16 bitach.
Przyjmij, że max liczba N to 65536.

Wskazówka: Przyjmij wagi poszczególnych bitów systemu binarnego :b

7

,b

6

....,b

1

, b

0

. ( np. dla

8 bitów będą to wartości:b

7

=128 b

6

=64...........b

1

=2 b

0

=1. Liczbę N można przedstawić jako

sumę iloczynów wartości bitów i wag:
N=X

7

*128 +X

6

*64+..........X

1

*2+X

0

*1 (gdzie: X

i

mają wartość o lub 1).

Jeśli dana waga występuje to odpowiada jej jedynka jeśli nie 0. Np. N= 96 można zamienić
na binarną metodą doboru wag. I tak waga 128 ponieważ jest większa od liczby N to nie może
wchodzić w skład sumy wag czyli wartość bitu b

7

=0. Kolejna największa waga 64 jest

mniejsza od N czyli musi być wybrana stąd b

6

=1. Pozostaje do „zagospodarowania” N=96-

64=32. Z tą liczbą postępujemy podobnie jak poprzednio. Postępowanie kontynuujemy dopóki
N>0.

Zadanie 37

Sformułuj algorytm i napisz program, który będzie zamieniał liczbę dziesiętną
N, całkowitą i bez znaku na liczbę w systemie oktalnym.

Zadanie 38

Sformułuj algorytm i napisz program, który będzie zamieniał liczbę oktalną na
liczbę dziesiętną.

Wskazówka:
Potraktuj, że wczytywana liczba jest zmienną tekstową. Zastosuj w algorytmie funkcje
stosowne w Matlabie, umożliwiające analizę tekstu. Wartości dziesiętne kodu ASCII dla
kolejnych cyfr to: 0-48, 1-49, 2-50,3-51 ...,9-57. W Matlabie kody ASCII można uzyskać
stosując funkcję double. Np

A=double(‘347’) da wynik w postaci macierzy liczb: A=[51 52 55].

Odwrotna funkcja zamieniająca kod ASCII na liczbę to char. Np. char(51)=3.

Zadanie 39

Sformułuj algorytm i napisz program, który po wprowadzeniu imienia będzie
identyfikował płeć.
Program powinien informować o wyniku identyfikacji w postaci:
To prawdopodobnie imię męskie! lub To prawdopodobnie imię męskie!

Wskazówka:
Wypisz kilka imion żeńskich. Na jaką literę się najczęściej kończą. Spróbuj to wykorzystać w
algorytmie.

Zadanie 40

Sformułuj algorytm i napisz program, który będzie zamieniał liczbę dziesiętną
N, całkowitą i bez znaku na liczbę w wybranym systemie o R=4 lub R=8.
Efektem programu powinna być informacja:
Podana liczba D=xxxx w systemie o podstawie R=yy ma następujące cyfry:
C1 C2 .....itp...

Zadanie 41

Sformułuj algorytm i napisz program, który będzie zamieniał liczbę z
dowolnego systemu o podstawie R na liczbę dziesiętną

71

Zadanie 42

Sformułuj algorytm i napisz program, który będzie zamieniał podaną liczbę
ułamkową na liczbę binarną 16 bitową i wartość tej liczby wyświetlał w postaci
heksadecymalnej.

Zadanie 43

Sformułuj algorytm i napisz program, który będzie zamieniał podaną liczbę
całkowitą dodatnią lub ujemną na kod U2 i przedstawiał jej wartość w postaci 4
cyfr heksadecymalnych.

Uwaga:
Zadbać by wprowadzana liczba nie przekroczyła zakresu, który może być przedstawiony
czterema cyframi heksadecymalnymi.

Zadanie 43

Sformułuj algorytm i napisz program, który będzie wczytywał ciąg liczb do
momentu wpisania liczby 0 i dla wczytanego ciągu wyznaczy liczbę minimalną
i maksymalną.

Zadanie 44

Sformułuj algorytm i napisz program, który będzie wczytywał ciąg liczb
dodatnich do momentu wpisania liczby 0 i dla wczytanego ciągu wyznaczy
wartość średnią i odchylenie standardowe.

Uwaga:
Spróbuj, czy potrafisz rozwiązać ten problem bez pamiętania w tablicy wczytywanych
wartości.

Zadanie 45

Sformułuj algorytm i napisz program, który będzie wczytywał ciąg liczb do
momentu wpisania liczby 0 i dla wczytanego ciągu wyznaczy wartość
najmniejszej liczby dodatniej (jeśli były takie liczby).

Zadanie 46

Sformułuj algorytm i napisz program, który będzie wczytywał ciąg liczb do
momentu wpisania liczby 0 i dla wczytanego ciągu wyznaczy wartość
największą liczby ujemnej (jeśli były takie liczby).

Zadanie 47

Sformułuj algorytm i napisz program, który będzie sprawdzał czy w ciągu
wczytanych n liczb występuje podana do sprawdzenia liczba x.

Zadanie 48

Sformułuj algorytm i napisz program, który określi jaki jest największy wspólny
dzielnik liczb dla podanej pary liczb n,m (n>m).

Uwaga:

72

Zastosuj odejmowanie od liczby większej liczby mniejszej do momentu otrzymania wyniku
zero. Po każdym kroku liczba, która była odjemną staje się liczbą większą a odjemnikiem staje
się liczb, która była różnicą.

Zadanie 49

Sformułuj algorytm i napisz program, który wczyta n-elementowy wektor
wierszowy A oraz macierz B i wykona operacją mnożenia A*B. Program
powinien kontrolować poprawność wprowadzania danych.

Uwaga:
Wykonaj to zadanie stosując wbudowane operacje macierzowe oraz bez stosowania tych
operacji.

Zadanie 50

Sformułuj algorytm i napisz program, który wczyta n-elementowy wektor
wierszowy A oraz macierz B i wykona operacją mnożenia B*A

T

. Program

powinien kontrolować poprawność wprowadzania danych.

Uwaga:
Wykonaj to zadanie stosując operacje macierzowe oraz bez stosowania tych operacji

Zadanie 51

Sformułuj algorytm i napisz program, który wczyta macierz A oraz macierz B i
wykona operacją mnożenia A*B. Program powinien kontrolować poprawność
wprowadzania danych.

Uwaga:
Wykonaj to zadanie stosując operacje macierzowe oraz bez stosowania tych operacji