BI-PA1 { Programov an a Algoritmizace I. Ladislav Vagner · PDF fileAlgoritmy BI-PA1 {...

AlgoritmyBI-PA1 – Programovanı a Algoritmizace I.

Ladislav Vagner

Katedra teoreticke informatikyFakulta informacnıch technologiı

CVUT v [email protected]

2., 4. a 5. rıjna 2017

Kontakt

mıstnost A–1233, KTI FIT,

e-mail: [email protected],

agenda: proseminare, Progtest.

L. Vagner, CVUT FIT Algoritmy, BI-PA1 2/35

Programovacı jazyky a styly

Imperativnı (proceduralnı) programovanı:

Pascal, strojovy kod, . . .

Funkcionalnı programovanı:

Haskell, Lisp, . . .

Logicke (deklarativnı) programovanı:

Prolog, SQL, XSLT, . . .

OO programovanı:

Eiffel, Objective C, Smalltalk, . . .

Kam patrı Java, C++, a C?


Programovacı jazyky a styly

Imperativnı (proceduralnı) programovanı:

Pascal, strojovy kod, . . .

Funkcionalnı programovanı:

Haskell, Lisp, . . .

Logicke (deklarativnı) programovanı:

Prolog, SQL, XSLT, . . .

OO programovanı:

Eiffel, Objective C, Smalltalk, . . .

Kam patrı Java, C++, a C?


Algoritmy

Vlastnosti algoritmu:

Hromadnost (univerzalnost).

Jednoznacnost (determinismus).

Poskytuje vysledky (resultativnost).

Konecnost.

Vstupy.

Vystupy.

Slozitost.

Zapis algoritmu:

textova podoba (pseudokod, programovacı jazyk),

graficka podoba (vyvojovy diagram – flow chart).


Algoritmy

Zakladnı elementy pri zapisu algoritmu:

vstupnı bod,

koncovy bod,

vetvenı,

prıkaz.

Odvozene:

smycky (= vetvenı + navrat),

I/O operace (= specialnı typ prıkazu),

vyvolanı jineho algoritmu (= specialnı typ prıkazu).


Algoritmy – vyvojove diagramy

Elementy vyvojoveho diagramu:

START

KONEC

Vstupní bod

Koncový bod

Podmínka (větvení)

Příkaz

I/O operace


Algoritmy – vyvojove diagramy

Prıklad: algoritmus nacte dve cısla a zobrazı vetsı z nich.

START

READ A,B

A > B

WRITE BWRITE A

END

+ -


Algoritmy – pseudokod

Prıklad: algoritmus nacte dve cısla a zobrazı vetsı z nich.

START

CTI A, B

POKUD A > B

ZOBRAZ A

JINAK

ZOBRAZ B

KONEC


Algoritmy – kvadraticka rovnice

Ukol: vymyslet a zapsat algoritmus, ktery dokaze vyresit zadanoukvadratickou rovnici.



START

CTI a, b, c

d := b * b - 4 * a * c

x1 := (-b + sqrt ( d )) / 2 / a

x2 := (-b - sqrt ( d )) / 2 / a

ZOBRAZ x1, x2

KONEC

Je tento algoritmus spravny?

Co se stane pro a = 0?Co se stane pro d < 0?



START

CTI a, b, c

d := b * b - 4 * a * c

x1 := (-b + sqrt ( d )) / 2 / a

x2 := (-b - sqrt ( d )) / 2 / a

ZOBRAZ x1, x2

KONEC

Je tento algoritmus spravny?Co se stane pro a = 0?

Co se stane pro d < 0?



START

CTI a, b, c

d := b * b - 4 * a * c

x1 := (-b + sqrt ( d )) / 2 / a

x2 := (-b - sqrt ( d )) / 2 / a

ZOBRAZ x1, x2

KONEC

Je tento algoritmus spravny?Co se stane pro a = 0?Co se stane pro d < 0?



START

CTI a, b, c

POKUD a = 0

ZOBRAZ "Neni kvadraticka rovnice"

KONEC

d := b * b - 4 * a * c

POKUD d < 0

ZOBRAZ "Neexistuje realne reseni"

KONEC

x1 := (-b + sqrt ( d )) / 2 / a

x2 := (-b - sqrt ( d )) / 2 / a

ZOBRAZ x1, x2

KONEC


Algoritmy – protiletecka obrana

Ukol: algoritmus pro rızenı obranne rakety urcı spravne nastavenınameru αd tak, aby raketa sestrelila nepratelskou strelu. Vıme, zeobranna strela letı rychlostı vd a odpalıme ji se zpozdenım t0.Nepratelskou strelu musıme zasahnout ve vzestupne fazi letu.Pokud to nelze splnit, algoritmus na to musı upozornit. Z radaru onepratelske strele vıme:

vzdalenost mısta odpalenı l ,

rozdıl nadmorskych vysek h,

namer nepratelske strely αe a

rychlost nepratelske strely ve .

αe

ve

αd

vd

l

h



Z fyzikalnıho popisu drahy strel zıskame nasledujıcı rovnice:

xe = l − vet cosαe

ye = h + vet sinαe −gt2

2xd = vd(t − t0) cosαd

yd = vd(t − t0) sinαd −g(t − t0)2

2

V okamziku stretu tx platı, ze xe = xd a ye = yd :

tx =l + t0vd cosαd

ve cosαe + vd cosαd=

2t0vd sinαd + 2h + gt20

2vd sinαd + 2gt0 − 2ve sinαe



Po upravach vyjde:

αd1 = 2 arctanB +√A2 + B2 − C 2

A− C

αd2 = 2 arctanB −√A2 + B2 − C 2

A− C

Kde:

A = gt20vd − 2t0vdve sinαe − 2hvd

B = 2lvd − 2t0vdve cosαe

C = 2lgt0 − 2lve sinαe − 2hve cosαe − gt20ve cosαe



Derivacı urcıme, ze nepratelska strela dosahne vrcholu stoupanı vcase:

tmax =ve sinαe

g

Pro vypoctene hodnoty uhlu αd musıme vypocıtat okamzik stretu:

tx1 =l + t0vd cosαd1

ve cosαe + vd cosαd1

tx2 =l + t0vd cosαd2

ve cosαe + vd cosαd2

Strelu lze sestrelit pouze s nastavenım, pro ktere je tx ≤ tmax .



START

CTI l, h, t0, ve, vd, ae

tmax := ve * sin(ae) / g

A := g*t0*t0*vd - 2*t0*vd*ve*sin(ae) - 2*h*vd

B := 2*l*vd - 2*t0*vd*ve*cos(ae)

C := 2*l*g*t0 - 2*l*ve*sin(ae) - 2*h*ve*cos(ae) - g*t0*t0*ve*cos(ae)

D := A*A + B*B - C*C

POKUD D < 0

ZOBRAZ "Nelze zasahnout"

KONEC

tmax := ve * sin(ae) / g

ad1 := 2*atan2( A-C, B + sqrt(D) )

tx1 := (l + t0*vd*cos(ad1)) / (ve*cos(ae) + vd*cos(ad1))

POKUD tx1 <= tmax

ZOBRAZ "Namer ", ad1

KONEC

ad2 := 2*atan2( A-C, B - sqrt(D) )

tx2 := (l + t0*vd*cos(ad2)) / (ve*cos(ae) + vd*cos(ad2))

POKUD tx2 <= tmax

ZOBRAZ "Namer ", ad2

KONEC

ZOBRAZ "Nelze zasahnout"

KONEC


Algoritmy – minimum, maximum a prostrednı cıslo

Ukol: pro tri zadana cısla a, b a c (navzajem ruzna) urcitmaximum, minimum a prostrednı cıslo.



START

CTI a, b, c

POKUD a > b

POKUD a > c

max := a

POKUD b > c

mid := b

min := c

JINAK

mid := c

min := b

JINAK

max := c

mid := a

min := b

JINAK

POKUD b > c

max := b

POKUD a > c

mid := a

min := c

JINAK

mid := c

min := a

JINAK

max := c

mid := b

min := a

ZOBRAZ "Maximum", max

ZOBRAZ "Prostredni", mid

ZOBRAZ "Minimum", min

KONEC



START

CTI a, b, c

max := a

POKUD b > max

max := b

POKUD c > max

max := c

min := a

POKUD b < min

min := b

POKUD c < min

min := c

mid := a + b + c - min - max


ZOBRAZ "Prostredni", mid

ZOBRAZ "Minimum", min

KONEC


Algoritmy – spolecny delitel a nasobek

Ukol: zapsat algoritmus, ktery pro zadana prirozena cısla a a b urcıjejich nejvetsı spolecny delitel a nejmensı spolecny nasobek.



START

CTI a, b

prod := a * b

DOKUD a <> b

POKUD a > b

a := a - b

JINAK

b := b - a

gcd := a

lcm := prod / gcd

ZOBRAZ "Nejvetsi spolecny delitel", gcd

ZOBRAZ "Nejmensi spolecny nasobek", lcm

KONEC

Je tento algoritmus efektivnı?

Pro 60 a 36.Pro 1001 a 1.



START

CTI a, b

prod := a * b

DOKUD a <> b

POKUD a > b

a := a - b

JINAK

b := b - a

gcd := a

lcm := prod / gcd



KONEC

Je tento algoritmus efektivnı?Pro 60 a 36.

Pro 1001 a 1.



START

CTI a, b

prod := a * b

DOKUD a <> b

POKUD a > b

a := a - b

JINAK

b := b - a

gcd := a

lcm := prod / gcd



KONEC

Je tento algoritmus efektivnı?Pro 60 a 36.Pro 1001 a 1.



START

CTI a, b

prod := a * b

POKUD a < b

tmp := a

a := b

b := tmp

DOKUD b > 0

tmp := a mod b

a := b

b := tmp

gcd := a

lcm := prod / gcd



KONEC


Algoritmy – maximum v posloupnosti

Ukol: zapsat algoritmus, ktery pro zadanou posloupnost nnavzajem ruznych celych cısel najde maximum.



START

CTI n

max := 0

DOKUD n > 0

CTI x

POKUD x > max

max := x

n := n - 1


KONEC

Je algoritmus spravny?

Ne pro n = 3 a vstup: -1, -2, -3.



START

CTI n

max := 0

DOKUD n > 0

CTI x

POKUD x > max

max := x

n := n - 1


KONEC

Je algoritmus spravny?Ne pro n = 3 a vstup: -1, -2, -3.



START

CTI n

POKUD n <= 0

ZOBRAZ "Chyba ..."

KONEC

CTI max

n := n - 1

DOKUD n > 0

CTI x

POKUD x > max

max := x

n := n - 1


KONEC


Algoritmy – druhe nejvetsı cıslo

Ukol: zapsat algoritmus, ktery pro zadanou posloupnost nnavzajem ruznych celych cısel najde druhe nejvetsı cıslo.



START

CTI n

POKUD n < 2

ZOBRAZ "Chyba ..."

KONEC

CTI m1, m2

POKUD m1 < m2

tmp := m1

m1 := m2

m2 := tmp

n := n - 2

DOKUD n > 0

CTI x

POKUD x > m1

m2 := m1

m1 := x

n := n - 1

ZOBRAZ "Druhe maximum", m2

KONEC


Ne pro n = 3 a vstup: 1, 3, 2.



START

CTI n

POKUD n < 2

ZOBRAZ "Chyba ..."

KONEC

CTI m1, m2

POKUD m1 < m2

tmp := m1

m1 := m2

m2 := tmp

n := n - 2

DOKUD n > 0

CTI x

POKUD x > m1

m2 := m1

m1 := x

n := n - 1


KONEC

Je algoritmus spravny?Ne pro n = 3 a vstup: 1, 3, 2.



START

CTI n

POKUD n < 2

ZOBRAZ "Chyba ..."

KONEC

CTI m1, m2

POKUD m1 < m2

tmp := m1

m1 := m2

m2 := tmp

n := n - 2

DOKUD n > 0

CTI x

POKUD x > m1

m2 := m1

m1 := x

JINAK

POKUD x > m2

m2 := x

n := n - 1


KONEC


Ano.



START

CTI n

POKUD n < 2

ZOBRAZ "Chyba ..."

KONEC

CTI m1, m2

POKUD m1 < m2

tmp := m1

m1 := m2

m2 := tmp

n := n - 2

DOKUD n > 0

CTI x

POKUD x > m1

m2 := m1

m1 := x

JINAK

POKUD x > m2

m2 := x

n := n - 1


KONEC

Je algoritmus spravny?Ano.


Algoritmy – faktorizace

Ukol: zapsat algoritmus, ktery pro zadane prirozene cıslo n urcıjeho prvocıselny rozklad (faktorizaci).

Napr. pro n = 720 je faktorizace:

720 = 5 ∗ 2 ∗ 2 ∗ 2 ∗ 2 ∗ 3 ∗ 3



START

CTI n

i := 2

DOKUD i < n

POKUD n mod i = 0

ZOBRAZ i

i := i + 1

KONEC

Je algoritmus spravne?

Ne, zobrazı vsechny delitele, ne pouze prvocısla.



START

CTI n

i := 2

DOKUD i < n

POKUD n mod i = 0

ZOBRAZ i

i := i + 1

KONEC

Je algoritmus spravne?Ne, zobrazı vsechny delitele, ne pouze prvocısla.



START

CTI n

i := 2

DOKUD i < n

POKUD n mod i = 0

POKUD isprime ( i )

ZOBRAZ i

i := i + 1

KONEC


Ne, zobrazı prvocıselne faktory, ale pouze jednou.



START

CTI n

i := 2

DOKUD i < n

POKUD n mod i = 0

POKUD isprime ( i )

ZOBRAZ i

i := i + 1

KONEC

Je algoritmus spravne?Ne, zobrazı prvocıselne faktory, ale pouze jednou.



START

CTI n

i := 2

DOKUD i <= n

POKUD n mod i = 0

POKUD isprime ( i )

ZOBRAZ i

n := n / i

JINAK

i := i + 1

KONEC


Ano, pouze pro n = 1 nezobrazı nic.Je velmi neefektivnı.



START

CTI n

i := 2

DOKUD i <= n

POKUD n mod i = 0

POKUD isprime ( i )

ZOBRAZ i

n := n / i

JINAK

i := i + 1

KONEC

Je algoritmus spravne?Ano, pouze pro n = 1 nezobrazı nic.

Je velmi neefektivnı.



START

CTI n

i := 2

DOKUD i <= n

POKUD n mod i = 0

POKUD isprime ( i )

ZOBRAZ i

n := n / i

JINAK

i := i + 1

KONEC

Je algoritmus spravne?Ano, pouze pro n = 1 nezobrazı nic.Je velmi neefektivnı.



START

CTI n

i := 2

DOKUD i <= n

POKUD n mod i = 0

ZOBRAZ i

n := n / i

JINAK

i := i + 1

KONEC


Ano, pouze pro n = 1 nezobrazı nic.Je stale neefektivnı.



START

CTI n

i := 2

DOKUD i <= n

POKUD n mod i = 0

ZOBRAZ i

n := n / i

JINAK

i := i + 1

KONEC

Je algoritmus spravne?Ano, pouze pro n = 1 nezobrazı nic.

Je stale neefektivnı.



START

CTI n

i := 2

DOKUD i <= n

POKUD n mod i = 0

ZOBRAZ i

n := n / i

JINAK

i := i + 1

KONEC

Je algoritmus spravne?Ano, pouze pro n = 1 nezobrazı nic.Je stale neefektivnı.



START

CTI n

factorize ( n )

KONEC

factorize ( n ):

START

i := sqrt ( n )

DOKUD i >= 2

POKUD n mod i = 0

factorize ( i )

factorize ( n / i )

KONEC

i := i - 1

ZOBRAZ n

KONEC


Dotazy

Dotazy . . .

Dekuji za pozornost.


Date post:	06-Feb-2018
Category:	Documents
Upload:	phamlien
View:	228 times
Download:	2 times

BI-PA1 { Programov an a Algoritmizace I. Ladislav Vagner · PDF fileAlgoritmy BI-PA1 {...

Documents