Podstawy Informatyki

Metalurgia, I rok

Wykład 4

Algorytmy

Sformułowanie problemu.

Opracowanie metodyki rozwiązania.

Opracowanie algorytmu.

Napisanie kodu źródłowego (zakodowanie) w wybranym
języku (Pascal, Fortran, C++, itp.).

Kompilacja kodu źródłowego

Uruchomienie programu na komputerze.

Wykonanie obliczeń.

Analiza otrzymanych wyników.

Usunięcie błędów programu (debugging).

Programowanie

Co to jest algorytm?

Jeżeli mamy do wykonania jakieś zadanie, budujemy sposób,
przepis realizacji tego zadania. Taki przepis to

algorytm.

Przykłady:

•przepis kucharski,

•instrukcja składania mebla/urządzenia. . . ,

•zapis nutowy,

•wykonywanie pisemne dodawania/mnożenia/dzielenia...

Algorytm (definicja nieformalna)

to sposób postępowania (przepis) umożliwiający rozwiązanie
określonego zadania (klasy zadań), podany w postaci
skończonego zestawu czynności do wykonania, ze wskazaniem
ich następstwa.

Istotne cechy algorytmu

•Definicja zadania = co algorytm ma zrobić.

•Opis ciągu czynnosci, które po kolei mają być wykonane.

•Czynności te muszą być na tyle proste (i możliwe do wykonania),
aby wykonawca algorytmu mógł je bez dodatkowego tłumaczenia,
wykonać ⇒operacje elementarne;
odpowiednio dobrany poziom szczegółowości.

•Skonczona ilość operacji elementarnych ⇒skończony czas
działania.

•Algorytm dostaje pewne informacje (dane wejściowe) i zwraca
jakieś (oczekiwane) wyniki — dane wyjściowe.

•Może istnieć kilka przepisów, które dają w efekcie te same
wyniki.

Algorytm

Pochodzenie nazwy:

od nazwiska w wersji łacińskiej Algorithmus, Algorismus

perskiego matematyka Muhammeda ibn Musy zwanego al

