ALGORYTMY1.PDF

Metodynauczaniaj¦zykówprogramowania

wykładdlaIIrokuZLMzima2003/2004

OpracowałaZoﬁaWalczak

1.Troch¦wiadomo±cioalgorytmachisposobachich

przedstawiania

Algorytm jestprzepisemopisuj¡cymkrokpokrokurozwi¡zaniejakiego±

problemulubdoj±ciedojakiego±celu.

Najcz¦±ciejjestwielemo»liwo±ci(algorytmów)rozwi¡zaniadanegozagad-

nienia.Nale»ywtedywybra¢taki,którynajbardziejnadajesi¦donaszych

celówtzn.najszybciejotrzymamypoprawnywynik.

Słowo algorytm pochodziodbrzmieniafragmentunazwiska:Muhammad

ibnMusaal-Chorezmi,arabskiegomatematykaiastronoma»yj¡cegonaprze-

łomieVIIIiIXwieku.Jestonuznawanyzaprekursorametodobliczeniowych

wmatematyce.

Naukazajmuj¡casi¦algorytmamiiichwłasno±ciaminazywasi¦ algoryt-

mik¡ .Porazpierwszytejnazwyu»yłDawidHarelwtytuleswojejksi¡»ki

Algorytmika.Rzeczoistocieinformatyki [WNT,W-wa1992].

Budowaniealgorytmówjestrówniestarejakd¡»eniedozdobywaniawy-

znaczonychcelów.Człowiekzawszestarałsi¦ułatwi¢sobie»yciepocz¡wszy

odwzniecaniaogniapoprzezbudowaniepiramidczyszeregowaniewielko±ci

isterowaniemaszynami.Jednymznajstarszych,najcz¦±ciejprzytaczanych

wksi¡»kachinformatycznychimatematycznychalgorytmówjest Algorytm

Euklidesa, któryznajdujenajwi¦kszywspólnydzielnikdwóchliczb.Maon

ponad2000latizostałporazpierwszyzamieszczonywwiekopomnymdziale

Euklidesa Elementy ,wktórymsformułowałrównie»aksjomatyk¦geometrii

napłaszczy¹nie,zwan¡te»jegoimieniem.WprawdziewBabilonie,ok.1800

latprzednasz¡er¡znanoistosowanowieleprzepisówrachunkowych,alenie

nadajesi¦imtakiegoznaczenia,gdy»wieleznichzostałowypartychprzez

metodypó¹niejsze.

Sporozewspółczesnychalgorytmówkorzystazezdobyczyzprzeszło±ci

gdy»okazujesi¦,»enaszychprzodkówcharakteryzowałaogromnaintuicja.

Zaprekursoraalgorytmówkomputerowychuwa»anajestAdaAugusta

(1815-1852),LadyLovelace,córkaByrona.Uwa»asi¦j¡zapierwsz¡progra-

mistk¦,jejimieniemnazwanojedenznowoczesnychj¦zykówprogramowania

wysokiegopoziomu,j¦zykAda.

Równocze±nieztworzeniemalgorytmówczłowiekstarałsi¦budowa¢urz¡-

dzenia,którepomogłybymuwykona¢obliczenia.Pierwszetakieurz¡dzenia

spotykamyju»uSumerów,około3000latp.n.e.Byłatoglinianatabliczka

zwy»łobionymirowkamiwktórychumieszczonokamienie.Przesuwanieka-

mienizjednejstronynadrug¡ułatwiałoliczenie.Udoskonaleniemtabliczek

SumerówbyłskonstruowanyprzezChi«czykówabakus(pó¹niejszeliczydło)-

drewnianatabliczkapodzielonanaklumny.Ka»dakolumnaoznaczałajedn¡

pozycj¦cyfrow¡.WXVIIwiekuzacz¦tobudowa¢urz¡dzeniazbli»onedona-

szychkalkulatorów.Du»eznaczeniedlarozwojutechnikiobliczeniowejmiało

wynalezienieprzezszkockiegomatematykaJ.Neperalogarytmówizastoso-

wanietzw.pałeczkiNeperapozwalaj¡cejznacznieprzyspieszy¢»mudneobli-

czenia.Nat¦pnymiurz¡dzeniamilicz¡cymibyłm.inn.sumatorarytmetyczny

