Ws ze chnica Poranna

Proste rachunki wykonywane za pomocą komputera

prof. dr hab. Maciej M Sysło

prof. dr hab. Maciej M Sysło

Ze szyt dydaktyczny opracowany w ramach projektu edukacyjne go

— ponadre gionalny program rozwijania kompe tencji

uczniów szkół ponadgimna zjalnych w zakresie technologii
informacyjno-komunikacyjnych (ICT).

Warszawska Wyżs za Szkoła Informa tyki

ul. Lewartowskie go 17, 00 -169 Wars zawa

Projekt graficzny: FRYCZ I WICHA

Wars zawa 2009
Copyright © Wars za wska Wyżs za Szkoła Informatyki 2009
Publikacja nie jes t prze znaczona do sprze da ży.

Uniwersytet Wrocławski, UMK w Toruniu

[e-mail], s [e-mail]

< 4 >

Informa tyka +

Komputery nie przes ta ły być mas zynami ma tematycznymi – jak kiedyś je nazywano – i obe cnie służą rów-
nie ż do wykonywania różnych obliczeń. Wykład jes t poś więcony m.in. algorytmom obliczania : wartoś ci dzie -
się tnej liczby binarnej, pos taci binarnej liczby dziesiętnej, wartoś ci wielomianu, największego wspólnego
dzielnika dwóch liczb (algorytm Euklides a) ora z wartości potęgi. Motywacją dla wprowadzenia tych algoryt-
mów jes t chęć obja śnienia metody s zyfrowania informacji z kluczem publicznym RSA, pows zechnie s tos owa -
nej w kryptografii komputerowej. Na warszta tach uczniowie zapoznają się z komputerowymi demons tracja -
mi omówionych na wykładzie algorytmów ora z zaprogramują w ję zyku Pas cal lub C++ i przetes tują wybrane
algorytmy.

Te zaję cia s ą drugą częścią wprowadzenia do algorytmiki i programowania . Omawiane s ą wię c rów-

nie ż ogólne pojęcia z zakresu algorytmiki, jak s pe cyfikacja problemu, schematy blokowe algorytmów, pod-
s tawowe struktury danych (ciąg i tablica) ora z pra cochłonnoś ć (złożonoś ć) algorytmów. Na wars ztatach zo-
s tają wprowadzone podstawowe ins trukcje języka programowania (itera cyjna i warunkowa ora z procedura
i funkcja nies tandardowa), wystarczające do zaprogramowania i uruchomienia komputerowych realizacji al-
gorytmów omówionych na wykładzie. Przytoczono ciekawe przykłady za stos owań omawianych zagadnień.

Rozwa żania są prowadzone na elementarnym poziomie i do ich wysłuchania ora z wzięcia udzia łu

w wars ztatach wys tarczy znajomoś ć informa tyki wyniesiona z gimna zjum ora z matematyki na poziomie s zko-
ły ś redniej. Te zaję cia s ą adresowane do wszys tkich uczniów w szkołach ponadgimnazjalnych, zgodnie bo-
wiem z nową pods tawą programową, ks ztałceniem umiejętnoś ci a lgorytmicznego rozwiązywania problemów
mają być obję ci ws zys cy uczniowie.

Wprowadzenie ................................................................................................................................................. 5

1. Sys tem dziesiętny i s ys tem binarny ............................................................................................................. 5

2 . Obliczanie wartoś ci wielomianu – schemat Hornera .................................................................................... 6

3. Zamiany liczby binarnej na dziesiętną ...................................................................................................... 12

4 . Otrzymywanie binarnego rozwinięcia liczby dzie siętnej ............................................................................ 13

5. Szybkie obliczanie wartoś ci potęgi ............................................................................................................ 15

6. Algorytm Euklides a .................................................................................................................................... 16

7. Dodatek. Algorytm, algorytmika i algorytmiczne rozwią zywanie problemów – rozważania ogólne .......... 19

Literatura

............................................................................................................................................... 22

> Proste rachunki wykonywane za pomocą komputera

< 5 >

Komputery w dals zym ciągu s ą przede ws zys tkim ma szynami ma tematycznymi, chociaż użytkownik widzi
częs to teks ty i obra zy, słys zy muzykę , ogląda filmy. Wykład jes t poś wię cony algorytmom wykonywania ele -
menta rnych obliczeń, takich jak: obliczanie wartoś ci dzie siętnej liczby binarnej, pos taci binarnej liczby dzie -
siętnej, wartoś ci wielomianu, na jwięks zego wspólnego dzielnika dwóch liczb, wartoś ci potęgi.

Te zajęcia są drugą czę ścią wprowadzenia do algorytmiki i programowania. Omawiane s ą więc rów-

nież ogólne pojęcia z zakresu algorytmiki, jak specyfikacja problemu, s chematy blokowe algorytmów, pod-
stawowe s truktury danych (ciąg i tablica) oraz pracochłonnoś ć (złożoność) algorytmów. Na wars ztatach zo-
stają wprowadzone pods tawowe instrukcje ję zyka programowania (iteracyjna i warunkowa oraz procedura
i funkcja nie standardowa), wys tarczające do zaprogramowania i uruchomienia komputerowych realiza cji al-
gorytmów omówionych na wykładzie. Przytoczono ciekawe przykłady za s tosowań omawianych zagadnień.

Rozwa żania ogólne na temat algorytmiki, algorytmicznego myślenia i rozwiązywania problemów z po-

mocą komputerów s ą zamies zczone w Doda tku (rozdz. 7 ). Materiał tam za warty może być dobrym podsumo-
waniem zajęć.

Jako literaturę rozs zerzającą prowadzone tutaj rozwa żania polecamy podręczniki [2], a zwła s zcza

książki [5] i [6].

Obecnie w powsze chnym użyciu je st s ys te m dziesiętny, zwany też s ys temem dzie siątkowym. Komputery na-
tomias t wszys tkie operacje wykonują w s ys temie binarnym, zwanym również s ys temem dwójkowym. Oba
s ystemy, to dwa przykła dy tzw. s ys temu pozycyjnego zapis ywania wartości liczbowych. Powinny one być
Wam znane z lekcji ma tema tyki. Przypomnijmy jednak jeden i drugi s ys tem.

Liczba za pis ana w s ys temie dziesię tnym, np. 357, oznacza wartość, na którą s kładają się trzy s etki,

pię ć dziesią tek i siedem jednoś ci, a za tem wartoś ć tej liczby można zapisa ć jako 357 = 3

•

100 + 5

•

10 + 7

•

1,

a także jako 357 = 3

•

10

2

+ 5

•

10

1

+ 7

•

10

0

.

A za tem, dziesiętna liczba naturalna złożona z n cyfr:

d

n–1

d

n–2

... d

1

d

0

oznacza wartoś ć:

d

n–1

10

n–1

+ d

n–2

10

n–2

+ ... + d

1

10

1

+ d

0

10

0

.

(1)

Liczba 10 w tej reprezentacji na zywa się pods tawą s ystemu li-
czenia . Do zapis ywania liczb w s ys temie dziesiętnym s ą uży-
wane cyfry: 0, 1, 2, 3, 4, 5, 6, 7, 8 i 9. Ten spos ób reprezento-
wania liczb na zywa się s ys te m pozycyjnym, gdyż w tym s ys te -
mie znaczenie cyfry zależy od jej pozycji w cią gu cyfr, okre śla -
jącym liczbę. Na przykład, liczby 123 i 321 ma ją różną wartoś ć,
chocia ż s ą złożone z tych s amych cyfr, a liczba 111 jes t złożona
z trzech jedynek, z których ka żda ma inne znaczenie dla warto-
ści tej liczby.

Ws zys tkim są zna ne tzw. cyfry rzymskie: I, V, X, L, C, D. M. Oznaczają one odpowiednio

liczby: 1, 5, 10, 50, 100, 500, 1000. W tym s ys temie , liczba III ma dziesię tną wartość 3, a zatem każda
z cyfr w tej liczbie ma takie s amo znaczenie, a wartoś ć jes t obliczana prze z dodawanie wartości cyfr. Za -
pis z w tym s ys temie liczby 2009 i 2012. Na liczbach rzymskich trudno wykonuje się podstawowe dzia -
łania: dodawanie, odejmowanie i mnożenie. Liczby te były s tos owa ne przez Rzymian głównie do zapi-
s ywania wartoś ci liczbowych, a nie do wykonywania na nich działań.

Za pods tawę s ys temu liczenia można przyjąć dowolną liczbę naturalną p więks zą od 1, np. 2, 5, 8, 16 czy 60.
Je śli p jes t pods tawą s ys temu liczenia , to liczby w tym s ys temie są zapis ywane za pomocą cyfr ze zbioru {0,
1, ..., p – 1}.

Dwa tysiące lat prze d na s zą erą
Babilończycy s tosowali s ys tem kopowy
(tj. przy pods tawie 60) – przypuszcza
się, że s tąd wzią ł s ię podział ką ta
pe łnego na 360 stopni, godziny – na 60
minut, a minuty – na 60 s ekund.

< 6 >

Informa tyka +

W rozwa żaniach zwią zanych z komputerami pojawia ją się liczby w s ys tema ch o podstawach 2, 8 i 16. Nas zą
uwagę skupimy głównie na s ystemie o pods tawie 2, a o innych s ys tema ch jes t mowa w ćwiczeniach.

Jeśli p = 2, to s ys tem na zywa się binarnym lub dwójkowym
– cyfry liczby, zapisanej w tym s ys temie, mogą mieć wartoś ć
0 lub 1 i na zywają się bitami. Liczba naturalna a dana w s yste -
mie dzies iętnym ma na s tępującą pos tać w s ys temie binarnym
dla pewnego n:

a = b

n–1

2

n–1

+ b

n–2

2

n–2

+ ... + b

1

2

1

+ b

0

2

0

,

(2)

gdzie współczynniki b

n–1

, b

n–2

, ..., b

1

, b

0

są liczbami 0 lub 1. W skrócie pis zemy zwykle a = (b

n–1

b

n–2

... b

1

b

0

)

2

i cią g bitów w nawia sie na zywamy binarnym rozwinięciem liczby a . Na przykład mamy, 8 = (1000)

2

, 12 =

(1100)

2

, 7 = (111)

2

. Cyfra b

n–1

jest najbardziej znaczącą , a b

0

– najmniej znaczącą w rozwinię ciu liczby a.

Spos oby wykonywania działań w s ys temach innych niż dziesię tny są pros tym przenie sieniem za sad z s ys te -
mu dziesiętne go.

Jeśli się dobrze przyjrzymy wzorom oznaczonym prze z (1) i (2), to zauwa żymy, że przypominają one specjalne
wielomiany – ws półczynnikami tych wielomianów s ą cyfry rozwinięcia , a argumentem wielomianu – je st pod-
s tawa s ystemu liczenia . Aby wię c obliczyć wartoś ć dziesiętną liczby, danej w innym s ys temie , poznamy algo-
rytm, który służy do bardzo efektywne go obliczania wartości wielomianu.

Jednym z najważniejs zych kroków w algorytmach jes t powtarzanie tej samej czynności (operacji), czyli itera -
cja . W tym punkcie zilus trujemy iterację na przykładzie s zybkiego spos obu oblicza nia wartoś ci wielomianu.

Obliczanie wartoś ci wielomianu o zadanych współczynnikach
jes t jedną z najczęś ciej wykonywanych operacji w komputerze.
Wynika to z wa żne go ma tematycznego faktu, zgodnie z którym
ka żdą funkcję (np. funkcje trygonometryczne) można za s tą pić
wielomianem, którego pos tać zale ży od funkcji i od tego, jaką
chcemy uzyskać dokładnoś ć obliczeń.

Na przykład, obliczanie wartoś ci funkcji cos x w prze -

dziale 0 ≤ x ≤ π/ 2 z błę dem nie więks zym niż 0.0009, można za-
s tąpić obliczaniem wartości nas tępującego wielomianu:

cos x = 1 – 0.49670x

2

+ 0.03705x

4

.

Zacznijmy od prostych ćwiczeń.
Jeśli dane s ą wartoś ci współczynników a, b i c wielomianu s topnia 2:

w(x) = a x

2

+ bx + c,

to je go wartoś ć można obliczyć wykonując za znaczone mnożenia i dodawania: a

•

x

•

x + b

•

x + c, czyli 3 mnoże -

nia i dwa dodawania . Można także nieco inaczej – wyłączmy x z dwóch pierws zych składników – wtedy otrzy-
mamy:

w(x) = (a x + b)x + c

i dla tej pos taci obliczanie wartoś ci tego wielomianu przyjmuje pos tać: (a

•

x + b)

•

x + c, czyli są wykony-

wane tylko 2 mnożenia i dwa dodawania .

Za prekursora systemu binarnego uważa się
G.W. Leibniza, który w pracy opublikowanej
w 1703 roku zilustrował wykonywanie
czterech podstawowych działań
arytmetycznych na liczbach binarnych.

Ada Augus ta , córka Byrona , uznawana
pows zechnie za pierws zą programis tkę
komputerów, prze łomowe znaczenie
mas zyny analitycznej Ch. Babba ge’a ,
pierwowzoru późniejs zych komputerów,
upatrywała właś nie „w możliwoś ci
wielokrotne go wykonywania prze z
nią dane go cią gu instrukcji, z liczbą
powtórzeń z góry zadaną lub zależną
od wyników obliczeń”.

> Proste rachunki wykonywane za pomocą komputera

< 7 >

W podobny spos ób można prze ds tawić wielomian s topnia 3:

v(x) = a x

3

+ bx

2

+ cx + d

najpierw wyłączam x z pierws zych trze ch wyra zów, a na s tępnie wyłączamy x z dwóch pierws zych wyrazów
w nawia sie:

v(x) = a x

3

+ bx

2

+ cx + d = v(x) = v(x) = (a x

2

+ bx + c)x + d, = ((a

•

x + b)

•

x + c)

•

x + d.

Widać z tego os tatniego wzoru, że wartoś ć wielomiany s topnia 3 można obliczyć za pomocą 3 mnożeń i 3 do-
da wań.

Rozwa żmy tera z wielomian s topnia n:

w

n

(x) = a

0

x

n

+ a

1

x

n–1

+ ... + a

n–1

x + a

n

(3)

i zas tosujmy grupowanie wyrazów podobnie, jak w wielomianie s topnia 3 – najpierw wyłączamy x ze wszys t-
kich wyra zów z wyjątkiem os tatniego, a nas tępnie s tosujmy ten s am krok wielokrotnie do wyra zów, które
będą pojawiały się w najgłębs zych nawia sach, a ż pozos tanie jednomian:

w

n

(x) = a

0

x

n

+ a

1

x

n–1

+ ... + a

n–1

x + a

n

= (a

0

x

n–1

+ a

1

x

n–2

+ ... + a

n–1

)x + a

n

= ((a

0

x

n–2

+ a

1

x

n–3

+ ... + a

n–2

)x+ a

n–1

)x + a

n

=

= (...((a

0

x + a

1

)x+ a

2

)x +... + a

n–2

)x+ a

n–1

)x + a

n

(4)

Przeds taw w postaci (4) nas tępujące wielomiany:

w(x) = 3x

4

– x

3

+ 5x

2

+ 7x – 2

w(x) = x

5

– x

3

+ 4 x

2

+ 3x – 1

w(x) = x

6

– x

3

+ x

Zapiszmy teraz spe cyfikację, czyli dokła dny opis rozwa żanego tutaj problemu:

Problem: Obliczanie wartoś ci wielomianu
Da ne:

n – nieujemna liczba całkowita – s topień wielomianu;

a

0

, a

1

, ... a

n

– n+1 współczynników wielomianu;

z – wartoś ć argumentu.

Wynik: Wartoś ć wielomianu (4) s topnia n dla wartoś ci a rgumentu x = z.

Aby obliczyć ze wzoru (4) wartoś ć wielomia nu dla wartości argumentu z, należy pos tę pować nas tępująco
(y oznacza pomocniczą zmienną ):

y := a

0

y := yz + a

1

y:= yz + a

2

...

y:= yz + a

n–1

y:= yz + a

n

Ws zys tkie wiers ze, z wyjątkiem pierws ze go można zapis ać w je dnolity spos ób – otrzymujemy wtedy:

y := a

0

(5)

y: = yz + a

i

dla i = 1, 2, ..., n.

Ten sposób obliczania wartoś ci wielomianu na zywa s ię s che matem Hornera .

< 8 >

Informa tyka +

Uwaga. W opisie algorytmu pojawiło się polecenie (ins trukcja)
przypis ania

1

, np. y := a

0

, w której występuje s ymbol :=, złożony

z dwóch znaków: dwukropka i równości. Przypis anie oznacza
nadanie wielkoś ci (zmiennej) s tojącej po lewej strony tego s ym-
bolu wartości równej wartości wyrażenia (w szczególnym przy-
padku to wyra żenie może być zmienną ) znajdującego się po pra-
wej s tronie tego s ymbolu. Przypisanie jes t s tos owane na przy-
kład wtedy, gdy należy zmienić wartoś ć zmiennej, np. i := i + 1
– w tym przypadku ta s ama zmienna wys tępuje po lewej i po
prawej s tronie s ymbolu przypisania. Polecenie przypis ania wy-
s tępuje w większoś ci języków programowania , stosowane s ą
tylko różne s ymbole i ich uproszczenia dla jego oznaczenia.

Zas tosuj s chema t Hornera do obliczenia wartości wielomianów z ćwicz. 2 w punkcie z = 1.

Możemy wię c tera z zapis ać:

Algorytm: Schemat Hornera
Dane:

n – nieujemna liczba ca łkowita (s topień wielomia nu);

a

0

, a

1

, ... , a

n

– n+1 współczynników wielomianu;

z – wartość argumentu.

Wynik: y = w

n

(z) – wartość wielomianu (4) stopnia n dla wartości argumentu x = z.

Krok 1. y := a

0

– początkową wartością jes t współczynnik przy najwyżs zej p otę dze.

Krok 2. Dla i = 1, 2, …, n oblicz wartoś ć dwumianu y := yz + a

i

Wynika s tąd, że aby obliczyć wartoś ć wielomianu stopnia n wys tarczy wykonać n mnożeń i n dodawań. Udo-
wodniono, że je s t to najs zybs zy spos ób obliczania wartoś ci wielomianu.

Schemat blokowy algorytmu (zwany również siecią działań lub siecią obliczeń) jes t graficznym opisem: dzia -
łań składających się na algorytm, ich wzajemnych powią zań i kolejnoś ci ich wykonywania. W informa tyce
miejs ce schematów blokowych je st pomię dzy opisem algorytmu w pos taci lis ty kroków, a progra mem, napi-
s anym w wybranym ję zyku programowania . Należą one do kanonu wiedzy informatycznej, nie s ą jednak nie -
zbędnym jej elementem, chociaż mogą oka zać s ię ba rdzo przydatne na początkowym etapie projektowania
algorytmów i programów komputerowych. Z drugiej s trony, w wielu publikacjach algorytmy są przeds tawia-
ne w pos taci schematów blokowych, pożądana jes t wię c umiejętnoś ć ich odczytywania i rozumienia. Warto
nadmienić, że ten spos ób reprezentowania algorytmów pojawia się w zadaniach maturalnych z informatyki.

Na rys . 1 jes t prze ds tawiony s chemat blokowy algorytmu Sche mat Hornera . Jes t on zbudowany z bloków, któ-
rych ks ztałty zależą od rodzaju wykonywanych w nich polece ń. I tak mamy:

■

blok począ tku i blok końca algorytmu;

■

blok wprowadzania (wczytywania) da nych i wyprowadzania (drukowania) wyników – bloki te mają taki s am
ks ztałt;

■

blok operacyjny, w którym są wykonywane operacje przypisania;

■

blok warunkowy, w którym jes t formułowany warunek;

■

blok informacyjny, który może służyć do komentowa nia fragmentów s chematu lub łączenia ze s obą częś ci
więks zych s chematów blokowych.

Nie is tnieje pe łny układ za s ad poprawnego konstruowania schema tów blokowych. Można natomias t wymie -
nić dość naturalne za sady, wynikające z charakteru bloków:

1

Polecenie przypisa nia jes t czas em nazywane niepoprawnie pods ta wieniem

Schemat Hornera został podany przez
jego autora w 1819 roku, chociaż znacznie
wcześniej Isaac Newton stosował
podobną metodę obliczania wartości
wielomianów w s woich rachunkach
fizycznych. W 1971 roku, A. Borodin
udowodnił, że schemat Hornera jes t
optymalnym, pod względem liczby
wykonywanych działań, algorytmem
obliczania wartości wielomianu.

> Proste rachunki wykonywane za pomocą komputera

< 9 >

■

schemat zawiera dokładnie jeden blok począ tkowy, ale może zwierać wiele bloków końcowych – począ tek
algorytmu je st je dnoznacznie określony, ale algorytm może się kończyć na wiele różnych sposobów;

■

z bloków: początkowe go, wprowadzania danych, wyprowadzania wyników, operacyjnego wychodzi
dokładnie jedno połączenie , może jednak wchod zić do nich wiele połączeń;

■

z bloku warunkowe go wychodzą dwa połączenia, oznaczone wartoś cią warunku: TAK i NIE;

■

połączenia wychodzące mogą dochodzić do bloków lub do innych połączeń.

START

Blok początku a lgorytmu

Blok wprowadzania

danych

Blok wyprowadzenia

wyniku

Wprowadź liczbę n i n+1

danych: a

0

, a

1

, a

2

, ..., a

n

oraz z

Blok operacyjny

i := 0

y := a

0

i := i + 1

y := yz + a

i

;

Wyprowa dź:

wynik y

STOP

Blok zakończenia

algorytmu

Blok

warunkowy

Ta k

Nie

i = n

Rysunek 1.
Realizacja schema tu Hornera w pos taci schematu blokowego

Zakreś l na s chemacie blokowym na rys . 1 fragmenty odpowiadające pos zczególnym kro -

kom w opisie algorytmu Schemat Hornera . Zauwa ż, że ten s chemat blokowy za wiera również fragmen-
ty odpowiadające wczytywaniu danym i wypis ywaniu wyników.

Blok wprowadzania danych w s chemacie na rys . 1 polega na wczyta niu liczby n a później

na wczytaniu n + 1 liczb a

i

. Narysuj s zczegółowy s chemat blokowy te go bloku.

Schema ty blokowe mają wady, trudne do wyeliminowania . Ła two kons truuje się z ich pomocą algorytmy dla
obliczeń nie zawierających itera cji i warunków, którym w s chematach odpowiadają rozgałęzienia, nieco trud-
niej dla obliczeń z rozgałęzieniami, a trudniej dla obliczeń iteracyjnych. Za pomocą s chematów blokowych nie
można w naturalny s posób zapisa ć rekurencji ora z obja śnić znaczenia wielu poję ć zwią zanych z algorytmiką ,
takich np. jak programowanie z użyciem procedur, czyli podprogramów z parame trami. .

W dals zej czę ści zaję ć rzadko bę dziemy korzys tać ze s chematów blokowych, wystarczy nam bowiem

umiejętnoś ć programowania .

< 10 >

Informa tyka +

Schemat Hornera ma wiele za stosowań. Może być wykorzys tany m.in. do:

■

obliczania wartoś ci dziesiętnej liczb danych w innym s ys temie pozycyjnym (rozdz. 3);

■

s zybkiego obliczania wartości potęgi (rozdz. 5).

Zanim podamy komputerową realizację pierwszego algorytmu – schematu Hornera , musimy ustalić, w jaki
spos ób bę dą repre zentowane w algorytmie dane i jak bę dziemy je podawać do algorytmu.

Danymi dla schematu Hornera s ą s topień wielomianu n, zapis ane w pos taci ciągu n + 1 liczb współ-

czynniki wielomianu a

0

, a

1

, a

2

, ..., a

n

ora z liczba z, dla której chcemy obliczyć wartoś ć wielomianu. Stopień wie -

lomianu jes t liczbą naturalną (czyli dodatnią liczbą całkowitą ), a pozos tałe liczby mogą być ca łkowite lub rze -
czywis te, czyli np. dzie siętne (tj. z kropką ). Rodzaj danych liczb na zywa się typem danych. Przyjmujemy, że
poza s topniem wielomianu, pozos ta łe dane s ą rzeczywis te.

Dla wygody będziemy zakładać, że wiemy, ile będzie danych i ta liczba danych wys tępuje na początku

danych – jest nią liczba n, s topień wielomianu.

Zbiór danych, który jes t przetwarzany za pomocą algorytmu, może być podawany (czytany) z klawiatu-

ry, czytany z pliku lub może być zapis any w algorytmie w odpowiedniej strukturze danych.

Zapis zemy tera z s chemat Hornera posługując się polecenia mi języka Pa s cal (odpowiedni program w ję zyku
C++ zostanie podany na zaję ciach wars ztatowych). Przyjmujemy na początku, że dane s ą podawane z klawia -
tury – na początku nale ży wpisać liczbę ws zys tkich danych, a po niej kolejne elementy danych w podanej ilo-
ś ci. Po ka żdej danej liczbie naciskamy klawisz Enter.

Progra m, który jes t zapis em s chema tu Hornera w języku Pa s cal, je s t umies zczony w drugiej kolum-

nie w tab. 1. Język Pas cal je s t zrozumiały dla komputerów, które s ą wypos a żone w spe cjalne programy, tzw.
kompila tory, przekładają ce progra my użytkowników na ję zyk we wnętrzny komputerów. Progra m w tab. 1
be z więks zego trudu zrozumie ta kże człowiek dysponujący opis em s che matu Horne ra w pos ta ci lis ty kro-
ków. Kilka tylko s łów komenta rza. W wiers zach nr 2 i 3 znajdują s ię deklaracje zmiennych – kompute r mus i
wiedzie ć, jakimi wielkoś cia mi pos ługuje s ię a lgorytm i ja kie to s ą liczby, czyli jakiego s ą one t ypu – inte-

ger

oznacza liczby ca łkowite (np. s topień wielomia nu jes t liczbą ca łkowitą ), real oznacza liczby rze czywi-

s te , czyli np. liczby, które zawie rają kropkę dzies ie tną. Polecenia w ję zyka ch progra mowa nia na zywa ją się
ins trukcjami. Je śli chce my z kilku ins trukcji zrobić jedną , to tworzymy z nich blok, umies zcza jąc na je go po-
czą tku słowo begin, a na końcu – end. Pojedyncze ins trukcje kończymy średnikiem. Na końcu programu
s tawiamy kropkę . Pokrótce to ws zys tkie pods tawowe za s ady pis ania progra mów w języku Pas cal dla kom-
puterów.

Jedna ins trukcja wymaga wytłumaczenie, chocia ż równie ż jes t doś ć oczywis ta . W wiers zach 9 – 12

znajdują s ię ins trukcje, które realizują Krok 2 algorytmu polegający na wykonaniu je dnej iteracji s chematu
Hornera . Dodatkowo, wcześ niej jes t czytany kolejny współczynnik wielomianu. Ins trukcja , służąca do wie -
lokrotne go wykonania innych ins trukcji nazywa s ię ins trukcją iteracyjną lub ins trukcją pę tli. W programie
w tab. 1 ta instrukcja zaczyna się w wierszu nr 9 a kończy w wiers zu nr 12:

for i:=1 to n do begin

...

end

Ta ins trukcja iteracyjna , jak napisaliś my, służy do powtórzenia dwóch instrukcji:

read(a);

y:=y*z+a

Inne typy ins trukcji itera cyjnej bę dą wprowadzane sukces ywnie.

Uwaga. Poniewa ż założyliś my, że dane s ą podawane z klawiatury, zmieniliś my ich kolejnoś ć w s tosunku
do specyfikacji – liczba z, dla której jes t obliczana wartość wielomianu, jes t podawa na na począ tku, przed
współczynnikami wielomianu.

> Proste rachunki wykonywane za pomocą komputera

< 11 >

Tabela 1.
Program w ję zyku Pas cal (druga kolumna)

Lp

Program w ję zyku Pa s cal

Odpowiedniki ins trukcji po pols ki

1.

Program Horner;

nazwa programu;

2.

var i,n :integer;

zmienne i,n: naturalne;

3.

var a,y,z:real;

zmienne a,y,z: rzeczywiste;

4.

begin

pocz

ą tek

5.

read(n);

czytaj(n);

6.

read(z);

czytaj(z);

7.

read(a);

czytaj(a);

8.

y:=a;

pocz

ą tkowa wartoś ć wielomianu

9.

for i:=1 to n do begin

dla i:=1 do n wykonaj pocz

ą tek

10.

read(a);

czytaj(a);

11.

y:=y*z+a

modyfi kacja warto

ś ci wielomianu

12 .

end;

koniec iteracji;

13.

write(y)

drukuj(y) - warto

ś ć wielomianu

14.

end.

koniec. – na ko

ńcu stawiamy kropkę

W wyniku wykonania te go programu, wypis ywana jes t na ekranie wartoś ć wielomianu y w punkcie z. Ta war-
toś ć jes t wypis ywana w pos taci normalnej, np. liczba 30 jes t wypis ywana jako:

3.00000000000000E+001

czyli 3.00000000000000

•

10^ 1. Nie jes t to najwygodniejs za pos tać liczb, zwła s zcza liczb o nie wielkich war-

toś ciach. Aby wybrać inny format wyprowadzanych liczb, możemy napisać:

write(y:2:2)

co będzie oznaczać, że wartoś ć y zos tanie wyś wie tlona (wydrukowana , wyprowadzona) z dwoma cyframi
przed kropką i z dwoma cyframi po kropce.

Uruchom program Horner i wykona j obliczenia dla wybranego wielomianu i kilku je go

argumentów.

Zmodyfikujemy teraz nas z pierwszy program tak, aby:

■

stopień i współczynniki wielomianu były czytane na począ tku i przechowywane w programie
– do przechowania w programie współczynników użyjemy tablicy, która je st s ynonimem ciągu w ję zyku
programowania;

■

można było liczyć wartoś ć wielomianu o wczytanych współczynnikach dla wielu argumentów – zakładamy
w tym celu, że ciąg argumentów jes t zakończony liczbą 0 (jes t to tak zwany wartownik ciągu, gdyż jego rolą
jes t pilnowanie końca cią gu).

Za głębiające
się bloki
ins trukcji

< 12 >

Informa tyka +

Przy tych za łożeniach, program będący implementacją

2

s chema tu Hornera , może mie ć na s tępującą pos tać:

Program Horner_ tablica;

var i,n:integer;

y,z:real;

a :array[0..100] of real;

{Przyjmujemy, ze wielomian ma stopien co najwyzej 100}

begin

read(n);

for i:=0 to n do read(a[i]);

writeln(’z y‘);

read(z);

while z <> 0 do begin

y:=a[0];

for i:=1 to n do

y:=y*z+a[i];

write(’ ‘,y:2:5);

writeln;

read(z)

end

end.

Skomentowania wymaga użyta ins trukcja warunkowa:

while z <> 0 do begin

y:=a[0];

for i:=1 to n do

y:=y*z+a[i];

write(’ ‘,y:2:5);

writeln;

read(z)

end

W bloku tej instrukcji jes t wykonywany s chemat Hornera dla kolejnych wartości argumentu z tak długo, jak
długo czytana liczba z je st różna od 0 (z <> 0).

Dodatkowo, w programie wprowa dziliśmy drukowanie wyników w pos taci tabelki.

Uruchom program Horner _tablica i wykonaj obliczenia dla wybranego wielomianu

i kilku jego argumentów. Popraw wygląd wyników.

Binarne rozwinię cie dziesiętnej liczby naturalnej (prawa strona we wzorze (2)) przypomina s woją postacią wie -
lomian (patrz wzór (3)), gdzie a jes t wartością wielomianu stopnia n – 1 o współczynnikach b

n–1

, b

n–2

, ..., b

1

, b

0

należących do zbioru {0, 1}, dla wartoś ci argumentu x = 2. Z tej interpretacji rozwinięcia (2) wynika spos ób ob-
liczania dziesiętnej wartoś ci liczby naturalnej a, gdy jest dane jej binarne rozwinięcie (b

n–1

b

n–2

... b

1

b

0

)

2

. Wys tar-

czy zas tos ować schemat Hornera, który dla wielomianu, danego wzorem (2), przyjmuje nas tępującą pos tać:

a = b

n–1

2

n–1

+ b

n–2

2

n–2

+ ... + b

1

2

1

+ b

0

2

0

= (...(b

n–1

2 + b

n–2

)2 + ... + b

1

)2 + b

0

(6)

2

Terminem implementacja okreś la się w informat yce realizację algorytmu w pos taci programu komputerowego.

> Proste rachunki wykonywane za pomocą komputera

< 13 >

Napis z program służący do obliczania dziesię tnej wartoś ci liczby a danej w pos taci binar-

nego rozwinięcia (b

n–1

b

n–2

... b

1

b

0

)

2

.

Wska zówka . Zmodyfikuj odpowiednio program Hornera _tablica. Zwróć uwagę, że kolejne cyfry
rozwinięcia binarnego liczby w pos taci (2) s ą ponumerowane odwrotnie niż współczynniki wielomianu
we wzorze (3) i zauwa ż przy tym, że indeks współczynnika odpowiada potędze liczby 2, przed którą s toi
ten współczynnik. Nie powinno to je dnak utrudnić Ci wykonania tego ćwiczenia.

Pos tać rozwinięcia binarnego (6) sugeruje bardzo pros ty spos ób oblicza nia wartoś ci liczby a za pomocą kal-
kulatora .

Oblicz za pomocą kalkulatora dziesiętną wartoś ć liczby a, prze ds tawionej w pos taci roz-

winięcia binarnego. Wykorzys taj algorytm wynikający z pos taci (6). Zauwa ż, że nie musis z korzystać
z doda tkowej pamię ci kalkulatora.
Wska zówka . Możes z skorzys ta ć z kalkulatora dos tę pne go wś ród akces oriów środowiska Windows.

Ws zys tkie fakty podane powyżej przenos zą się na rozwinięcia liczby w s ys temie przy dowolnej pods ta wie p.

Zmodyfikuj program na pis any w ćwicz. 8 tak, aby mógł być s tos owa ny do obliczania

dziesiętnej wartoś ci liczby a danej w pos taci rozwinięcia przy pods tawie p.

Interes uje nas tera z czynnoś ć odwrotna – otrzymanie binarnego rozwinię cia dla danej dzie siętnej liczby na-
turalnej a.

Zauwa żmy, że we wzorze (2), czyli w binarnym przedstawieniu liczby a, wszys tkie składniki z wyją tkiem

os tatniego s ą podzielne prze z 2, a zatem ten os tatni składnik, czyli b

0

jes t res ztą z dzielenia liczby a przez 2.

Bity b

1

, b

2

,..., to res zty z dzielenia przez 2 kolejno otrzymywa nych ilora zów. Dzielenie kończymy, gdy ilora z

wynos i 0, gdyż wtedy kolejne re szty będą już cały cza s równe 0, a zera na początku rozwinięcia binarnego nie
mają żadne go znaczenia . Prześledź ten proces na przykładzie z rys . 2.

dzielenie

iloraz

res zta

749 | 2

374

1

374 | 2

187

0

187 | 2

93

1

93 | 2

46

1

46 | 2

23

0

23 | 2

11

1

11 | 2

5

1

5 | 2

2

1

2 | 2

1

0

1 | 2

0

1

Rysunek 2.
Przykład tworzenia binarnej reprezentacji liczby dziesię tnej 749. Otrzymaliś my 749 = (1011101101)

2

Zauwa żmy, że w powyżs zym algorytmie binarna repre zenta cja liczby je st tworzona od końca , czyli od naj-
mniej znaczące go bitu.

< 14 >

Informa tyka +

Wprowadzimy tera z dwie operacje, wykonywane na liczbach całkowitych, których wyniki s ą również liczbami
ca łkowitymi, a które s ą przydatne przy obliczaniu ilora zu i res zty z dzielenia liczb ca łkowitych przez siebie.

Dla dwóch liczb całkowitych k i l definiujemy:

r = k

mod l – r jes t res ztą z dzielenia k przez l, czyli r spełnia nierównoś ci 0 ≤ r < l, gdyż res zta jes t nie-

ujemną liczbą mniejs zą od dzielnika;

q = k

div l – q jes t ilorazem całkowitym z dzielenia k przez l, czyli q jes t wynikiem dzielenia k przez l

z pominięciem części ułamkowej.

Z definicji tych dwóch operacji wynika nas tępująca równoś ć:

k = l

•

q + r = l

•

(k div l) + (k mod l).

(7)

Upe wnij się, że dobrze rozumiesz te dwie operacje, które czę s to wys tępują w obliczeniach komputerowych
na liczbach całkowitych.

Dla liczby naturalnej l = 6 i dla liczby naturalnej k, zmieniającej się od 0 co 1 do 20 oblicz

wartości k div l ora z k mod l i sprawdź prawdziwość równości (7).

Przyjmij, że l = 2, a więc intere suje nas ilora z i res zta z dzielenia liczby na turalnej k prze z

2. Podaj, w zależnoś ci od parzys toś ci liczby k, ile wynosi k mod 2 ora z k div 2.

Dotychcza s owa dyskusja prowadzi nas do na s tę pującego algorytmu:

Algorytm: Zamiana dzies ię tnej liczby naturalnej na pos tać binarną
Dane:

Dziesiętna liczba naturalna a.

Wynik: Cią g bitów, tworzących binarne rozwinięcie liczby a , w kolejności od najmniej znaczącego bitu.
Krok 1. Powta rzaj krok 2 dopóki a jes t liczbą więks zą od zera , w prze ciwnym ra zie zakończ algorytm.
Krok 2. Za kolejny bit (od końca) rozwinię cia przyjmij: a mod 2 i przypisz: a := a div 2.

Poniżej prze ds tawiamy implementację te go algorytmu w języku Pa scal.

Program Rozwiniecie_ binarne;

var a:integer;

begin

read(a);

while a <> 0 do begin

write(a mod 2,’ ‘);

a:=a div 2

end

end.

W powyżs zym programie , kolejne bity rozwinięcia binarnego liczby a s ą wypis ywane

w kolejnoś ci od najmniej znaczą cego, a więc odwrotnie, niż to się przyjmuje. Zmodyfikuj ten program
tak, aby binarne rozwinię cie danej liczby było wyprowadzane od najbardziej znaczące go bitu.
Wska zówka . Pos łuż się tablicą , w której będą przechowywane kolejno generowane bity.

Os oby, które nie znają logarytmu, mogą opuścić ten podpunkt.

Liczby w komputerze są zapis ywane w pos taci binarnej. Intere sujące je st więc pytanie, ile miejs ca w kompu-
terze, czyli ile bitów, zajmuje liczba naturalna a w pos taci binarnej. Odpowiedź na to pytanie jes t bardzo wa ż-
na w informa tyce , nawet dzisiaj, kiedy można korzystać z niemal nieograniczonej pamięci komputerów i nie
trzeba się obawiać, że jej za braknie.

> Proste rachunki wykonywane za pomocą komputera

< 15 >

Najpierw rozwa żymy odwrotne pytanie: Jaką najwięks zą liczbę naturalną można zapis ać na n bitach? Liczba
taka ma ws zys tkie bity równe 1 w s woim rozwinięciu binarnym (11...11)

2

, a więc jej wartoś ć, jako suma n po-

czą tkowych wyra zów ciągu geometrycznego z ilora zem równym 2, wynosi:

2

n–1

+ 2

n–2

+ ... + 2

1

+ 2

0

= (1 – 2

n

)/ (1 – 2) = 2

n

– 1

Ta równoś ć ma ciekawą interpreta cję. Wa rtoś ć s umy po lewej s tronie jes t liczbą o jeden mniejs zą od liczby
(100...00)

2

, która w rozwinięciu binarnym s kłada s ię z n+1 bitów i ma tylko jeden bit równy 1 – najbardziej

znaczący. Tą liczbą je st 2

n

. Na rys. 3 poka za no, ile bitów potrzeba do przedstawienia w pos taci binarnej liczb

z pos zczególnych przedzia łów. Z os tatniej równoś ci wynika, że liczba a może być zapis ana na n bitach, jeśli
spełnia nierównoś ć:

2

n

– 1 ≥ a , czyli 2

n

≥ a + 1.

Dla danej liczby a wybieramy najmniejsze n s pełniające tę nierównoś ć, gdyż początkowe zera w rozwinię ciu
liczby nie mają znaczenia . Logarytmują c obie s trony nierówności można dokładnie okreś lić wartoś ć n:

n =

log

2

(a + 1)

Użyliśmy funkcji powała, której wartością jes t najmniejs za liczba całkowita więks za od liczby s tojącej pod
powałą, gdyż liczba bitów w rozwinięciu liczby a jes t zaws ze liczbą naturalną , a wartoś ć logarytmu może nie
być liczbą ca łkowitą,

końce podzia łów

1

3

7

15

31

63

= 2

n

– 1

liczba bitów n

2

3

4

5

6

Rysunek 3.
Liczba bitów potrzebnych do zapamię tania liczb a z pos zczególnych przedzia łów

Z powyżs zych rozwa żań należy zapamiętać, że liczba bitów potrzebnych do zapamię tania w komputerze licz-
by na turalnej jes t w przybliżeniu równa logarytmowi przy podstawie 2 z wartoś ci tej liczby. na przykład, licz-
ba 1000 jes t pamię tana na log

2

(1000 + 1) = 10 bitach.

Przy tej oka zji porównaj s zybkoś ć wzra s tania funkcji liniowej i funkcji logarytmicznej.

Narysuj w jednym układzie ws półrzędnych wykres y dwóch funkcji, logarytmicznej i li-

niowej. Utwórz także tabelę wartoś ci obu funkcji dla liczb wybra nych z prze działu [1, 10

9

]. Zauwa ż, jak

wolno rośnie funkcja logarytmiczna w porównaniu z funkcją liniową .

Funkcja logarytmiczna odgrywa bardzo wa żną rolę w informatyce.

Binarna reprezentacja liczb naturalnych je st źródłem s zybkich metod obliczania wartości potę gi x

m

, gdzie m

jes t liczbą naturalną , a x może być dowolną liczbą rzeczywis tą (wartoś ć pods ta wy x nie ma znaczenia dla na-
szych rozwa żań). Metody te znajdują zas tos owanie w algorytmach kryptogra ficznych, w których s ą obliczane
wartoś ci potęg o bardzo dużych wykładnika ch.

Posłużmy się najpierw przykładem. Przypuś ćmy, że chcemy obliczyć wartoś ć potęgi. x

22

. Pros te wy-

mnożenie pods tawy prze z siebie x

22

= x

•

x

•

...

•

x to 21 mnożeń. A skorzys tajmy z binarnej reprezentacji wykład-

nika potęgi. Można go przeds tawić jako sumę potęg liczby 2:

22 = 2 + 4 + 16 = 2

1

+ 2

2

+ 2

4

< 16 >

Informa tyka +

wtedy na s za potę ga przyjmuje pos ta ć x

22

= x

2+4+16

= x

2

•

x

4

•

x

16

i można ją obliczyć wielokrotnie podnos ząc do

kwadra tu pods ta wę x i mnożąc prze z siebie odpowie dnie czynniki. Dla potę gi 22 obliczanie potęgi przebie -
ga na s tępująco: x

2

, x

4

= (x

2

)

2

, x

8

= (x

4

)

2

, x

16

= (x

8

)

2

i mnożymy prze z siebie x

2

•

x

4

•

x

16

. W sumie wykonuje my 6

mnożeń (podniesienie do kwadra tu wymaga wykona nia jedne go mnożenia).

Korzys tają z przeds tawienia wykładnika w repre zentacji bina rnej 22 = (10110)

2

w postaci s chematu

Hornera , wykładnik można zapis ać 22 = 1

•

2

4

+ 0

•

2

3

+ 1

•

2

2

+ 1

•

2

1

+ 0

•

2

0

= (((2 + 0)2 +1)2 + 1)2 + 0, a s tąd otrzy-

mujemy:

x

(((2 + 0)2 +1)2 + 1)2 + 0

= (x

((2 + 0)2 +1)2 + 1

)

2

= (x

((2 + 0)2 +1)2

x)

2

= (x

(2 + 0)2 +1

)

2

x)

2

= (x

(2 + 0)2

x)

2

x)

2

= (x

(2 + 0)

)

2

x)

2

x)

2

= (((x

2

)

2

x)

2

x)

2

.

Korzys tając z tego zapisu, potęgę x

22

obliczamy wykonując kolejno na s tępujące mnożenia: x

2

, x

4

= (x

2

)

2

, x

5

=

x

4

•

x, x

10

= (x

5

)

2

, x

11

= x

10

•

x, x

22

= (x

11

)

2

. W s umie wykonujemy równie ż 6 mnożeń.

W oparciu o jedną i drugą metodę nas zkicowaną powyżej, podaj kolejnoś ć wykonywania

mnożeń podcza s obliczania wartości potę gi x

313

. Ile mnożeń jes t wykonywanych w obu przypadkach?

Obie metody potęgowania korzys tają z binarnego rozwinię cia wykła dnika , ale różnią się tym, że w pierws zym
przypadku to rozwinięcie jes t przeglądane od najmniej znaczące go bitu (mówimy o metodzie od prawej do le -
wej), a w drugim – od najbardziej znaczącego (czyli metodą od lewej do prawej). Poniewa ż reprezentacja bi-
narna liczby naturalnej jes t tworzona od najmniej znaczącego bitu (zob. rozdz. 4), podamy tera z algorytm ob-
liczania wartoś ci potęgi, który wykonuje potęgowanie rozkładając wykładnik na pos ta ć binarną (pos tać ta
jednak nie je st zachowywana w algorytmie). Szybkie potę gowanie, wykorzystujące s chemat Hornera pozo-
s tawiamy do s amodzielne go wykona nia.

Binarny algorytm potę gowania „od prawej do lewej”
Dane:

Liczba na turalna m i dowolna liczba x.

Wynik: Wartość potę gi y = x

m

.

Krok 0. {Us talenie początkowych wartości potę gi y i zmiennych pomocniczych z i l.}

y := 1:

l := m; z := x;

Krok 1. Jeśli l mod 2 = 1 (czyli l jes t liczbą nieparzystą ), to y := y

•

z;

Krok 2. l := l div 2; je śli l = 0, to zakończ algorytm – wynikiem jes t bie żąca wartość y.
Krok 3. z := z

•

z; wróć do kroku 1.

Wykonaj powyższy algorytm dla m = 22 i m = 313. Wypis z kolejne wartoś ci zmiennych

y, l, z i porównaj kolejne wartości zmiennej y z wcześniej otrzymanymi wartoś cia mi potę gi dla tych war-
toś ci wykładnika .

Napis z program w języku Pas cal, bę dący realizacją algorytmu podnos zenia do potęgi

„od prawej do lewej”. Jako wynik, dla danego wykładnika m, wyprowadzaj liczbę mnożeń wykonywa -
nych w tym algorytmie dla obliczenia wartoś ci x

m

.

Szybkie algorytmy potę gowania s ą s tos owane w algorytmach s zyfrujących, w których wykła dniki potęg s ą
bardzo dużymi liczbami.

Przeds ta wiamy w tym punkcie algorytm, który wś ród przepis ów opa trywanych tych mianem, zos tał odkryty
jako jeden z na jwcześniejs zych, bo jes zcze w s tarożytności, prze z Euklides a .

> Proste rachunki wykonywane za pomocą komputera

< 17 >

Danymi s ą dwie nieujemne liczby cał-
kowite m i n. Liczba k jes t

najwięk-

szym wspólnym dzielnikiem m i n, je-
śli dzieli m oraz n i je st najwięks zą licz-
bą o tej wła sności — oznaczamy ją przez
NWD(m,n).

Algorytm Euklides a jest

najs tars zą me todą znajdowania naj-
więks ze go wspólnego dzielnika dwóch
liczb (patrz ramka obok).

Pierws zą metodą , jaka może przyjś ć na myśl, gdy chcemy znale źć najwięks zy wspólny

dzielnik dwóch danych liczb m i n, je st sprawdzanie podzielnoś ci tych liczb przez kolejne liczby natu-
ralne, począws zy od 2, a s kończyws zy na mniejs zej z m i n. Ile dzieleń na leży wykonać, aby obliczyć tą
metodą NWD(24,48) ora z NWD(46,48)? A dla dowolnych m i n? Opis z tę metodę w pos taci algorytmu
w wybranej przez s iebie reprezentacji. Możes z opis ać tę metodę w pos ta ci programu komputerowego.

Nie możes z być chyba zadowolony z efektywnoś ci tego algorytmu, zwła s zcza dla przykładowych danych licz-
bowych — w pierws zym przypadku, gdy jedna z liczb dzieli drugą, od ra zu widać, że ta mniejs za jes t pos zu-
kiwanym największym wspólnym dzielnikiem obu liczb. A je śli żadna z liczb nie dzieli drugiej, tak jak w dru-
gim przypadku?

Załóżmy, że n ≥ m . Wtedy dzielą c n przez m otrzymujemy nas tępującą równoś ć:

n = qm + r, gdzie 0 ≤ r < m

(8)

Wielkoś ci q i r s ą odpowiednio ilorazem i res ztą z dzielenia n prze z m. Dla danych z ćwicz. 17, równoś ć (8)
przyjmuje pos tać: 48 = 2

•

24 i 48 = 1

•

46 + 2. Wynikają s tąd na s tępujące wnioski:

■

jeśli r = 0, to NWD(m,n) = m, czyli jeśli jedna z liczb dzieli drugą bez res zty, to mniejsza z tych liczb jes t ich
najwięks zym wspólnym dzielnikiem;

■

jeśli r ≠ 0, to równoś ć (8) można zapisać w pos taci r = n – qm; a s tąd wynika, że ka żda liczba dzieląca
n i m dzieli ca łe wyra żenie po pra wej s tronie tej równoś ci, a więc dzieli również r; zatem, najwięks zy
wspólny dzielnik m i n dzieli również res ztę r.

Te dwa wnioski można zapisa ć w postaci na s tępującej równoś ci:

NWD(m,n) = NWD(r,m),

w której przyjęliś my, że NWD(0,m) = m, gdyż 0 jes t podzielne prze z ka żdą liczbę różną od zera.
Za stosujmy tera z tę obserwację do obliczenia NWD(25,70). Otrzymamy:

NWD(25,70) = NWD(20,25) = NWD(5,20) = NWD(0,5) = 5,

gdyż stos ując równoś ć (8) otrzymujemy kolejno:

70 = 2

•

25 + 20

25 = 1

•

20 + 5

20 = 4

•

5

Euklides stosował swój algorytm do znajdowania najdłuższego
odcinka mieszczącego się całkowitą liczbę razy w dwóch danych
odcinkach. Było to około 300 roku p.n.e., na długo
przed pojawieniem się określenia algorytm.
Algorytm Euklidesa jest jednym z najczęściej przytaczanych
algorytmów w książkach informatycznych i matematycznych.
Powodem jest nie tylko szacunek dla jego „wieku”, ale to, że ma
wiele zastosowań w rozwiązywaniu problemów rachunkowych
i posługując się nim, można ilustrować wiele podstawowych pojęć
i własności informatycznych.

< 18 >

Informa tyka +

Powyżs ze pos tępowanie zaws ze się kończy, bo pierwszy element w parze argumentów funkcji NWD maleje,
gdyż jes t to reszta .

Możemy tera z przedstawić opis algorytmu Euklide sa . Zauwa żmy jes zcze, że ilora z q z równoś ci (8) nie wys tę -
puje w na s tępnych iteracjach tej równoś ci, zatem nie trzeba go wyznaczać.

Algorytm Euklide sa (z dzieleniem) wyznaczania NWD
Dane:

Dwie liczby naturalne m i n, .

Wynik: NWD(m,n) — najwięks zy wspólny dzielnik m i n.
Krok 1. Jeś li m = 0, to n jes t szukanym dzielnikiem. Zakończ algorytm.
Krok 2. r := n mod m, n := m, m := r. Wróć do kroku 1.

Nas tępne ćwiczenie zwraca uwagę, że dla pe wnych liczb algorytm Euklidesa wykonuje dużo iteracji.

Za s tos uj algorytm Euklides a do liczb 34 i 55. Co ciekawego możes z powiedzie ć o dzia -

łaniu algorytmu w tym przypadku – ile wynos zą kolejne ilorazy? Wypis z od końca ciąg res zt tworzo-
nych w tym przypadku. Jak inaczej można zdefiniować ten cią g? Podaj inną parę liczb, dla której algo-
rytm Euklides a dzia ła podobnie.

Zapis zemy tera z algorytm Euklides a w pos taci programu:

program Euklides;

var m,n,r:integer;

begin

read(m,n);

while m>0 do begin

r:=n mod m;

n:=m;

m:=r

end;

write(n)

end.

Zapis zemy tera z algorytm Euklides a w pos taci wydzielonej funkcji NWD, której wartoś cią jes t wła śnie najwięk-
s zy wspólny dzielnik dwóch liczb, będących a rgumentami tej funkcji.

program Euklides_funkcja;

var m,n:integer;

function NWD(m,n:integer):integer;

var r:integer;

begin

while m>0 do begin

r:=n mod m; n:=m; m:=r

end;

NWD:=n

end; {NWD}

begin

read(m,n);

writeln(NWD(m,n))

end.{Euklides_funkcja}

W nagłówku funkcji, po jej nazwie
i parametrach, podaje się typ wyniku
funkcji i średnik.

W tres ci funkcji wys tępuje ins trukcja
przypis ania na zwie funkcji jej wartoś ci.

> Proste rachunki wykonywane za pomocą komputera

< 19 >

Is tnieje jes zcze wiele innych implementacji a lgorytmu Euklides a, np. wykonujących odejmowanie zamia s t
dzielenia. Je dna z najciekaws zych implementacji wykorzys tuje tzw. rekurencję, czyli funkcję, która odwołu-
je się do siebie.

program Euklides_ rekurencja;

var m,n:integer;

function NWD_rek(m,n:integer):integer;

begin

if m>n then NWD_ rek:=NWD_rek(n,m)

else if m = 0 then NWD _rek:=n

else NWD _rek:=NWD_ rek(n mod m,m)

end;

begin

read(m,n);

writeln(NWD _rek(m,n))

end.

Zapoznaj się z przeds tawionymi implementacjami algorytmu Euklides a, uruchom te pro-

gramy i przetes tuj je na wybranych parach liczb naturalnych, w tym m.in. na parze liczb 34 i 55.

Ten rozdział jes t krótkim wprowadzeniem do zajęć w module „Algorytmika i programowanie”. Krótko wyja-
śniamy w nim pods tawowe pojęcia ora z s tos owane na zajęciach podejś cie do rozwią zywania problemów
z pomocą komputera .

Pows zechnie przyjmuje się , że algorytm jes t opis em krok po kroku rozwią zania pos tawionego problemu lub
sposobu os iągnięcia jakiegoś celu. To poję cie wywodzi się z matematyki i informatyki – za pierws zy algorytm
uznaje się bowiem a lgorytm Euklidesa (patrz rozdz. 6), podany ponad 2300 lat temu. W os ta tnich latach algo-
rytm s tał się bardzo popularnym s ynonimem przepisu lub ins trukcji postępowania .

W s zkole, algorytm pojawia się po ra z pierws zy na lekcjach matematyki już w s zkole pods tawowej, na

przykład jako algorytm pisemnego dodawania dwóch liczb, wiele klas wcześniej, zanim s taje s ię przedmio-
tem zajęć informatycznych.

O znaczeniu algorytmów w informatyce może ś wiadczyć nas tępujące określenie, przyjmowane za de -

finicję informatyki:

informatyka jes t dziedziną wiedzy i działa lności zajmują cą się algorytmami

W tej definicji informa tyki nie ma dużej przes ady, gdyż zawarte s ą w niej pośrednio inne pojęcia s tosowane
do definiowania informatyki: komputery – jako urządzenia wykonujące odpowie dnio dla nich zapis ane algo-
rytmy (czyli niejako wprawiane w ruch algorytmami); informacja – jako materiał przetwa rzany i produkowa-
ny prze z komputery; programowanie – jako zes pół metod i środków (np. języków i s ys temów użytkowych) do
zapis ywania algorytmów w pos taci programów.

Położenie nacisku w poznawaniu informatyki na algorytmy je st jes zcze uza s adnione tym, że zarówno

kons trukcje komputerów, jak i ich oprogramowanie bardzo szybko s ię s tarzeją , natomia s t pods tawy s toso-
wania komputerów, które s ą przedmiotem zainteresowań algorytmiki, zmieniają się bardzo powoli, a niektó-
re z nich w ogóle nie ule gają zmianie.

Algorytmy, zwła s zcza w s woim popularnym znaczeniu, wys tępują ws zę dzie wokół nas – niemal każdy

ruch człowieka , zarówno anga żujący jego mięśnie , jak i bę dący je dynie działaniem umysłu, jes t wykonywany
we dług jakiegoś przepisu pos tępowania, które go nie zaws ze jes te śmy nawet ś wiadomi. Wiele nas zych czyn-

< 20 >

Informa tyka +

noś ci potrafimy wyabs trahować i poda ć w pos taci precyzyjne go opisu, a le w bardzo wielu przypadkach nie
potrafimy nawet powtórzyć, jak to się dzieje lub jak to się stało

3

.

Nie ws zys tkie pos tę powania z na s zego otoczenia, na zywane algorytmami, s ą ś ciśle zwią zane z kom-

puterami i nie ws zys tkie przepis y działań można uznać za algorytmy w znaczeniu informatycznym. Na przy-
kład nie są nimi na ogół przepis y kulinarne, chocia ż odwołuje się do nich David Harel w s woim fundamental-
nym dziele o algorytmach i algorytmice [3]. Otóż przepis np. na s porządzenie „ciągutki z wiśniami”, którą za -
chwycała się Alicja w Krainie Czarów, nie jes t algorytmem, gdyż nie ma dwóch osób, które na je go podstawie ,
dys ponując tymi s amymi produktami, zrobiłyby taką s amą, czyli jednakowo smakującą ciągutkę. Nie może
być bowiem algorytmem przepis , który dla identycznych danych daje różne wyniki w dwóch różnych wykona -
niach, jak to najczęś ciej bywa w przypadku robienia potraw według „algorytmów kulinarnych”.

Algorytmika to dział informa tyki, zajmujący się różnymi aspektami tworzenia i analizowania algorytmów,
przede ws zys tkim w odnie sieniu do ich roli jako precyzyjnego opisu postę powania , mającego na celu znale -
zienie rozwią zania pos ta wionego problemu. Algorytm może być wykonywany przez człowieka , przez kompu-
ter lub w inny sposób, np. przez specjalnie dla niego zbudowane urządzenie. W os tatnich la tach pos tęp w roz-
woju komputerów i informatyki był nierozerwalnie zwią zany z rozwojem cora z doskonals zych algorytmów.

Informatyka jes t dziedziną zajmującą się rozwią zywaniem problemów z wykorzys taniem komputerów.

O znaczeniu algorytmu w informatyce może ś wiadczyć fakt, że każdy program komputerowy działa zgodnie
z jakimś algorytmem, a więc zanim zadamy komputerowi nowe zadanie do wykonania powinniśmy umie ć
„wytłumaczyć” mu dokładnie, co ma robić. Bardzo trafnie to sformułowa ł Donald E. Knuth, je den z najznako-
mits zych, żyją cych informatyków:

Mówi się często, że człowiek dotąd nie zrozumie czegoś ,

za nim nie nauczy tego – kogoś innego.

W rzeczywistości,

człowiek nie zrozumie czegoś naprawdę,

za nim nie zdoła nauczyć tego – komputera .

Staramy s ię, by pre zentowane algorytmy były jak najpros ts ze i by dzia łały jak najs zybciej. To os tatnie żądanie
może wydawa ć się dziwne , przecie ż dys ponujemy już teraz bardzo s zybkimi komputerami i s zybkoś ć działa -
nia proces orów s tale rośnie (według prawa Moore’a podwaja się co 18 mie sięcy). Mimo to is tnieją problemy,
których obe cnie nie jes t w s tanie rozwią zać żaden komputer i zwięks zenie szybkoś ci komputerów nie wiele
pomoże , kluczowe wię c s taje się opracowywanie cora z s zybs zych algorytmów. Jak to ujął Ralf Gomory, s zef
oś rodka badawczego IBM:

Najleps zym sposobem przyspieszania komputerów

jest obarczanie ich mniejs zą liczbą dzia łań.

Komputer jest s tosowany do rozwią zywania problemów zarówno przez profesjonalnych informatyków, którzy
projektują i tworzą oprogramowanie, jak i przez tych, którzy stosują tylko technologię informacyjno-komuni-
kacyjną , czyli nie wykraczają poza posługiwanie się gotowymi narzędziami informatycznymi. W obu przypad-
kach ma zas tos owanie podejście do rozwiązywania problemów algorytmicznych, która polega na s ystema -
tycznej pracy nad komputerowym rozwią zaniem problemu i obejmuje cały proces projektowania i otrzymania
rozwiązania. Celem nadrzędnym tej metodologii jes t otrzymanie dobrego rozwią zania, czyli takiego, które jes t:

■

zrozumiałe dla każdego, kto zna dziedzinę rozwiązywanego problemu i użyte narzę dzia komputerowe,

■

poprawne , czyli spe łnia specyfikację problemu, a więc dokładny opis problemu,

■

efekt ywne , czyli niepotrzebnie nie marnuje za s obów komputerowych, cza su i pamięci.

3

Interes ująco ujął to J. Nievergelt – Jest tak, jakby na przykład stonoga chciała wyjaśnić, w jakiej kolejności wpra wia w ruch

swoje nogi, ale z przera żeniem stwierd za, że nie może iść dalej.

> Proste rachunki wykonywane za pomocą komputera

< 21 >

Ta metoda składa się z na s tępujących s ze ściu etapów:

1. Opis i analiza s ytuacji problemowej. Na pods ta wie opisu i analizy s ytuacji problemowej należy w pe łni zro-

zumieć, na czym polega problem, jakie s ą dane dla problemu i jakich oczekujemy wyników, ora z jakie s ą
możliwe ograniczenia.

2. Sporządzenie specyfikacji problemu, czyli dokładnego opis u problemu na pods ta wie rezultatów etapu 1.

Specyfikacja problemu zawiera:

■

opis danych,

■

opis wyników,

■

opis relacji (powią za ń, zale żności) między danymi i wynikami.

Specyfikacja jes t wykorzystana w następnym etapie jako specyfikacja tworzonego rozwią zania (np. programu).

3. Zaprojektowanie rozwią zania . Dla sporządzonej na poprze dnim e tapie specyfikacji problemu, je st projek-

towane rozwią zanie komputerowe (np. program), czyli wybierany odpowiedni algorytm i dobierane do nie go
struktury danych. Wybierane jes t także środowisko komputerowe (np. język programowania), w którym bę -
dzie realizowane rozwią zanie na komputerze.

4. Komputerowa realizacja rozwią zania. Dla projektu rozwią zania , opracowanego na poprzednim eta pie, jes t

budowa ne kompletne rozwią zanie komputerowe, np. w pos taci programu w wybranym ję zyku programowa -
nia. Na s tępnie, te stowana jes t poprawnoś ć rozwiązania komputerowe go i badana jego efektywnoś ć działa-
nia na różnych danych.

5. Te s towanie rozwiązania. Ten etap jest poś więcony na s ys tematyczną weryfikację poprawnoś ci rozwią zania

i tes towanie jego włas ności, w tym zgodności ze specyfikacją .

6. Prezentacja rozwią zania . Dla otrzymanego rozwią zania nale ży jeszcze opracować dokumentację i pomoc

dla (innego) użytkownika. Cały proces rozwią zywania problemu kończy pre zentacja innym zainteres owanym
os obom (uczniom, nauczycielowi) spos obu otrzymania rozwią zania ora z s amego rozwiązania wra z z doku-
mentacją .

Chocia ż powyżs za metodologia jes t s tos owana głównie do otrzymywania komputerowych rozwią za ń, które
mają pos tać programów napis anych w wybranym ję zyku programowania , może być zas tos owana również do
otrzymywania rozwiązań komputerowych wię ks zoś ci problemów z obszaru za s tos owań informa tyki i posłu-
giwania się technologią informacyjno-komunikacyjną

4

, czyli gotowym oprogramowaniem.

Dwie uwagi do powyżs zych rozwa żań.

Uwaga 1. Ws zys cy, w mniejszym lub więks zym s topniu, zmagamy się z problemami, pochodzącymi z róż-
nych dziedzin (przedmiotów). W na s zych rozwa żaniach, problem nie jes t je dnak wyzwaniem nie do pokona -
nia, przyjmujemy bowiem, że problem jes t s ytua cją , w której uczeń ma przeds tawić jej rozwią zanie ba zując na
tym, co wie , ale nie ma powiedziane, jak to ma zrobić. Problem na ogół zawiera pewną trudnoś ć, nie je st ru-
tynowym zadaniem. Na takie s ytuacje problemowe rozs zerzamy pojęcie problemu, wymagającego przedsta -
wienia rozwiązania komputerowe go.

Uwaga 2. W tych rozwa żaniach rozs zerzamy także pojęcie programowania . Jak pows zechnie wiadomo, kom-
putery wykonują tylko programy. Użytkownik komputera może korzys tać z is tniejących programów (np. za
pakietu Office), a może także posługiwać się własnymi programami, napis anymi w języku programowania ,
który „rozumieją” komputery. W s zkole nie ma zbyt wiele cza su, by uczyć programowania , uczniowie te ż nie
są odpowie dnio przygotowani do programowania komputerów. Is tnieje jednak wiele sposobności, by ks ztał-
cić zdolność komunikowania się z komputerem za pomocą programów, które pows tają w inny spos ób niż za
pomocą programowania w wybranym języku programowania. Szczególnym przypadkiem takich programów
jes t oprogramowanie edukacyjne, które służy do wykonywania i śledzenia działania algorytmów. „Programo-
wanie” w przypadku takiego oprogramowania pole ga na dobieraniu odpowiednich parametrów, które ma ją
wpływ na działanie algorytmów i tym s amym umożliwiają leps ze zapoznanie s ię z nimi.

4

W najnows zej pods tawie programowej dla przedmiotu informat yka , przyję tej do realizacji pod koniec 20 08 roku, to po-

dejś cie jes t zalecane jako pods tawowa metodologia rozwią zywania problemów z pomocą komputera .

< 22 >

Informa tyka +

1. Cormen T.H., Leis erson C.E., Rives t R.L., Wprowadzenie do algorytmów, WNT, Warsza wa 1997
2. Gurbiel E., Hard-Olejniczak G., Kołczyk E., Krupicka H., Sysło M.M., Informatyka , Część 1 i 2, Podręcznik

dla LO, WSiP, Wars zawa 2002-2003

3. Harel D., Algorytmika . Rzecz o istocie informa tyki, WNT, Wars zawa 1992
4. Knuth D.E., Sztuka progra mowania , Tomy 1 – 3, WNT, Wars za wa 2003
5. Sysło M.M., Algorytmy, WSiP, Wars zawa 1997
6. Sysło M.M., Piramidy, s zyszki i inne konstrukcje algorytmiczne, WSiP, Warsza wa 1998. Kolejne rozdzia ły tej

ksią żki są zamie szczone na s tronie: http:// www.ws ipne t.pl/ kluby/ informa tyka _eks tra.php?k=69

7. Wirth N., Algorytmy + struktury danych = programy, WNT, Wars zawa 1980

Nota tki

< 23 >

W projekcie

, poza wykładami i warsztatami,

przewidziano następujące działania:

■

24-godzinne kursy dla uczniów w ramach modułów tematycznych

■

24-godzinne kurs y metodyczne dla nauczycieli, przygotowujące

do pracy z uczniem zdolnym

■

nagrania 60 wykładów informatycznych, prowadzonych

przez wybitnych specjalistów i nauczycieli akademickich

■

konkursy dla uczniów, trzy w ciągu roku

■

udział uczniów w pracach kół naukowych

■

udział uczniów w konferencjach naukowych

■

obozy wypoczynkowo-naukowe.

Szczegółowe informacje znajdują się na stronie projektu