No title

INFORMATIKA Dluhopisy (lohy z MO { kategorie P, 21. st)

; PAVEL T PFER

Matematicko-fyzikln fakulta UK, Praha

V dne nm pokraovn serilu o zajmavch programtorskch lohch z Matematick olympidy { kategorie P se zastavme u sout n lohy krajskho kola prv skonenho 57. ronku MO ( koln rok 2007/ 2008). V echny sout n lohy pro 57. ronk MO kategorie P navrhli organiztoi olympidy z Fakulty matematiky, fyziky a informatiky Univerzity Komenskho v Bratislav . Tato loha se zabv problmem ze ivota jak doshnout maximlnho zisku pi obchodovn s dluhopisy, mme-li dn poten kapitl. Uva ovan model obchodovn s dluhopisy je ov em oproti skutenosti znan zjednodu en, pedpokld nem nn kurzy a vnosnost jednotlivch obchodovanch dluhopis b hem celho sledovanho obdob. Zaneme jako obvykle pesnm zadnm sout n lohy: ???

Kleof nedvno zd dil po sv bohat tetice Anastzii hromadu pen z. Nev d l v ak co s nimi, a proto se rozhodl investovat je do dluhopis. Od vs si chce nechat poradit, jak by m l svou investici optimln spravovat. Matematika - fyzika - informatika 18 2008/2009

103

Pro jednoduchost budeme pedpokldat nsledujc skutenosti: { Ka d typ dluhopisu m svoji pevnou cenu, stejnou pi koupi i prodeji. { Ka d typ dluhopisu m pevn dan ron vnos, kter se vyplc v dy na konci roku. { Je mo n nakoupit libovoln mno stv ka dho typu dluhopisu. Uva ujme napklad nsledujc situaci: Banka nabz dva typy dluhopis: Dluhopisy za 4 000 korun s ronm vnosem 400 a dluhopisy za 3 000 korun s ronm vnosem 250. M-li Kleof 10 000 korun, nejlep , co s nimi m e ud lat, je koupit dva dluhopisy po 3 000 a jeden za 4 000, m zsk ron vnos 900 korun. Po dvou letech obdr Kleof dvakrt vnosy a bude mt celkov kapitl 11 800 korun. V tomto okam iku se mu vyplat jeden dluhopis za 3 000 korun prodat a msto n j si koupit dluhopis za 4 000. Po tetm roce bude jeho kapitl roven 12 850 korunm. Sout n loha: Napi te program, kter pete ze vstupu Kleof v poten kapitl, ceny a vnosy nabzench dluhopis a poet rok, na kter chce Kleof investovat, a spot, kolik nejvce pen z m e Kleof mt po uplynut danho potu rok. Formt vstupu: Na prvnm dku vstupu je jedno cel slo K (1 K 1 000 000), kter udv Kleof v poten kapitl. Na druhm dku je uveden poet typ nabzench dluhopis D (1 D 100). Na tetm dku je D dvojic celch sel ci a vi , kter pedstavuj ceny a vnosy jednotlivch dluhopis (0 < ci 109, 0 vi ci =10, ci je v dy nsobkem T=1000). Na poslednm dku vstupu je uveden poet rok R (1 R 40). asovou slo itost svho algoritmu vyjdete pomoc K, D, T a R. Navrhn te algoritmus, kter pro hodnoty K, D, T a R z v e uvedench rozsah bude co nejrychlej . Formt vstupu: Vstupem programu je jedin slo, kter uruje maximln hodnotu Kleof ova kapitlu po R letech obchodovn s dluhopisy. M ete pedpokldat, e se tato hodnota vejde do b n celoseln prom nn. ???

Problm si nejprve objasnme na n kolika ilustrujcch pkladech. Pedpokldejme vstup ve tvaru 104

Matematika - fyzika - informatika 18 2008/2009

10 000 2 4 000 400 4

3 000

poten kapitl poet dluhopis 250 ceny a vnosy jednotlivch dluhopis poet rok

Vstupem programu bude slo 14 050. Jedn se pesn o pklad ze zadn lohy, pouze prodlou en o jeden dal rok. Ve tvrtm roce bude Kleof vlastnit 3 dluhopisy po 4 000, m vyd l dal ch 1 200 korun. V druhm pkladu uva ujme vstup 100 000 3 103 000 9 001 47 000 7 83 000 100 31 Kleof koup jeden dluhopis za 83 000 korun. Tm za 30 let zsk 3 000 korun. Na posledn rok si konen m e koupit jeden dluhopis za 103 000. V poslednm roce tedy vyd l dal ch 9 001. Sprvnm vsledkem proto bude 112 001. A je t tet pklad se vstupem 100 000 3 103 000 9 001 47 000 7 83 000 100 37 Jedn se vlastn o pokraovn pedchozho pkladu, pouze investice je del o 6 let. Prb h bude stejn jako v pedchozm pkladu, navc po 36. roce Kleof dokoup jeden dluhopis za 47 000, tak e v poslednm roce zsk je t o 7 korun vce. Vsledkem je proto slo 166 014. Primitivn algoritmus e en lohy by mohl bt zalo en na slepm zkouen v ech mo nost, takov e en by ov em bylo znan neefektivn. Mnohem lep e en zskme s vyu itm techniky dynamickho programovn, s n jste se mohli seznmit ped rokem v 17. dlu na eho serilu !1] nebo teba v uebnici !2]. Nejprve si v imn te, e na konci ka dho roku po vyplacen ronch vnos m e Kleof v echny sv dluhopisy prodat a podle sv aktuln #nann situace se m e znovu rozhodnout, jak dluhopisy si pod do dal ho roku. To je mo n dky skutenosti, e v na loze neuva ujeme Matematika - fyzika - informatika 18 2008/2009

105

dn poplatky za nkup a prodej dluhopis. M eme tedy e it ka d rok investovn zcela samostatn a nezvisle na ostatnch letech. Nadle se proto omezme na otzku, jak nejvy ron vnos V!P] m eme nkupem dluhopis zskat, pokud mme na zatku roku k dispozici #nann prostedky ve v i P. Cel e en lohy potom bude vypadat tak, e na zatku prvnho roku nakoupme za poten kapitl K nejvhodn j m mo nm zpsobem dluhopisy, na konci roku se nm majetek zv o vnosy V!K] a do druhho roku zvolme novou co nejvhodn j investici vychzejc z na ich celkovch #nannch prostedk ve v i K+V!K]. Stejnm zpsobem postupujeme i v dal ch letech, popsan vpoet se tedy opakuje tolikrt, kolik rok chceme investovat. Jak tedy spotme pro jist #nann obnos P nejvy dosa iteln ron vnos V!P]? Za na ich P korun chceme koupit n kolik kus dluhopis ze znm nabdky D druh dluhopis s cenami ci a ronmi vnosy vi . Je nm pochopiteln jedno, v jakm poad je koupme, n kter dluhopis ale musme koupit jako prvn. Koupme-li nejdve j-t dluhopis, zskme z n j vnos vj a zstane nm je t P ; cj korun. Za ty nakoupme co nejvhodn ji dal dluhopisy, m vyd lme dal ch V!P ;cj ] korun. Celkov tedy doshneme ronho vnosu vj + V!P ;cj ]. Jeliko ale nevme, kter dluhopis bude nejvhodn j koupit jako prvn, vyzkou me v echny mo nosti a vybereme z nich tu, kter povede k nejvy mu vnosu. Dostvme tak vztah V!P] = maxfv1+ V!P ;c1 ], v2 + V!P ;c2 ], : : : , vD + V!P ;cD ] g Maximum bereme samozejm pouze pes ty dluhopisy, kter si m eme za P korun koupit, tzn. pro kter cj P. K vpotu V!P] podle uvedenho vztahu potebujeme znt hodnoty V!P ;c1 ], V!P ;c2 ], : : : , V!P ;cD ]. Ty by sice bylo mo n urovat rekurzivnm vpotem (volnm rekurzivn funkce pro men hodnoty argument), to by ale vedlo k velmi neefektivnmu e en, nebo& by se stejn hodnoty potaly opakovan mnohokrt. 'lohu proto vye me dynamickm programovnm, budeme postupovat odspodu od nejmen ch hodnot. Jist plat V!0]=0, dle spotme V!1], potom V!2], atd., dokud se nedostaneme k uren hodnoty V!P]. V echny spotan hodnoty si ukldme do pole V. Ka dou z hodnot jsme v dy spotali z pedchzejcch hodnot, kter jsme v tu chvli ji znali. 106


Musme se je t rozhodnout, kter v echny hodnoty V!P] si takto mme pedem spotat, tzn. nakolik m e vzrst Kleof v majetek. Podle zadn je vnos ka dho dluhopisu roven nejv e 10 % jeho ceny, za jeden rok tedy m e vzrst celkov Kleof v kapitl pi jakkoliv uva ovan investici nejv e o 10 %. Za R rok proto doshne hodnoty nejv e K1 1R. Z hlediska programov realizace algoritmu bude pro ns nejjednodu spotat si pedem do pole V v echny hodnoty V!P] a do tto meze, i kdy pro konkrtn vstupn data m e bt reln zhodnocen dluhopis hor a Kleof v kapitl nemus tto horn hranice doshnout. Jinou mo nost by bylo nepotat si hodnoty V!P] pedem, ale dopotvat je podle poteby v ka dm roce. V zadn lohy je tak stanoveno, e ceny v ech dluhopis jsou nsobkem T = 1 000. Pokud tedy m Kleof na zatku roku teba 14 947 korun, m e z nich pi sv investici v tomto roce vyu t pouze 14 000 korun. Vnosy i celkov kapitl musme sice potat po skonen ka dho roku s pesnost na koruny, ale pi rozhodovn, kter investice bude nejvhodn j , potebujeme znt hodnoty V!P] pouze pro nsobky T. Zbv odhadnout asovou a pam &ovou slo itost algoritmu. Nejprve budeme potat potebn hodnoty V!P], kterch je celkem K1 1R/T. Ka dou z nich spotme podle v e uvedenho vztahu v ase O(D), tak e celou tuto prvn st vpotu zvldneme v ase O(DK1 1R /T). Vlastn vpoet zhodnocen kapitlu je pak u velmi jednoduch, R-krt zopakujeme nav en majetku o pedem spotan vnos, co pedstavuje prci O(R). Tento as je zanedbateln v porovnn s odhadem O(DK1 1R/T) na celkovou asovou slo itost algoritmu. V programu budeme potebovat dv pole velikosti D na ulo en vstupnch dat { cen a vnos jednotlivch dluhopis. K vlastnmu vpotu nm pak u posta jedno jednorozm rn pole V, do kterho si ulo me pedem spotan maximln mo n zhodnocen kapitlu. Velikost tohoto pole m eme odhadnout potem ulo ench daj K1 1R/T. Uv me-li omezen ze zadn lohy K 1 000 000, R 40, T=1 000, vyjde nm potebn velikost pole men ne 50 000, tak e takov pole V m eme bez problmu pou t. program Dluhopisy const MAXD = 100 T = 1000

{maximln poet dluhopis} {nsobek ceny dluhopis}


107

MAXV = 50000

{maximln dosaiteln kapitl / T}

var cena, vynos: array1..MAXD] of longint {popis dluhopis} V: array0..MAXV] of longint {maximln ron v nosy} K: longint {poten kapitl} D: longint {poet dluhopis} R: longint {poet rok - dlka investice} P: longint {maximln dosaiteln kapitl / T} i, j: longint begin read(K, D) for i:=1 to D do begin read(cenai], vynosi]) cenai] := cenai] div T end read(R)

{ceny ulome v nsobcch T}

P := round(K * exp(R*ln(1.1)) / T) + 1 V0] := 0 for i:=1 to P do {investovan stka v nsobcch T} begin Vi] := 0 for j:=1 to D do {nabzen dluhopis} if i >= cenaj] then {lze ho koupit} if vynosj] + Vi-cenaj]] > Vi] then {vyplat se koupit} Vi] := vynosj] + Vi-cenaj]] end for i:=1 to R do K := K + VK div T] writeln(K) end.

108

{roky investovn} {maximln zhodnocen za jeden rok} {v sledn kapitl}


Literatura 1] Tpfer, P.: Spolen vybran podposloupnost ( lohy z MO { kategorie P, 17. st), MFI, ro. 17 (2007 { 2008), . 2. 2] Tpfer, P.: Algoritmy a programovac techniky, Prometheus, Praha 2007 (2. vydn). (Autorkou vodn ilustrace je Mgr. Jaroslava ermkov z Hlinska v echch.)

Matematika na internetu JI HTLE Prodovdeck fakulta UP, Olomouc

Internet je mohutnou a stle dynamicky se rozvjejc studnic informac, troufm si ci v eho druhu, a zasahujc do ka d oblasti. Sv msto na internetu m tak matematika. Najdeme zde strnky zkladnch a stednch kol, kde organizuj matematick krou ky, semine a projekty, strnky fakult a kateder vysokch kol a univerzit zabvajcch se matematikou, osobn strnky student a uitel matematiky, i lid, pro kter je matematika velkm zjmem a konkem. Na toto tma byl v MFI ped asem publikovn psp vek !1]. Proto e neustl rozvoj internetu stle pin na jedn stran vznik novch a novch strnek, ale tak i znik n kterch star ch strnek, klade si tento lnek za cl situaci zmapovat a upozornit na takov strnky na internetu, jejich obsahem jsou pev n tmata stedo kolsk matematiky a kter tedy mohou pomoci stedo kolskm uitelm matematiky pi jejich pprav na hodinu i v samotn vuce. Pitom mohou poslou it nejen jako zdroj informac, ale tak jako zdroj zajmavch nebo zbavnch loh, test, hek, nm t na vuku atd. Zam ujeme se na strnky v e tin resp. sloven tin , kde pi erpn informac odpad mo n jazykov barira tene a u ivatele internetu v jedn osob . (Odkazy na strnky zabvajc se matematikou v cizm jazyce jsou uvedeny v !1]. Konkrtn jsou to odkazy 11 { 15, kter jsou platn a tyto strnky v souasn dob funguj. Pidejme k nim je t jeden cizokrajn odkaz: mathworld.wolfram.com) Matematika - fyzika - informatika 18 2008/2009

109

1. Cifrikova matematika (www.matematika.webz.cz, www.matematika.tk). 2. Matematika polopat (matematika.havrlant.net). 3. E { matematika (www.e-matematika.cz). 4. Matematika online (www.aristoteles.cz/matematika/matematika.php). 5. Excellent Matematika (matematika.host.sk). 6. Matematika (matematika.wz.cz). 7. Matematika pro ka dho (www.maths.cz). 8. Zbavn matematika (www.tady.cz/zabavna.matematika). 9. Testpark.cz (www.testpark.cz/testy/matematika). 10. Cabri geometrie (www.pf.jcu.cz/cabri). Poznmka: V echny v e uveden strnky byly v dob psan tohoto lnku v provozu. V tabulce 1 je znzorn no, ke ktermu tmatu se na konkrtn strnce vyskytuje text nebo pklady.

Tab. 1 Zkladn poznatky z matematiky Rovnice a nerovnice Funkce + Goniometrie Planimetrie + Stereometrie + Analytick geometrie Kombinatorika, statistika, pravdpodobnost Posloupnosti a ady Komplexn sla Diferenciln a integrln poet

1

2

3

X X X X X X X X X X X X X X X X X

4

5

X X X X X

6

7

8

9

10

X X X X X X X X X X

X

1. Cifrikova matematika

(www.matematika.webz.cz, www.matematika.tk) Na strnkch zjemce nalezne teorii a e en pklady, oboj si m e ve v t in ppad sthnout ve formtech .doc, .pdf nebo .zip. Strnky 110


jsou rozd leny do kategori: algebra, matematick analza, ostatn, f)rum (dotazy a odpov di i nvody e en), hry (logick a dal online hry, online kalkulaka). Sm autor, student matematiky na pedagogick fakult , upozor*uje, e strnky nejsou bez chyb.

2. Matematika polopat (matematika.havrlant.net)

Strnka obsahuje matematick f)rum, kde u ivatel (nutnost registrace) mohou vkldat dotazy a odpov di+ douovn { nabdka a poptvka+ odkazy na strnky o matematice a anglitin , na IQ test+ a matematick tmata viz tabulka 1.

3. E { matematika (www.e-matematika.cz)

Tento portl se uchz o pze* matematik svm pzviskem nesnesiteln lehk matematika. Nabz texty, ukzkov e en pklady, pklady k procvien, psemky i tvrtletn prce k tmatm hlavn zkladnch a stednch kol, n kter zdarma, n kter za poplatek.

4. Matematika online

(www.aristoteles.cz/matematika/matematika.php) Web, na kterm najdete tak fyziku a chemii, obsahuje pev n uebn texty, pehledn tabulky, e en pklady i dal lohy, to v e nachystan k vytisknut. N kter materily i slu by jsou pstupn a po zaplacen poplatku.

5. Excellent Matematika (matematika.host.sk)

Na strnkch jsou umst ny vukov texty, tabulky a grafy, maturitn pklady, popis a odkazy na ti programy se vztahem k matematice, online v deck kalkulaka, slovnk pojm a odkazy na strnky. Bohu el v ak tyto strnky nebyly ji del dobu aktualizovny a dopln ny (obr. 1).

6. Matematika (matematika.wz.cz)

: : : strnka o matematice pro ty, co ji maj rdi, i pro ty druh Zajmav strnka, jej hlavn npln je n kolik skript pro online vpoty ke kvadratick funkci a z oblasti kombinatoriky, planimetrie a stereometrie. Dle zde nalezneme zajmav slovn lohy a matematick pohdky. Matematika - fyzika - informatika 18 2008/2009

111

;; ; ; Obr. 1

7. Matematika pro ka dho (www.maths.cz) Pom rn mlad a rozvjejc se strnky, kter maj ambice stt se rozshlmi a kvalitnmi. Je pravda, e je na nich stle co zlep ovat a dopl*ovat, co autor in. ten zde nalezne texty k tmatm, vzorce, e en pklady, dle hlavolamy (nev edn lohy) a online testy a cvien.

8. Z bavn matematika (www.tady.cz/zabavna.matematika) Tyto strnky dobe poslou jako zdroj zajmavch a zbavnch loh z oblasti algebry, aritmetiky a geometrie spolu se sprvnm vsledkem a e enm (obr. 2).

9. Testpark.cz (www.testpark.cz/testy/matematika) Portl zam en vhradn na online testy s vyhodnocenm poskytuje inspiraci na psemku z matematiky, i kdy zatm zde nalezneme testy sp pro ky zkladnch kol. 112


; ; ; ; Obr. 2

10. Cabri geometrie (www.pf.jcu.cz/cabri)

Velice p kn a pnosn strnky o programu Cabri geometrie a jejm vyu it pi vuce geometrie, ke kterm nen snad poteba dodvat vce. teni MFI se s tmto SW produktem ji vcekrt setkali, viz nap. !2], !3], !4]. Literatura 1] Sibravov, L.:: Stedokolsk matematika na Internetu. MFI, r. 13 (2003/2004), . 3, str. 167 { 178. 2] Vrba. A.:: Oivl geometrie. MFI, r. 10, (2000/2001), . 2, str. 105 { 117. 3] Luk , S.:: Rieenie kontruknch loh na stredov smernos pomocou Cabri geometrie. MFI, r. 15 (2005/2006), . 1, str. 47 { 57. 4] Vrba, A.:: Cabri vkroilo do tet dimenze. MFI, r. 17 (2007/2008), . 1, str. 52 { 56.


113

No title

Recommend Documents