BlaisePascalaisuwaklogarytmicznyskonstruowanyprzezE.GunteraiW.

Oughtreda.WieleosóbpodejmowałopróbyudoskonaleniasumatoraPascala

ijednymznichbyłG.W.Leibniz,któryw1671rokuzbudowałprost¡

czterodziałaniow¡maszyn¦licz¡c¡.

Odpocz¡tkuXIXwiekurozpoczynasi¦eramaszynbudowanychnaza-

sadachktóreodnajdujemywewspółczesnychkomputerach.Pierwszymich

konstruktorembyłCharlesBabbage,jednaktwórc¡komputerawdzisiejszym

sensiejestKonradZuse,któryswoj¡pierwsz¡maszyn¦zbudowałprzedII

wojn¡±wiatow¡.

Obecnekomputerywykonuj¡obliczeniairozwi¡zuj¡problemywcoraz

krótszymczasieajesttomo»liwenietylkodzi¦kipost¦powitechnikiale

tak»edzi¦kistosowaniubardziejefektywnychalgorytmówczylitakich,które

wykonuj¡mniejsz¡liczb¦operacji.

1.1.Reprezentacjealgorytmów

Reprezentacjaalgorytmutoinaczejjegoopis.Naprzykładzieprostego

zadaniarachunkowegopoka»emy,jakieutworzonydlaniegoalgorytmmo»e

mie¢reprezentacje.

Zadanie. Obliczwarto±¢funkcji

f ( x )= x

| x |

(1)

dladowolnegorzeczywistego x ,gdzie | x | oznaczafunkcj¦-warto±¢bezwzgl¦d-

na.

Naszymzadaniemjestpodaniealgorytmu,czylisposobuobliczaniawar-

to±citejfunkcji.Popierwszemusimyzadba¢odokładnesformułowaniezada-

nia-winformatyceu»ywasi¦poj¦cia specyﬁkacja naoznaczeniedokładnego

opisuzadania,któremaby¢wykonane.Naogółspecyﬁkacjamaposta¢wy-

szczególnienia,wktóryms¡wymienione dane dlazadaniaiwarunki,jakie

maj¡onespełnia¢,oraz wyniki irównie»warunki,jakiemusz¡onespełnia¢.

Abypoda¢specyﬁkacj¦zadaniapolegaj¡cegonaobliczeniuwarto±cina-

szejfunkcjimusimyuzupełni¢jejopisodziedzin¦.Zpostaciwzoruwynika,»e

funkcjaniejestokre±lonadla x =0.Ustalmywi¦cdodatkowo,»ewarto±ci¡

funkcjiwzerzejest0.Mo»emywi¦cju»poda¢specyﬁkacj¦rozwi¡zywanego

zadania:

Obliczaniewarto±ciprzykładowejfunkcji

Dane: Dowolnaliczbarzeczywista x .

Wynik: Warto±¢funkcji f ( x )podanejwzorem(1),je±li x jestró»neodzera,

0-wprzeciwnymprzypadku.

1.1.1.Słownyopisalgorytmu

Słownyopisalgorytmujestzazwyczajdyskusj¡osposobachrozwi¡zania

zadania.Poprzypomnieniudeﬁnicjifunkcji-warto±¢bezwzgl¦dnamo»eon

przyj¡¢nast¦puj¡c¡posta¢:

Obliczaniewarto±ciprzykładowejfunkcji

Dane: Dowolnaliczbarzeczywista x .

Wynik: Warto±¢funkcji f ( x )okre±lonejnast¦puj¡cymwzorem

> <

− 1 , dla x< 0

0 , dla x =0

1 , dla x> 0

f ( x )=

(2)

> :

Natymmo»nazako«czy¢słownyopismetodyrozwi¡zaniapostawionego

zadania.

1.1.2.Opisalgorytmuwpostacilistykroków

Listakrokówjestjednymznajcz¦±ciejstosowanychsposobówopisuobli-

cze«iichkolejno±ci.Poszczególnekrokizawieraj¡opisoperacji,któremaj¡

by¢wykonaneprzezalgorytm.Dodatkoweuwaginieb¦d¡cecz¦±ci¡algoryt-

muumieszczamyw { uwaga } .Dlanaszegozadaniaalgorytmwpostacilisty

krokówb¦dziewygl¡dałnast¦puj¡co:

Obliczaniewarto±ciprzykładowejfunkcji(2)

Dane: Dowolnaliczbarzeczywista x .

Wynik: Warto±¢funkcji f ( x )okre±lonejwzorem(2).

Krok0. Wczytajwarto±¢danej x .

Krok1. Je±li x> 0,to f ( x )=1.Zako«czalgorytm.

Krok2. { Wtymprzypadku x ¬ 0. } Je±li x =0,to f ( x )=0.Zako«cz

algorytm.

Krok3. { Wtymprzypadku x< 0. } Je±li x< 0,to f ( x )= − 1.Zako«cz

algorytm.

Opisalgorytmuwpostacikrokówpozwalabardzodokładnieokre±li¢,jakie

działaniamaj¡zosta¢wykonanewcelurozwi¡zaniazadania.

1.1.3.Schematblokowyalgorytmu

Schematblokowytograﬁcznysposóbprzedstawieniaalgorytmu.Składa

si¦onzklatekipoł¡cze«mi¦dzynimi.Wklatkachzapisywanes¡operacje,

któremaj¡by¢wykonane,apoł¡czeniawyznaczaj¡kolejno±¢ichwykony-

wania.Dlaodró»nieniarodzajówwykonywanychoperacjicz¦stostosujesi¦

ró»nekształtyklatek.

1.1.4.Drzewoalgorytmu

Drzewoalgorytmu,zwanetak»edrzewemoblicze«jestszczególnymro-

dzajemschematublokowego.Drzewo(wopracowaniachinformatycznychry-

sowanedogórynogamitoznaczykorzeniemdogóry)składasi¦z korzenia ,

li±ci i gał¦zi .Korze«-towierzchołek,wktórymrozpoczynasi¦działanie

algorytmu,wwierzchołkachpo±rednichumieszczanes¡operacjewykonywane

walgorytmie,wierzchołkiko«cowetoli±cie,któreodpowiadaj¡ró»nymwy-

nikomzako«czeniaoblicze«walgorytmie.Gał¦zie-topoł¡czeniawdrzewie

wskazuj¡cekierunekwykonywaniaoperacji.

Tensposóbprzedstawianiaalgorytmujestwygodnyzwłaszczadowyzna-

czanialiczbywykonywanychoperacji.

Innymsposobemprzedstawianiaalgorytmujestzbudowaniedrzewawyra-

»enia.Jaksamanazwawskazujejestonowykorzystywaneprzedewszystkim

doobliczaniawarto±ciwyra»e«.Ztakimdrzewemspotykamysi¦wszkole

bardzowcze±nie,podczasnaukiobliczaniawarto±ciwyra»eniazawieraj¡ce-

gonawiasy.Drzewowyra»eniamo»nanarysowa¢tradycyjnie,korzeniemdo

dołulubwsposóbinformatyczny-korzeniemdogóry.Obliczaniewarto±ci

wyra»eniazapisanegowdrzewiespływaodli±cigał¦ziamidokorzenia.

2.Algorytmyliniowe

Algorytmliniowy maposta¢ci¡gu(listy)kroków,którebezwarunkowo

musz¡by¢wszystkiewykonanewtakiejkolejno±ci,wjakiejwyst¦puj¡.

Algorytmyliniowes¡zapisemoblicze«,któremaj¡posta¢ci¡guoperacji

rachunkowych(matematycznych)wykonywanychbezsprawdzaniajakichkol-

wiekwarunków.Naprzykładwi¦kszo±¢oblicze«warkuszachkalkulacyjnych

przebiegawedługalgorytmuliniowego.Naogółjednakrozwi¡zaniaskompli-

kowanegoproblemuniemo»naprzedstawi¢tylkowpostacialgorytmulinio-

wego,chocia»mo»eonby¢cz¦±ci¡algorytmubardziejzło»onego.

Najprostszymprzykłademalgorytmuliniowegojestalgorytmobliczania

warto±ciwielomianu.Rozwa»mywielomiandrugiegostopnia

w ( x )= ax 2 + bx + c.

Abyobliczy¢jegowarto±¢zwyklepodnosimy x dokwadratuanast¦pnie

