pierwsze_przyklady_algorytmow.pdf

Algorytmyodprojektudozapisuwjęzyku

programowania

AndrzejSendlewski

14października2009roku

Algorytm

Zacznijmyodprzypomnieniaokreśleniapojęciaalgorytmu.

ALGORYTM to skończony ciąg dobrze określonych i jednoznacz

nych instrukcji (rozkazów) prowadzących od DANYCH do WY

NIKÓW, z których każda musi być wykonywana mechanicznie w

skończonym czasie.

Algorytm rozwiązujący dany problem musi być ostatecznie zapisany przy

najmniejwjęzykuprogramowania.Jednakżewfazieprojektowaniaposługu

jemy się zarówno językiem naturalnym (niestety mało precyzyjnym) i spe

cjalniedotegoceluwymyślonymjęzykiem„obrazkowym”,zwanymjęzykiem

schematów blokowych .Schematblokowytografzorientowanyoróżnych

rodzajachwierzchołków,zwyróżnionymi:wierzchołkiempoczątkowymikoń

cowym. Każda ścieżka prowadząca od wierzchołka początkowego do wierz

chołkakońcowegojestmożliwymciągieminstrukcji,któryzostaniewykonany

wtrakciedziałaniaalgorytmunakonkretnych danychwejściowych. Niebę

dziemytutajformalnieopisywaćjęzykaschematówblokowych,awyjaśnimy

wszystkonaprzykładach.Zacznijmyodbanalnegozadania.

Schematyblokowedowszystkichprzykładównarysujsamodzielnie

(patrzwykład).

1 Przykład

Zaprojektowaćalgorytmobliczającydladanejliczbynaturalnej n sumę s =

1+2+3+ ... + n .

Rozwiązaniejestbardzoproste.Każdymatematykumiezsumowaćteliczby

zgodniezewzorem:

1+2+3+ ... + n = 1+ n

2 · n.

Przeto wystarczy nadać zmiennej s wartość 1+ n

2 · n tj., wykonać jedną

instrukcjęprzypisania.OtocałyalgorytmwjęzykuPASCAL

begin

s:=((1+n)*n) div 2;

end;

Niewkażdejsytuacjibędziemywstaniepodaćwzór(albogonieznamy,albo

takiwzórnieistnieje),azadanietrzebarozwiązać.Zauważmy,żewnaszym

przypadkuwystarczywykonać n kroków,w k tymkrokudodającdosumypo

k − 1krokachliczbę k .Wymagato n instrukcjiprzypisania,coniestetyzależy

od danej n . Języki programowania dopuszczają konstrukcję umożliwiająca

zapis czynności trwających dowolnie długo za pomocą skończonego zapisu.

Jesttostrukturaprogramistycznatzw. pętli .(narysujsamodzielnieschemat

blokowyzwykładu).

begin

s:=0; k:=1;

while k<=n do

begin

s:=s+k; k:=k+1;

end;

Zobaczinnerozwiązaniazużyciem pętlirepeatorazforwprogramieSche

matyBlokowe.

2 Przykład

Zaprojektowaćalgorytmobliczającydladanychliczbnaturalnych x i y iloraz

q iresztę r zdzielenia x przez y .

Otorozwiązanie

begin

q:=0; r:=x;

while r>=y do

begin

q:=q+1; r:=ry;

end;

Algorytmtenkończysię,gdyżkażdewykonanieinstrukcjiwpętlipomniejsza

wartość r o y ,cogwarantuje,żeposkończonejilościtakichinstrukcjiwartość

zmiennej r będziemniejszaodwartości y .Natomiastkońcowewartości q i r

sąposzukiwanymodpowiednioilorazemiresztą,gdyżnapoczątkualgorytmu

ipokażdymwykonaniuinstrukcjiwpętliwartościzmiennychspełniająrów

nanie x = q · y + r .

3 Przykład

Zaprojektowaćalgorytmobliczającydladanychliczbnaturalnych a i b naj

większywspólnypodzielniktychliczb.

Oto trzy różne rozwiązania. Algorytmy te oparte są na klasycznym rozu

mowaniu Euklidesa znanym z arytmetyki liczb całkowitych. Zmienne x i y

wprowadzamyjedyniepoto,abyzachowaćpierwotnewartościdanych a i b .

begin {algorytm Euklidesa z odejmowaniem}

x:=a; y:=b;

while x<>y do

if x>y then x:=xy else y:=yx;

end; {NWD(a,b)=x=y}

begin {algorytm Euklidesa z dzieleniem z resztą}

x:=a; y:=b;

while (x>0) and (y>0) do

if x>y then x:=x mod y else y:=y mod x;

end; {NWD(a,b)=x+y}

begin {klasyczny algorytm Euklidesa}

x:=a; y:=b;

repeat

r:=x mod y;

x:=y;

y:=r;

until

r=0;

end; {NWD(a,b)=y}

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: