algorytmy 5 id 57587 Nieznany (2)

Algorytmy

–

Jędryczkowski

–

2005 r.

Algorytmy

–

Jędryczkowski

–

2005 r.

Algorytmem

nazywamy sko

czony ci

g czynno

ci,

przekształcaj

cy zbiór danych wej

ciowych (danych)

na zbiór danych wyj

ciowych (wyników).

Algorytmem

nazywamy sko

czony ci

g czynno

ci,

nazywamy sko

czony ci

g czynno

ci,

przekształcaj

cy zbiór danych wej

ciowych (danych)

przekształcaj

cy zbiór danych wej

ciowych (danych)

na zbiór danych wyj

ciowych (wyników).

na zbiór danych wyj

ciowych (wyników).

DANE

WYNIKI

Algorytm

Algorytmy

–

Jędryczkowski

–

2005 r.

Algorytmy,

które wykonuj

działania matematyczne

na danych liczbowych, nazywamy algorytmami
numerycznymi.

Algorytmy,

które wykonuj

działania matematyczne

które wykonuj

działania matematyczne

na danych liczbowych, nazywamy

algorytmami

numerycznymi.

Algorytmika,

to dział informatyki zajmuj

cy si

ró

nymi

aspektami

tworzenia

analizowania

algorytmów

Algorytmika

to dział informatyki zajmuj

cy si

to dział informatyki zajmuj

cy si

ró

nymi

aspektami

tworzenia

analizowania

ró

nymi

aspektami

tworzenia

analizowania

algorytmów

Algorytmy

–

Jędryczkowski

–

2005 r.

Program komputerowy

to logicznie uporz

dkowany

g instrukcji j

zyka programowania realizuj

algorytm.

Program komputerowy

to logicznie uporz

dkowany

to logicznie uporz

dkowany

g instrukcji j

zyka programowania realizuj

g instrukcji j

zyka programowania realizuj

algorytm.

Specyfikacja zadania

to szczegółowy opis zadania,

w którym wymienia si

dane wej

ciowe i wyniki oraz

warunki jakie musz

spełnia

. Specyfikacja okre

zatem zwi

zek pomi

dzy danymi a wynikami.

Specyfikacja zadania

to szczegółowy opis zadania,

w którym wymienia si

dane wej

ciowe i wyniki oraz

w którym wymienia si

dane wej

ciowe i wyniki oraz

warunki jakie musz

spełnia

. Specyfikacja okre

warunki jakie musz

spełnia

. Specyfikacja okre

zatem zwi

zek pomi

dzy danymi a wynikami.

zatem zwi

zek pomi

dzy danymi a wynikami.

Algorytmy

–

Jędryczkowski

–

2005 r.

Problem

Algorytm

Program

komputerowy

Komputer

Algorytm

zapis

wykonuje

realizuje

wybór

Algorytmy

–

Jędryczkowski

–

2005 r.

Problem:

oblicz

redni

arytmetyczn

trzech

dowolnych liczb rzeczywistych.

Problem:

oblicz

redni

arytmetyczn

trzech

oblicz

redni

arytmetyczn

trzech

dowolnych liczb rzeczywistych.

Dane:

trzy dowolne liczby rzeczywiste A, B, C

Dane:

trzy dowolne liczby rzeczywiste

Wynik:

warto

ść

redniej arytmetycznej liczb A, B, C,

równ

Wynik:

warto

ść

redniej arytmetycznej liczb

warto

ść

redniej arytmetycznej liczb

równ

Algorytmy

–

Jędryczkowski

–

2005 r.

1. Zacznij algorytm

2. Wprowadź wartość trzech liczb A, B, C

3. Oblicz wartość wyrażenia: SUMA:=A+B+C

4. Oblicz wartość wyrażenia SR:=SUMA/3

5. Wyprowadź wynik: SR

6. Zakończ algorytm

Zacznij algorytm

Wprowadź wartość trzech liczb A, B, C

Oblicz wartość wyrażenia: SUMA:=A+B+C

Oblicz wartość wyrażenia SR:=SUMA/3

Wyprowadź wynik: SR

Zakończ algorytm

Algorytmy

–

Jędryczkowski

–

2005 r.

Problem:

oblicz warto

ść

bezwzgl

dowolnej

liczby rzeczywistej.

Problem:

oblicz warto

ść

bezwzgl

dowolnej

oblicz warto

ść

bezwzgl

dowolnej

liczby rzeczywistej.

Dane:

dowolna liczba rzeczywista A

Dane:

dowolna liczba rzeczywista

Wynik:

warto

ść

bezwzgl

dna liczby A równa W

Wynik:

warto

ść

bezwzgl

dna liczby

warto

ść

bezwzgl

dna liczby

równa

Algorytmy

–

Jędryczkowski

–

2005 r.

1. Zacznij algorytm

2. Wprowadź wartość liczbę A

3. Jeżeli A>=0, to W:=A. W przeciwnym

wypadku W:=-A

4. Wyprowadź wynik: W

5. Zakończ algorytm

Zacznij algorytm

Wprowadź wartość liczbę A

Jeżeli A>=0, to W:=A. W przeciwnym

wypadku W:=

Wyprowadź wynik: W

Zakończ algorytm

Algorytmy

–

Jędryczkowski

–

2005 r.

STOP

START

Wprowadź (A, B)

Wyprowadź (W)

Początek algorytmu

Koniec algorytmu

Wprowadzanie danych

Blok wejścia

Wprowadzanie danych

Blok wejścia

Wyprowadzanie danych

Blok wyjścia

Wyprowadzanie danych

Blok wyjścia

Algorytmy

–

Jędryczkowski

–

2005 r.

S:=A+B

W:=C/A

Czy

A=0?

TAK

NIE

Sprawdzanie warunków

Blok warunkowy

albo decyzyjny

Sprawdzanie warunków

Blok warunkowy

albo decyzyjny

Wykonywanie obliczeń

Blok operacyjny

Wykonywanie obliczeń

Blok operacyjny

Algorytmy

–

Jędryczkowski

–

2005 r.

Łącznik

Połączenie

Algorytmy

–

Jędryczkowski

–

2005 r.

Średnia

arytmetyczna trzech

dowolnych liczb

rzeczywistych

STOP

START

Wprowadź (A, B, C)

Wyprowadź (SR)

SUMA:=A+B+C

SR:=SUMA/3

Algorytmy

–

Jędryczkowski

–

2005 r.

Wartość bezwzględna

dowolnej liczby

rzeczywistej.

Algorytm z warunkiem.

STOP

START

Wprowadź (A)

Wyprowadź (W)

W:=A

Czy

A>0?

NIE

W:=

TAK

Algorytmy

–

Jędryczkowski

–

2005 r.

Notacja zwana „DRZEWEM ALGORYTMU”
nadaje się do prostego przedstawiania
algorytmów porządkowania.

DRZEWO ALGORYTMU składa się z:
• korzenia
• wierzchołków pośrednich (węzłów)
• wierzchołków końcowych (liści)

Notacja zwana

„DRZEWEM ALGORYTMU”

nadaje się do prostego przedstawiania

algorytmów porządkowania.

DRZEWO ALGORYTMU

składa się z:

•

korzenia

•

wierzchołków pośrednich (węzłów)

•

wierzchołków końcowych (liści)

Algorytmy

–

Jędryczkowski

–

2005 r.

Porządkowanie

trzech dowolnych

liczb A, B, C.

A<=B

C<=B

C<=A

B<=C

C<=A

(C, A, B)

(C, B, A)

(A, B, C)

(A, C, B)

(B, C, A)

(B, A, C)

TAK

NIE

TAK

NIE

Algorytmy

–

Jędryczkowski

–

2005 r.

ITERACJĄ nazywamy instrukcję powtarzania
ciągu instrukcji. Liczba powtórzeń może być
ustalona bądź zależeć od spełnienia
określonego warunku sprawdzanego w każdej
iteracji.
Iterację często nazywamy PĘTLĄ.

ITERACJĄ

nazywamy instrukcję powtarzania

ciągu instrukcji. Liczba powtórzeń może być

ustalona bądź zależeć od spełnienia

określonego warunku sprawdzanego w każdej

iteracji.

Iterację często nazywamy

PĘTLĄ.

Algorytmy

–

Jędryczkowski

–

2005 r.

Wyświetlanie

kolejnych liczb

od 0 do 14

STOP

START

K:=0

Wyprowadź (K)

K:=K+1

K < 15

TAK

NIE

Algorytmy

–

Jędryczkowski

–

2005 r.

Algorytm

ten stosuje si

do wyszukiwania

najwi

kszego (najmniejszego) elementu w zbiorze.

Algorytm

ten stosuje si

do wyszukiwania

ten stosuje si

do wyszukiwania

najwi

kszego (najmniejszego) elementu w zbiorze.

najwi

kszego (najmniejszego) elementu w zbiorze.

Dane:

dziesi

ęć

nieuporz

dkowanych dowolnych liczb

Dane:

dziesi

ęć

nieuporz

dkowanych dowolnych liczb

dziesi

ęć

nieuporz

dkowanych dowolnych liczb

Wynik:

najwi

ksza i najmniejsza liczba

Wynik:

najwi

ksza i najmniejsza liczba

najwi

ksza i najmniejsza liczba

Algorytmy

–

Jędryczkowski

–

2005 r.

1. Zacznij algorytm

2. Przyjmij za MAX (MIN) pierwszą liczbę

3. Dla kolejnych liczb jeśli MAX jest mniejszy od

kolejnej liczby X (MAX<X) wykonaj MAX:=X

(jeśli MIN jest większy od kolejnej liczby X

(MIN>X) wykonaj MIN:=X)

4. Wyprowadź wynik: MAX (MIN)

5. Zakończ algorytm

Zacznij algorytm

Przyjmij za MAX (

MIN

) pierwszą liczbę

Dla kolejnych liczb jeśli MAX jest mniejszy od

kolejnej liczby X (MAX<X) wykonaj MAX:=X

(

jeśli MIN jest większy od kolejnej liczby X

(MIN>X) wykonaj MIN:=X

)

Wyprowadź wynik: MAX (

MIN

)

Zakończ algorytm

Algorytmy

–

Jędryczkowski

–

2005 r.

Zasada ta ma nast

puj

cy cel:

Problem algorytmiczny dzielimy na mniejsze cz

ęś

ci,

których rozwi

zanie daje rozwi

zanie problemu

głównego. Najcz

ęś

ciej w ten sposób mo

efektywniej rozwi

problem główny.

Zasada ta ma nast

puj

cy cel:

Zasada ta ma nast

puj

cy cel:

Problem algorytmiczny dzielimy na mniejsze cz

ęś

ci,

Problem algorytmiczny dzielimy na mniejsze cz

ęś

ci,

których rozwi

zanie daje rozwi

zanie problemu

których rozwi

zanie daje rozwi

zanie problemu

głównego. Najcz

ęś

ciej w ten sposób mo

głównego. Najcz

ęś

ciej w ten sposób mo

efektywniej rozwi

problem główny.

efektywniej rozwi

problem główny.

Algorytmy

–

Jędryczkowski

–

2005 r.

Algorytm

ten stosuje si

do jednoczesnego

wyszukiwania

najwi

kszego

najmniejszego

elementu w zbiorze.

Algorytm

ten stosuje si

do jednoczesnego

ten stosuje si

do jednoczesnego

wyszukiwania

najwi

kszego

najmniejszego

wyszukiwania

najwi

kszego

najmniejszego

elementu w zbiorze.

Dane:

dziesi

ęć

nieuporz

dkowanych dowolnych liczb

Dane:

dziesi

ęć

nieuporz

dkowanych dowolnych liczb

dziesi

ęć

nieuporz

dkowanych dowolnych liczb

Wynik:

najwi

ksza i najmniejsza liczba

Wynik:

najwi

ksza i najmniejsza liczba

najwi

ksza i najmniejsza liczba

Algorytmy

–

Jędryczkowski

–

2005 r.

W celu wyszukania najmniejszej i najwi

kszej

liczby

oczywi

cie

wykona

najpierw

algorytm MAX a potem algorytm MIN. Takie
post

powanie jest jednak mało ekonomiczne bo

wymaga przejrzenia całego zbioru liczb dwukrotnie.

Wst

