Algoritmy BI-PA1 – Programov´an´ı a Algoritmizace I.
Ladislav Vagner Katedra teoretick´ e informatiky Fakulta informaˇ cn´ıch technologi´ı ˇ CVUT v Praze
[email protected]
3. ˇr´ıjna 2016 a 4. ˇr´ıjna 2016
Kontakt m´ıstnost A–1233, KTI FIT, e-mail:
[email protected], agenda: prosemin´aˇre, Progtest.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
2/35
Programovac´ı jazyky a styly Imperativn´ı (procedur´aln´ı) programov´an´ı: Pascal, strojov´y k´ od, . . .
Funkcion´aln´ı programov´an´ı: Haskell, Lisp, . . .
Logick´e (deklarativn´ı) programov´an´ı: Prolog, SQL, XSLT, . . .
OO programov´an´ı: Eiffel, Objective C, Smalltalk, . . .
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
3/35
Programovac´ı jazyky a styly Imperativn´ı (procedur´aln´ı) programov´an´ı: Pascal, strojov´y k´ od, . . .
Funkcion´aln´ı programov´an´ı: Haskell, Lisp, . . .
Logick´e (deklarativn´ı) programov´an´ı: Prolog, SQL, XSLT, . . .
OO programov´an´ı: Eiffel, Objective C, Smalltalk, . . .
Kam patˇr´ı Java, C++, a C?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
3/35
Algoritmy Vlastnosti algoritmu: Hromadnost (univerz´alnost). Jednoznaˇcnost (determinismus). Poskytuje v´ysledky (resultativnost). Koneˇcnost. Vstupy. V´ystupy. Sloˇzitost. Z´ apis algoritmu: textov´a podoba (pseudok´ od, programovac´ı jazyk), grafick´a podoba (v´yvojov´y diagram – flow chart).
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
4/35
Algoritmy Z´akladn´ı elementy pˇri z´apisu algoritmu: vstupn´ı bod, koncov´y bod, vˇetven´ı, pˇr´ıkaz. Odvozen´e: smyˇcky (= vˇetven´ı + n´avrat), I/O operace (= speci´aln´ı typ pˇr´ıkazu), vyvol´an´ı jin´eho algoritmu (= speci´aln´ı typ pˇr´ıkazu).
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
5/35
Algoritmy – v´yvojov´e diagramy Elementy v´yvojov´eho diagramu:
Vstupní bod
START
Koncový bod
KONEC
Podmínka (větvení)
Příkaz I/O operace ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
6/35
Algoritmy – v´yvojov´e diagramy Pˇr´ıklad: algoritmus naˇcte dvˇe ˇc´ısla a zobraz´ı vˇetˇs´ı z nich.
START READ A,B
+
A>B
WRITE A
-
WRITE B
END
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
7/35
Algoritmy – pseudok´od Pˇr´ıklad: algoritmus naˇcte dvˇe ˇc´ısla a zobraz´ı vˇetˇs´ı z nich. START ˇ CTI A, B POKUD A > B ZOBRAZ A JINAK ZOBRAZ B KONEC
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
8/35
Algoritmy – kvadratick´a rovnice ´ Ukol: vymyslet a zapsat algoritmus, kter´y dok´aˇze vyˇreˇsit zadanou kvadratickou rovnici.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
9/35
Algoritmy – kvadratick´a rovnice 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 spr´avn´y?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
10/35
Algoritmy – kvadratick´a rovnice 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 spr´avn´y? Co se stane pro a = 0?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
10/35
Algoritmy – kvadratick´a rovnice 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 spr´avn´y? Co se stane pro a = 0? Co se stane pro d < 0?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
10/35
Algoritmy – kvadratick´a rovnice 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
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
11/35
Algoritmy – protileteck´a obrana ´ Ukol: algoritmus pro ˇr´ızen´ı obrann´e rakety urˇc´ı spr´avn´e nastaven´ı n´amˇeru αd tak, aby raketa sestˇrelila nepˇr´atelskou stˇrelu. V´ıme, ˇze obrann´a stˇrela let´ı rychlost´ı vd a odp´al´ıme ji se zpoˇzdˇen´ım t0 . Nepˇr´atelskou stˇrelu mus´ıme zas´ahnout ve vzestupn´e f´azi letu. Pokud to nelze splnit, algoritmus na to mus´ı upozornit. Z radaru o nepˇr´atelsk´e stˇrele v´ıme: vzd´alenost m´ısta odp´alen´ı l, rozd´ıl nadmoˇrsk´ych v´yˇsek h, n´amˇer nepˇr´atelsk´e stˇrely αe a rychlost nepˇr´atelsk´e stˇrely ve .
ve
vd αe αd ˇ L. Vagner, CVUT FIT
h l
Algoritmy, BI-PA1
12/35
Algoritmy – protileteck´a obrana Z fyzik´aln´ıho popisu dr´ahy stˇrel z´ısk´ame n´asleduj´ıc´ı rovnice:
xe
= l − ve t cos αe
ye
= h + ve t sin αe −
xd
= vd (t − t0 ) cos αd
yd
= vd (t − t0 ) sin αd −
gt 2 2 g (t − t0 )2 2
V okamˇziku stˇretu tx plat´ı, ˇze xe = xd a ye = yd :
tx =
ˇ L. Vagner, CVUT FIT
l + t0 vd cos αd 2t0 vd sin αd + 2h + gt02 = ve cos αe + vd cos αd 2vd sin αd + 2gt0 − 2ve sin αe Algoritmy, BI-PA1
13/35
Algoritmy – protileteck´a obrana Po u ´prav´ach vyjde:
αd2
√
A2 + B 2 − C 2 A−C √ B − A2 + B 2 − C 2 = 2 arctan A−C
αd1 = 2 arctan
B+
Kde: A = gt02 vd − 2t0 vd ve sin αe − 2hvd B = 2lvd − 2t0 vd ve cos αe C
ˇ L. Vagner, CVUT FIT
= 2lgt0 − 2lve sin αe − 2hve cos αe − gt02 ve cos αe
Algoritmy, BI-PA1
14/35
Algoritmy – protileteck´a obrana Derivac´ı urˇc´ıme, ˇze nepˇr´atelsk´a stˇrela dos´ahne vrcholu stoup´an´ı v ˇcase: ve sin αe tmax = g Pro vypoˇcten´e hodnoty u ´hlu αd mus´ıme vypoˇc´ıtat okamˇzik stˇretu:
tx1 = tx2 =
l + t0 vd cos αd1 ve cos αe + vd cos αd1 l + t0 vd cos αd2 ve cos αe + vd cos αd2
Stˇrelu lze sestˇrelit pouze s nastaven´ım, pro kter´e je tx ≤ tmax .
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
15/35
Algoritmy – protileteck´a obrana 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 ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
16/35
Algoritmy – minimum, maximum a prostˇredn´ı ˇc´ıslo ´ Ukol: pro tˇri zadan´a ˇc´ısla a, b a c (navz´ajem r˚ uzn´a) urˇcit maximum, minimum a prostˇredn´ı ˇc´ıslo.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
17/35
Algoritmy – minimum, maximum a prostˇredn´ı ˇ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 ˇ L. Vagner, CVUT FIT
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 Algoritmy, BI-PA1
18/35
Algoritmy – minimum, maximum a prostˇredn´ı ˇc´ıslo 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 "Maximum", max ZOBRAZ "Prostredni", mid ZOBRAZ "Minimum", min KONEC ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
19/35
Algoritmy – spoleˇcn´y dˇelitel a n´asobek ´ Ukol: zapsat algoritmus, kter´y pro zadan´a pˇrirozen´a ˇc´ısla a a b urˇc´ı jejich nejvˇetˇs´ı spoleˇcn´y dˇelitel a nejmenˇs´ı spoleˇcn´y n´asobek.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
20/35
Algoritmy – spoleˇcn´y dˇelitel a n´asobek 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´ı?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
21/35
Algoritmy – spoleˇcn´y dˇelitel a n´asobek 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. ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
21/35
Algoritmy – spoleˇcn´y dˇelitel a n´asobek 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. ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
21/35
Algoritmy – spoleˇcn´y dˇelitel a n´asobek 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 ZOBRAZ "Nejvetsi spolecny delitel", gcd ZOBRAZ "Nejmensi spolecny nasobek", lcm KONEC ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
22/35
Algoritmy – maximum v posloupnosti ´ Ukol: zapsat algoritmus, kter´y pro zadanou posloupnost n navz´ajem r˚ uzn´ych cel´ych ˇc´ısel najde maximum.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
23/35
Algoritmy – maximum v posloupnosti START ˇ CTI n max := 0 DOKUD n > 0 ˇ CTI x POKUD x > max max := x n := n - 1 ZOBRAZ "Maximum", max KONEC
Je algoritmus spr´avn´y?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
24/35
Algoritmy – maximum v posloupnosti START ˇ CTI n max := 0 DOKUD n > 0 ˇ CTI x POKUD x > max max := x n := n - 1 ZOBRAZ "Maximum", max KONEC
Je algoritmus spr´avn´y? Ne pro n = 3 a vstup: -1, -2, -3.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
24/35
Algoritmy – maximum v posloupnosti 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 ZOBRAZ "Maximum", max KONEC
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
25/35
Algoritmy – druh´e nejvˇetˇs´ı ˇc´ıslo ´ Ukol: zapsat algoritmus, kter´y pro zadanou posloupnost n navz´ajem r˚ uzn´ych cel´ych ˇc´ısel najde druh´e nejvˇetˇs´ı ˇc´ıslo.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
26/35
Algoritmy – druh´e nejvˇetˇs´ı ˇ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
Je algoritmus spr´avn´y?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
27/35
Algoritmy – druh´e nejvˇetˇs´ı ˇ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
Je algoritmus spr´avn´y? Ne pro n = 3 a vstup: 1, 3, 2.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
27/35
Algoritmy – druh´e nejvˇetˇs´ı ˇ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 JINAK POKUD x > m2 m2 := x n := n - 1 ZOBRAZ "Druhe maximum", m2 KONEC
Je algoritmus spr´avn´y?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
28/35
Algoritmy – druh´e nejvˇetˇs´ı ˇ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 JINAK POKUD x > m2 m2 := x n := n - 1 ZOBRAZ "Druhe maximum", m2 KONEC
Je algoritmus spr´avn´y? Ano.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
28/35
Algoritmy – faktorizace ´ Ukol: zapsat algoritmus, kter´y pro zadan´e pˇrirozen´e ˇc´ıslo n urˇc´ı jeho prvoˇc´ıseln´y rozklad (faktorizaci). Napˇr. pro n = 720 je faktorizace: 720 = 5 ∗ 2 ∗ 2 ∗ 2 ∗ 2 ∗ 3 ∗ 3
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
29/35
Algoritmy – faktorizace START ˇ CTI n i := 2 DOKUD i < n POKUD n mod i = 0 ZOBRAZ i i := i + 1 KONEC
Je algoritmus spr´avnˇe?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
30/35
Algoritmy – faktorizace START ˇ CTI n i := 2 DOKUD i < n POKUD n mod i = 0 ZOBRAZ i i := i + 1 KONEC
Je algoritmus spr´avnˇe? Ne, zobraz´ı vˇsechny dˇelitele, ne pouze prvoˇc´ısla.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
30/35
Algoritmy – faktorizace START ˇ CTI n i := 2 DOKUD i < n POKUD n mod i = 0 POKUD isprime ( i ) ZOBRAZ i i := i + 1 KONEC
Je algoritmus spr´avnˇe?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
31/35
Algoritmy – faktorizace START ˇ CTI n i := 2 DOKUD i < n POKUD n mod i = 0 POKUD isprime ( i ) ZOBRAZ i i := i + 1 KONEC
Je algoritmus spr´avnˇe? Ne, zobraz´ı prvoˇc´ıseln´e faktory, ale pouze jednou.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
31/35
Algoritmy – faktorizace 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 spr´avnˇe?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
32/35
Algoritmy – faktorizace 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 spr´avnˇe? Ano, pouze pro n = 1 nezobraz´ı nic.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
32/35
Algoritmy – faktorizace 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 spr´avnˇe? Ano, pouze pro n = 1 nezobraz´ı nic. Je velmi neefektivn´ı.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
32/35
Algoritmy – faktorizace 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 spr´avnˇe?
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
33/35
Algoritmy – faktorizace 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 spr´avnˇe? Ano, pouze pro n = 1 nezobraz´ı nic.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
33/35
Algoritmy – faktorizace 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 spr´avnˇe? Ano, pouze pro n = 1 nezobraz´ı nic. Je st´ale neefektivn´ı.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
33/35
Algoritmy – faktorizace START ˇ CTI n factorize ( n ) KONEC factorize ( n START i := sqrt ( n DOKUD i >= 2 POKUD n mod factorize factorize KONEC i := i - 1 ZOBRAZ n KONEC ˇ L. Vagner, CVUT FIT
): ) i = 0 ( i ) ( n / i )
Algoritmy, BI-PA1
34/35
Dotazy
Dotazy . . . Dˇekuji za pozornost.
ˇ L. Vagner, CVUT FIT
Algoritmy, BI-PA1
35/35