Chuwarismi, żyjącego w IX w (podał on algorytmy

wykonywania działań arytmetycznych na liczbach
dziesiętnych.

Algorytmika - dział wiedzy zajmujący się badaniem algorytmów

Sposoby zapisu algorytmu:

•słowami,

•za pomocą schematu blokowego,

•w pseudokodzie,

•w jednym z języków programowania

Program - formalnie spisana wersja algorytmu.

Algorytm sekwencyjny - opis słowny

Postawienie problemu:

- Co należy zrobić, aby zobaczyć film “Katyń” ?

Algorytm 1a:

Idź do kina

Kup bilet

Obejrzyj film

Wróć do domu



Algorytm powyższy zawiera 4 podstawowe składniki, z
których każdy wymaga zakończenia wykonania pewnej

akcji przed rozpoczęciem następnej.



W komputerze każdy składnik będzie zapisany jako

instrukcja lub grupa instrukcji (procedura).



Algorytm powinien być kolejno uściślany, by mógł być w

swojej ostatecznej postaci zrozumiały dla komputera, oraz

by uwzględniał wszystkie okoliczności przewidziane przez
projektanta.

Algorytm 1b:

POCZĄTEK

jeżeli nie wyświetlają filmu "Katyń”

to znajdź sobie inne zajęcie

w przeciwnym razie { idź do kina

jeżeli jest kolejka to ustaw się w kolejce (na końcu?)
dopóki przed Tobą stoją ludzie wykonuj przesuwaj się do
przodu
jeżeli są wolne miejsca to {kup bilet, znajdź swoje miejsce

dopóki trwa projekcja

wykonuj oglądaj film}

w przeciwnym razie zaklnij po cichu, wyjdź z kina

wróć do domu }

KONIEC

Przykład algorytmu:

sumowanie zarobków pracowników

Dane: lista pracowników z zarobkami (tablica A)

(1) zanotuj "na boku"(zmienna

suma) liczbę 0;

Powtarzaj

(2) przeglądaj ankiety i dodawaj zarobki każdego pracownika do

liczby "na boku";

Aż do

(3) kiedy osiągniesz koniec listy, przedstaw wartość liczby "na boku"

jako wynik (

suma).

Cechy tego algorytmu:

•

Działa na różnych zestawach danych, ale daje poprawne wyniki.

•

Sam tekst algorytmu jest ograniczony i krótki, ale proces który
opisuje zmienia się wraz z długościa listy pracowników.

Algorytmy przedstawione powyżej wykorzystują język
naturalny oraz

słowa kluczowe. Słowa kluczowe definiują

podstawowe struktury sterujące programu oraz procesy
podejmowania decyzji występujących w algorytmie:



jeżeli ..... to ..... w przeciwnym razie



dopóki ..... wykonuj



powtarzaj ..... aż do

Te słowa kluczowe mają swoje odpowiedniki w każdym z
języków programowania.

Wprowadzenie słów kluczowych do opisu słownego
algorytmu jest częścią tzw.

pseudo - kodu,

wykorzystywanego do zapisu algorytmu.

Szczegółowy algorytm jest podstawą dla prawidłowo
zakodowanego programu.

Algorytm z “wcięciami” pozwala na bardziej czytelny zapis, i
stanowi nieformalną metodę ułatwiającą śledzenie “dróg”
programu.

Oprócz algorytmów słownych, często
stosuje się zapis algorytmu w postaci

schematów blokowych.

Schemat blokowy (block diagram, flowchart) to diagram,
na którym algorytm jest reprezentowany przez opisane
figury geometryczne, połączone liniami zgodnie z
kolejnością wykonywania czynności wynikających z
przyjętego algorytmu rozwiązania zadania; pozwala
dostrzec istotne etapy algorytmu i logiczne zależności
między nimi;

START

czytaj:
n,a(i), dla i=1,...n

suma=0

suma=suma + a(i)

i=i+1

i ≤

≤

≤

≤

n

tak

druk: suma

STOP

nie

Schematy blokowe

Start

Stop

instrukcja

?

tak

nie

czytanie danych,

wydruk wyników

•

strzałka wskazuje kierunek przebiegu sterowania programem,

łączy inne bloki,

•

operand (prostokąt) — wszystkie operacje z wyjątkiem instrukcji

wyboru,

•

predykat (romb) — instrukcja wyboru,

•

etykieta (owal) — początek lub koniec sekwencji schematu.

•

wejście/wyjście (równoległobok).

Algorytm Euklidesa

Problem: mając dane dwie liczby naturalne a i b znaleźć

ich największy wspólny dzielnik.

Pierwotnie problem ten sprowadzał się do czysto
geometrycznego problemu znalezienia wspólnej miary dla
dwóch odcinków.

Zadanie algorytmiczne:

Dane: a, b ∈

N,

Wynik: NWD(a,b).

Opis słowny:

•dane są dwie liczby

a i b;

•jeśli

a jest równe b, to NWD jest równe a,

•w przeciwnym wypadku, jeżeli

a jest większe od b, to zmień a

na równe

a - b, a jeżeli a jest mniejsze od b to zmień b na b - a;

•zacznij od początku.

START

czytaj:
a, b

a=a-b

tak

STOP

nie

a<>b

a>b

b=b-a

tak

Drukuj a

nie

Schemat blokowy

Algorytm Euklidesa (metoda 1)

•Pseudokod

loop

if a = b then return a;

else if a > b then a := a -b;

else b := b -a;

•Język C

while(a != b) {

if(a > b) a -= b;

else b -= a;

}

return a;

Algorytm Euklidesa (metoda 2)

•Język C

if(a < b) {

t = a;

a = b;

b = t;

}

while(b != 0) {

c = a % b;

a = b;

b = c;

}

return a;

Przy opracowywaniu algorytmu zwracamy uwagę na:

jego poprawność semantyczną (składnię),

prostotę,

czas działania,

ilość zajmowanej pamięci komputera,

optymalność,

ograniczenia

Zdanie proste

Określa elementarny lub bardziej złożony krok algorytmu.

Jeżeli jest to krok elementarny, to wystarczy przy tworzeniu programu

zapisać ten krok w języku programowania.

Jeżeli natomiast jest to złożony krok algorytmu, to podczas

uszczegółowienia algorytmu zostanie on zastąpiony sekwencją
prostszych zdań.

Przykład elementarnego kroku - instrukcja podstawienia (przypisania):
przypisz zmiennej suma wartość zero

FORTRAN:

suma = 0.0

C:

suma = 0.0 ;

PASCAL:

suma :=0.0 ;

Zdanie złożone:
oblicz pierwiastek równania kwadratowego

Jest to złożony krok algorytmu wymagający uszczegółowienia.

W programie jest to realizowane poprzez instrukcję złożoną grupującą

ciąg instrukcji prostych.

PODEJMOWANIE DECYZJI W PROGRAMIE

Zdanie decyzyjne “jeśli”

Zdanie to zawiera strukturę opisującą decyzje

podejmowane w algorytmie. Istnieją 2 rodzaje struktur:

struktura prosta : jeśli ..... to

struktura z alternatywą: jeśli ..... to .... w przeciwnym
razie

Struktura prosta

jeśli warunek to

zdanie

gdzie warunek jest wyrażeniem przyjmującym dwie
wartości:

- wartość prawdy,
- wartość fałszu

Jeżeli warunek przyjmie wartość prawdy, to wykonuje się

zdanie, a gdy warunek przyjmie fałsz, to zdanie nie
zostanie wykonane.

Przykład:

jeśli średnia ocen studenta jest większa od 4.5 to

wpisz studenta na listę nagród

warunek :

ś

rednia ocen studenta jest większa od 4.5

Jeżeli warunek jest prawdziwy, to wykonywane jest

zdanie:
wpisz studenta na listę nagród

Struktura z alternatywą

jeśli warunek to

zdanie 1

w przeciwnym razie

zdanie 2

Rozważmy następujący problem:

W zależności od wartości jakie przyjmuje zmienna x (np

ocena) należy wydrukować następujące komunikaty:

dla x <3

komunikat

“negatywna”

dla 3 <= x <= 6

komunikat

“pozytywna”

dla x > 6

komunikat

“niemożliwa”

Algorytm przyjmie postać:
jeżeli x <3 to

wypisz “negatywna”

w przeciwnym razie

jeżeli 3 <= x i x <= 6 to

wypisz “pozytywna”

w przeciwnym razie

wypisz “niemożliwa”

W programach numerycznych warunkiem jest najczęściej

wyrażenie logiczne:

nie, lub, i

Np.: a lub b,

(a lub b) i c, .....

W wyrażeniach logicznych występują też relacje:
= , <>, >, <, <=, >=

Np.: a > b,

c <= d

Przykład zdania decyzyjnego:

jeśli (a > b) lub (c <= d) to

podstaw x = 0

FORTRAN:
a).

IF ( warunek ) THEN

zdanie 1

ENDIF

b).

IF ( warunek ) THEN

zdanie 1

ELSE

zdanie 2

ENDIF

PASCAL:
a).

IF warunek

THEN

zdanie 1;

b).

IF warunek

THEN

zdanie 1

ELSE

zdanie 2;

C:
a).

IF warunek

zdanie 1;

b).

IF warunek

zdanie 1;

ELSE

zdanie 2;

Instrukcja decyzyjna wybierz

Zdanie wybierz służy do wyboru jednej z kilku możliwości.

Ma ono postać:

wybierz przełącznik z

wartość_1: zdanie_1
....
wartość_n: zdanie_n

w przeciwnym razie akcja awaryjna

Przykład:
wybierz p z

1: wykonaj wariant pierwszy
2: wykonaj wariant drugi
3: wykonaj wariant trzeci

w przeciwnym razie wydrukuj komunikat o błędzie

Przykład:

Program cenzurka1

....
....
wybierz ocena z

6: pisz(‘celujacy’);
5: pisz(‘bardzo dobry’);
4: pisz(‘dobry’);
3: pisz(‘dostateczny’);
2: pisz(‘niedostateczny’);

w przeciwnym razie pisz(‘blad danych’)
....
....

Koniec

Program cenzurka2

.....

jeżeli ocena = 6 to

pisz(‘celujacy’)

w przeciwnym razie

jeżeli ocena = 5 to

pisz(‘bardzo dobry’)

w przeciwnym razie

jeżeli ocena = 4 to

pisz(‘dobry’)

w przeciwnym razie

jeżeli ocena = 3 to

pisz(‘dostateczny’)

w przeciwnym razie

jeżeli ocena = 2 to
pisz(‘niedostateczny’)
w przeciwnym razie

pisz(‘blad danych’)

Blok instrukcji

W przypadku, gdy w danej instrukcji, np. instrukcji
warunkowej, powinna wykonać się więcej niż jedna
instrukcja, wówczas stosowany jest

blok instrukcji.

C:

{

instrukcja1;

instrukcja2;

instrukcja3;

........

}

Pascal:

begin

instrukcja1;

instrukcja2;

instrukcja3;

........

end;

Iteracja warunkowa dopóki(while)

dopóki

(wyrażenie) wykonuj instrukcja1;

instrukcja1

tak

wyrażenie

nie

Instrukcja1 może nie wykonać się ani jeden raz!

Działanie pętli:

• Obliczana jest wartość wyrażenia

• Jeśli wyrażenie jest równe fałszywe to instrukcja1 nie jest
w ogóle wykonywana

• Wpp. wykonywana jest instrukcja1.

• Ponownie obliczana jest wartość wyrażenia i ponownie
sprawdzana jego prawdziwość itd.

• Jeśli wyrażenie będzie fałszywe, to działanie pętli zostanie
przerwane

Uwaga: obliczenie wartości wyrażenia odbywa się

przed

wykonaniem instrukcji1

Iteracja warunkowa powtarzaj ... aż do ...

(repeat ... until ...)

powtarzaj

instrukcja1

aż do

(wyrażenie) ;

instrukcja1

nie

wyrażenie

tak

Instrukcja1 musi wykonać się conajmniej jeden raz!

Działanie pętli:

•Wykonywana jest instrukcja1

•Obliczana jest wartość wyrażenia

• Jeśli wyrażenie jest równe fałszywe to instrukcja1 jest
wykonywana kolejny raz

• Ponownie obliczana jest wartość wyrażenia i ponownie
sprawdzana jego prawdziwość itd.

• Jeśli wyrażenie będzie prawdziwe, to działanie pętli
zostanie przerwane

Uwaga: obliczenie wartości wyrażenia odbywa się

po

wykonaniu instrukcji1

Iteracja ograniczona dla

(for)

dla <zmienna> od <w1<> do <w2> (z krokiem <k>)

wykonuj

instrukcja1 ;

<zmienna> ← <w1>

tak

zmienna ≤ <w2>

nie

Instrukcja1 może nie wykonać się ani jeden raz!

instrukcja1

<zmienna> + <k>

Działanie pętli:

•Wykonanie instrukcji inicjalizujących pętlę

<zmienna> ←

←

←

←

<w1>

• Sprawdzenie wyrażenia warunkowego

<zmienna> ≤

≤

≤

≤

<w2>.

Jeśli fałsz, praca pętli zostaje zakończona,

Jeśli prawda, wykonana zostanie instrukcja1

• Wykonanie instrukcji

zwiększ <zmienna> o <k>

Uwaga: sprawdzenie wyrażenia <zmienna> ≤

≤

≤

≤

<w2>

odbywa się

przed wykonaniem instrukcja1

Instrukcje wejścia/wyjścia

Umożliwiają komunikowanie się programu z
użytkownikiem.

Umożliwiają czytanie danych jak również
wypisywanie komunikatów i wyników prowadzonych
obliczeń.

Np.: Pascal -

• read(a,b);
{ z klawiatury wprowadzamy : np. 12 5 }

• writeln(a);
{drukujemy na ekranie wartość a (np. 12) }