pnie podzielimy zbiór liczba na dwa podzbiory

wykonuj

c porównania s

siednich liczb (kolejny

slajd)

W celu wyszukania najmniejszej i najwi

kszej

W celu wyszukania najmniejszej i najwi

kszej

liczby

oczywi

cie

wykona

najpierw

liczby

oczywi

cie

wykona

najpierw

algorytm MAX a potem algorytm MIN. Takie

post

powanie jest jednak mało ekonomiczne bo

post

powanie jest jednak mało ekonomiczne bo

wymaga przejrzenia całego zbioru liczb dwukrotnie.

Wst

pnie podzielimy zbiór liczba na dwa podzbiory

Wst

pnie podzielimy zbiór liczba na dwa podzbiory

wykonuj

c porównania s

siednich liczb (kolejny

wykonuj

c porównania s

siednich liczb (kolejny

slajd)

Algorytmy

–

Jędryczkowski

–

2005 r.

Zbiór liczb:

2, 5, 3, 7, 9, 1, 4, 8, 0, 6

Zbiór liczb:

2, 5, 3, 7, 9, 1, 4, 8, 0, 6

2<5

3<7

9>1

4<8

0<6

Kandydaci na MAX

Kandydaci na MIN

Pierwszy zbiór przetwarzamy algorytmem MAX a drugi
algorytmem MIN otrzymuj

c szukane warto

ci.

Pierwszy zbiór przetwarzamy algorytmem MAX a drugi

algorytmem MIN otrzymuj

c szukane warto

ci.

algorytmem MIN otrzymuj

c szukane warto

ci.

Algorytmy

–

Jędryczkowski

–

2005 r.

Porz

dkowanie przez wybór (selection sort)

Algorytm ten wykorzystuje poznany wcze

niej

algorytm

MIN.

Wyszukiwany

jest

najmniejszy

element, a nast

pnie zamieniany jest miejscami z

ostatnim elementem przeszukiwanego podci

warto

ci. Kolejne wyszukiwanie prowadzone jest

bez elementów, które zostały ju

uporz

dkowane.

Porz

dkowanie przez wybór (

Porz

dkowanie przez wybór (

selection

sort)

Algorytm ten wykorzystuje poznany wcze

niej

Algorytm ten wykorzystuje poznany wcze

niej

algorytm

MIN.

Wyszukiwany

jest

najmniejszy

algorytm

MIN.

Wyszukiwany

jest

najmniejszy

element, a nast

pnie zamieniany jest miejscami z

element, a nast

pnie zamieniany jest miejscami z

ostatnim elementem przeszukiwanego podci

warto

ci. Kolejne wyszukiwanie prowadzone jest

warto

ci. Kolejne wyszukiwanie prowadzone jest

bez elementów, które zostały ju

uporz

dkowane.

bez elementów, które zostały ju

uporz

dkowane.

Algorytmy

–

Jędryczkowski

–

2005 r.

---

Algorytmy

–

Jędryczkowski

–

2005 r.

Komórka pomocnicza

Algorytmy

–

Jędryczkowski

–

2005 r.

Wyszukiwarka

Podobne podstrony:
ALGORYTM id 57461 Nieznany
algorytmika id 57568 Nieznany (2)
4 Klient algorytmy id 37672 Nieznany (2)
Algorytmy 2 id 57578 Nieznany
3 algorytmy id 33513 Nieznany (2)
Algorytmy1 id 57858 Nieznany
Algorytmy2 id 57859 Nieznany
AlgorytmyGenetyczne id 57864 Nieznany
JP SS 2 algorytmy id 228753 Nieznany
Algorytmy3 id 57861 Nieznany
ALGORYTM id 57461 Nieznany
algorytmika id 57568 Nieznany (2)
algorytmy sortujace id 57762 Nieznany
Algorytmy obliczen id 57749 Nieznany
algorytmy PKI Instrukcja id 577 Nieznany (2)
Algorytmy Genetyczne AG 3 id 61 Nieznany (2)
Algorytmy zadania id 51150 Nieznany (2)
algorytmy tekstowe id 57778 Nieznany (2)
3 3 BK Algorytmy parsingu id 34 Nieznany (2)

więcej podobnych podstron