mno»ymyprzezwspółczynnik a , x mno»ymyprzez b idodajemyotrzymane

iloczynydo c .Wsumiewykonujemytrzyrazymno»enieidwarazydodawa-

nie.Zauwa»my,»eje»eliwył¡czaj¡c x przednawiasprzedstawimywielomian

wpostaci

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

wówczasobliczaj¡cjegowarto±¢b¦dziemymusieliwykona¢tylkodwamno-

»eniaidwadodawania.Niejesttowprawdziedu»yzyskalestajesi¦on

bardziejwidoczny,gdyb¦dziemymielidoczynieniazwielomianemtrzeciego

stopnia.Przekształcaj¡cwielomian

v ( x )= ax 3 + bx 2 + cx + d =(( ax + b ) x + c ) x + d

zamiastwykonaniapi¦ciudziała«mno»eniaitrzechdodawaniawykonamy

jedymietrzymno»eniaitrzydodawania.

Sposobyobliczaniawarto±ciwielomianówprzedstawionepowy»ejs¡szcze-

gólnymprzypadkiemtakzwanego schematuHornera .

3.Algorytmyzodgał¦zieniami

Wwieluobliczeniachwmatematyceczyﬁzycekolejno±¢wykonywanych

krokówzale»yodspełnienialubniejakiego±warunku.Wobliczeniacharyt-

metycznychnale»ydba¢oto,abywszystkiedziałaniabyłymo»liwedowy-

konania.Nale»ywi¦csprawdzi¢,czynp.liczbaznajduj¡casi¦podznakiem

pierwiastkakwadratowegojestdodatniaitp.Tezabezpieczenia,polegaj¡ce

nasprawdzeniupewnychwarunkóws¡szczególniewa»ne,gdyobliczeniama

wykona¢komputer.Wtakimprzypadkukonstruowanyalgorytmmusizawie-

ra¢krokiwarunkowe.

Rozwa»myrównaniekwadratowepostaci

ax 2 + bx + c =0 (3)

wktórymdanymis¡trzyliczby a , b i c nazywanewspółczynnikamitrójmianu

kwadratowego.Zakładasi¦przytym,»ewspółczynnik a 6 =0.Pierwiastkitego

równaniawyznaczasi¦zewzorów

x 1 = − b − p

2 a . (4)

Podamyalgorytm,któryjestnajcz¦±ciejwykorzystywanymnalekcjach

matematykialgorytmemrozwi¡zywaniarównaniakwadratowego.

Algorytmrozwi¡zywaniarównaniakwadratowego

Dane: Współczynniki a,bic równania(3).

Wyniki: Pierwiastkirównania(3),je±lidanewspółczynnikirzeczywi±cie

okre±laj¡równaniekwadratoweirównaniemapierwiastki.Je±lirównanie

niemapierwiastków,towypisujeodpowiednikomunikat.

Krok1. Je±li a =0towypiszkomunikat,»eniejesttorównaniekwadratowe

izako«czalgorytm.

Krok2. Obliczwarto±¢wyró»nika= b 2 − 4 ac .

Krok3. Je±li < 0,towypiszkomunikat,»erównanieniemapierwiastków

izako«czalgorytm.

Krok4. Je±li=0,toobliczobapierwiastkiztegosamegowzoru: x 1 =

x 2 = − b/ 2 a ,wypiszichwarto±¢izako«czalgorytm.

Krok5. (Wtymprzypadku > 0).Obliczpierwiastki x 1 i x 2 zewzorów

(4),wypiszichwarto±ciizako«czalgorytm.

4.Porz¡dkowanieci¡guelementów

Porz¡dkowanieliczblubinaczejsortowaniejestjednymznajwa»niejszych

inajpopularniejszychzagadnie«informatycznych.Najłatwiejjestuporz¡d-

kowa¢dwieliczbygdy»nale»ywykona¢tylkojedn¡operacj¦porównania.

4.1.Porz¡dkowanietrzechliczb

Zaczniemywi¦codtrzechliczb.Mo»emypost¡pi¢nast¦puj¡co:najpierw

ustawiamydwiepierwszeliczbywewła±ciwejkolejno±cianast¦pnietrzeci¡

2 a ,x 2 = − b +

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: