INFORMATIKA Vlak (lohy z MO { kategorie P, 27. st)
;
PAVEL T PFER Matematicko-fyzikln fakulta UK, Praha
Ned vno jsme si v l nku 1] uk zali, jak lze v zadan posloupnosti sel urit dlku co nejdel ho souvislho symetrickho seku, tzv. palindromu. Pro e en tto lohy jsme na li p ekvapiv efektivn e en s line rn asovou sloitost. Tentokr t se budeme v novat na pohled velmi podobnmu, ale o n co obtn j mu kolu: V zadan posloupnosti sel chceme urit dlku co nejdel vybran podposloupnosti, kter je palindromem. P ipomeme, e vybran podposloupnost je tvo ena n ktermi prvky pvodn posloupnosti, p iem mus zstat zachov no jejich vz jemn po ad. loha zaloen na e en uvedenho problmu byla zad na v krajskm kole 60. ronku MO ( koln rok 2010/2011) { kategorie P. Nejprve se sezn mme s plnm zad nm, kter si pro pot eby na eho l nku vhodn zkr tme a upravme, ani bychom tm ov em zm nili smysl pvodn lohy.
Sout n loha
Na vstupu dostanete posloupnost psmen. Kad z t chto psmen p edstavuje jeden vagn vlaku. Rzn psmena odli uj rzn typy vagn. Vstupem programu bude vpis pozic vagn (psmen), kter mus bt 38
Matematika - fyzika - informatika 21 2011/2012
odstran ny, aby byl vsledn vlak (posloupnost psmen) po jejich odstran n stejn p i ten zep edu i zezadu (tedy aby vsledn et zec psmen byl palindromem). Pokud existuje vce monost, nalezn te a vypi te tu, kde je t eba odstranit nejmen mon poet vagn. Pokud je takovch monost vce, mete vypsat jednu libovolnou z nich.
Formt vstupu
Vstup programu je tvo en dv ma dky. Prvn dek obsahuje jedno cel slo N (1 N 50 000), kter uruje pvodn poet vagn vlaku. Druh dek obsahuje posloupnost N znak, kter popisuj jednotliv typy vagn.
Formt vstupu
Vstup programu je tvo en dv ma dky. Prvn obsahuje jedin slo K (0 K N ; 1), kter ud v , kolik vagn je pot eba z vlaku odstranit, aby vlak vypadal stejn z obou sm r. Druh dek obsahuje K rznch sel z rozmez od 1 do N urujcch po adov sla t ch vagn, kter maj bt z vlaku odstran ny. Pokud je posloupnost znak zadan na vstupu stejn p i ten zep edu i zezadu, pak na prvn dek vypi te slo 0 a druh dek zstane pr zdn. ???
Pklady: Vstup: 6 ABCDBA Vstup: 1 3 Odstran nm t etho psmene vznikne vlak s vagny ABDBA. Jinm spr vnm e enm je odstranit tvrt psmeno, kdy vznikne vlak s vagny ABCBA. Vstup: 7 ABECEDA Matematika - fyzika - informatika 21 2011/2012
39
Vstup: 2 26 Odstran nm druhho a estho psmene vznikne vlak s vagny AECEA. Vstup: 7 ABECADA Vstup: 4 3467 Odstran nm t etho, tvrtho, estho a sedmho psmene vznikne vlak s vagny ABA. V tomto p pad existuje vce rznch optim lnch e en. ???
Problematice vybranch podposloupnost jsme se v na em seri lu loh z MO kategorie P v novali v minulosti ji vcekr t, v posledn dob nap klad v l ncch 2] a 3]. Kadou z t chto loh bylo mon e it trivi lnm zpsobem zkou enm v ech monch vybranch podposloupnost, kterch je v ak exponenci ln mnoho a takov e en je tud velmi neefektivn. Naproti tomu se n m zatm vdy poda ilo nalzt efektivn e en zaloen na my lence dynamickho programov n. Stejn tomu bude i tentokr t. Zadan vlak V je tvo en vagny a1 a2 : : : a . Jako "podvlak# V si ozname jeho souvislou st tvo enou vagny a , a +1 : : : a . Budeme zkoumat, jak nalzt optim ln e en na lohy pro urit podvlak, kdy u zn me e en pro v echny podvlaky krat . Zajm n s tedy, jakou maxim ln symetrickou podposloupnost je mon vybrat z podvlaku V . Jestlie a = a , pak meme p edpokl dat, e jsou oba tyto krajn vagny za azeny v optim lnm e en pro podvlak V a mezi nimi se nach z optim ln e en o dva vagny krat ho podvlaku V +1 ;1 . Pokud neplat a = a , nemohou bt oba tyto vagny z rove za azeny v e en lohy pro V . V takovm p pad je tedy optim ln e en pro podvlak V rovno bu% optim lnmu e en pro V ;1 , nebo optim lnmu e en pro V +1 (podle toho, kter z nich bude vhodn j ). Vidme tedy, e e en pro kad podvlak V dok eme snadno spotat v konstantnm ase, pokud ji zn me e en pro podvlaky o jeden a o dva vagny krat . Vy e en zadan lohy dynamickm programov nm je p mou implementac pr v popsan my lenky. Zaneme od sek dlky 1, kter jsou N
i j
i
i
j
i j
i
j
i j
i
i
j
j
i j
i j
i j
i
j
i j
40
Matematika - fyzika - informatika 21 2011/2012
tvo eny jedinm vagnem a jsou tedy z ejm v echny symetrick. &e en v ech sek dlky 2 je rovn trivi ln { je ureno tm, zda jsou oba po sob jdouc vagny vlaku stejn, nebo ne. D le postupn pot me e en pro v echny seky dlky 3, 4, 5, atd., a nakonec najdeme e en pro cel vlak dlky N . Poet v ech postupn e ench souvislch sek (tzn. podvlak) je N + (N ; 1) + (N ; 2) + : : : + 1, tedy dov N 2 , kad e en urme v e uvedenm postupem v konstantnm ase. Algoritmus m tedy kvadratickou asovou sloitost vzhledem k dlce posloupnosti N . Pokud bude na m kolem urit pouze dlku maxim ln vybran symetrick podposloupnosti (resp. minim ln poet vagn, kter je t eba z vlaku vypustit, aby byl vsledn vlak symetrick), jsme v tuto chvli s e enm hotovi a meme si p edvst, jak by ho bylo mon naprogramovat. V n sledujc programov uk zce postupn pot me hodnoty prvk dvourozm rnho pole V tak, e slo V i j ] p edstavuje dlku maxim ln symetrick podposloupnosti vybran z seku a , a +1 : : : a . Hodnoty ukl dan do pole V pot me v po ad podle rostouc dlky seku. Jako posledn se spot slo V 1 N ], kter uruje dlku vslednho upravenho vlaku, tzn. hledan e en. Jeliko v loze poadujeme vypsat nikoliv dlku vslednho vlaku, ale minim ln poet vypu t nch vagn, program vyp e na vstup daj N ; V 1 N ]. i
i
j
program Vlak_1 {uren dlky maximln symetrick vybran podposloupnosti} const MaxN = 50000 var A: array 1..MaxN] of char {zadan posloupnost = vlak} V: array 1..MaxN, 1..MaxN] of integer {dlky max. symetrickch vybranch podposloupnost} N: integer {dlka posloupnosti} i, j, Delka: integer {vymezen rozsahu a dlka zvolenho seku posloupnosti} begin readln(N) for i:=1 to N do read(A i]) for i:=2 to N do V i,i-1]:=0
Matematika - fyzika - informatika 21 2011/2012
{dlka posloupnosti} {prvky posloupnosti} {przdn sek}
41
for i:=1 to N do V i,i]:=1 for Delka:=2 to N do for i:=1 to N-Delka+1 do begin j:=i+Delka-1 if A i] = A j] then V i,j]:=V i+1,j-1]+2 else if V i+1,j] > V i,j-1] then V i,j]:=V i+1,j] else V i,j]:=V i,j-1] end
{jednoprvkov sek} {dlka seku} {zatek seku} {konec seku}
{V 1,N] je dlka maximln vybran symetrick podposloupnosti} writeln(N-V 1,N]) {minimln poet vyputnch znak} end.
Tato jednoduch implementace vyuv pam ( kvadratick velikosti (vzhledem k N ). Ve skutenosti ale vystame dokonce s pam t line rn. Nemusme si toti b hem vpotu st le pamatovat v ech a N 2 d ve spotanch hodnot V i j ] pro seky krat dlky, k vy e en uritho podvlaku n m p ece sta zn t pouze e en pro podvlaky krat o jeden nebo o dva vagny. Budeme si tedy udrovat v pam ti pouze spotan e en vdy pro posledn dv dlky sek a na jejich z klad spot me e en pro seky bezprost edn n sledujc dlky. Poet v ech hodnot V i j ] uloench v jednom okamiku vpotu v pam ti bude tedy jist vdy men ne 3N . V na pvodn loze z MO m me v ak za kol urit nejen minim ln poet, ale tak seznam sel t ch vagn, kter je t eba z vlaku vypustit. &e en bude proto t eba je t doplnit o evidenci vypu t nch vagn. S line rn pam t pak ji nevystame a budeme pot ebovat pam ( kvadratick velikosti. Do programu p id me pole X , jeho hodnoty X i j ] budeme potat soub n s vpotem hodnot V i j ]. )slo X i j ] ud v po adov slo jednoho vagnu, kter je t eba vypustit z seku vlaku a , a +1 : : : a , abychom postupn zskali maxim ln vybranou symetrickou podposloupnost dlky V i j ]. Toto pole si musme uchov vat cel a na jeho i
i
42
j
Matematika - fyzika - informatika 21 2011/2012
z klad pak dok eme zp tn zrekonstruovat seznam v ech vypu t nch vagn pro zsk n vslednho symetrickho vlaku dlky V 1 N ]. Vsledn program vych z z p edchozho e en jednodu lohy, do n ho jsme pouze doplnili pr ci se zmn nm polem X a vpis sel vypou t nch vagn. program Vlak_2 {uren dlky maximln symetrick vybran podposloupnosti a nalezen jedn takov symetrick podposloupnosti max. dlky vstupem je seznam pozic znak, kter je t eba vynechat} const MaxN = 50000 var A: array 1..MaxN] of char {zadan posloupnost = vlak} V: array 1..MaxN, 1..MaxN] of integer {dlky max. symetrickch vybranch podposloupnost} X: array 1..MaxN, 1..MaxN] of integer {po adov slo znaku, kter se m z seku vypustit} N: integer {dlka posloupnosti} i, j, Delka: integer {rozsah a dlka zvolenho seku posloupnosti} begin readln(N) {dlka posloupnosti} for i:=1 to N do read(A i]) {prvky posloupnosti} for i:=2 to N do V i,i-1]:=0 {przdn sek} for i:=1 to N do V i,i]:=1 {jednoprvkov sek} for Delka:=2 to N do {dlka seku} for i:=1 to N-Delka+1 do {zatek seku} begin j:=i+Delka-1 {konec seku} if A i]=A j] then begin V i,j]:=V i+1,j-1]+2 X i,j]:=0 end {nic se nevypust, oba krajn znaky seku zstvaj}
Matematika - fyzika - informatika 21 2011/2012
43
else if V i+1,j] > V i,j-1] then begin V i,j]:=V i+1,j] X i,j]:=i end {vypust se prvn znak seku} else begin V i,j]:=V i,j-1] X i,j]:=j end {vypust se posledn znak seku} end {V 1,N] je dlka maximln vybran symetrick podposloupnosti} writeln(N-V 1,N]) {minimln poet vyputnch znak} {rekonstrukce seznamu vech vyputnch znak pro zskn maximln symetrick vybran podposloupnosti dlky V 1,N]:} i:=1 j:=N while i < j do {zkouman sek nen triviln} if X i,j] = 0 then begin inc(i) dec(j) end else begin write(X i,j], ' ') {po adov slo vyputnho znaku} if X i,j] = i then inc(i) else dec(j) end writeln end.
Literatura 1] Tpfer, P: Maximln palindrom ( lohy z MO { kategorie P { 24. st). MFI, r. 19 (2009/10), . 5 a 6. 2] Tpfer, P: Spolen vybran podposloupnost ( lohy z MO { kategorie P { 17. st). MFI, r. 17 (2007/08), . 2. 3] Tpfer, P: Poklesl podposloupnost ( lohy z MO { kategorie P { 20. st). MFI, r. 17 (2007/08), . 9.
44
Matematika - fyzika - informatika 21 2011/2012
M e pota rozvjet kreativitu k ? HELENA BINTEROV { EDUARD FUCHS Pedagogick fakulta JU esk Budjovice, Prodovdeck fakulta MU Brno
V pr ci ukazujeme, jak lze pota vyut k e en n kterch problm, kter mohou bt jinak pro ky jen velmi obtn e iteln. Souasn ukazujeme, e vyuit potae me p isp t ke zv en z jm k o teoretick z zem e en problematiky a podntit tak kovsk z jem o hlub pochopen probran l tky.
1. vod
Do v ech oblast na eho ivota, vetn vzd l v n, se st le intenzivn ji promtaj zm ny zpsoben masivnm nasazov nm pota a dal ch modernch technologi. I velmi konzervativn pedagogov jsou si dnes ji v domi toho, e tyto technologie a souasn "informan exploze# by se m ly odr et i ve kolsk praxi, zejmna ve vyuovacch metod ch (viz nap . 1]). Vyvst v tu v ak ada problm, jejich podstatou jsou ot zky, jakou roli maj hr t p i vuce potae a jak to ud lat, aby bylo dosaeno proklamovanch modernch cl vuky a aby p itom nedo lo k poklesu pot ebnch kovskch znalost. Odpov di na tyto ot zky nejsou jednoduch. K tomu, abychom kvalitn vzd l vali nap klad ky z kladn koly, nesta zakoupit interaktivn tabule a p slu n matematick programy a p itom je vyuvat "po staru#. P edev m musme mt ujasn no, jak dos hneme innho vyuit novch technologi v jednotlivch f zch pojmotvornho procesu, jak je tedy zapojit do vuky tak, aby se staly jej organickou sou st a ci je vyuvali aktivn a clen . Samotn zapojen modernch technologi do vuky ji mon urychl, av ak nezkvalitn. Clem je nauit se vyuvat tyto prost edky k tomu, aby ci um li na odpovdajc rovni e it problmy, aby um li p em let, t dit a vybrat nabzen informace a aby je dok zali samostatn pouvat a obhajovat v kadodennm ivot . O takov vyuit jsme se pokusili v n sledujcm experimentu. Matematika - fyzika - informatika 21 2011/2012
45
2. Popis experimentu
V na ich uebnicch Aritmetiky a Geometrie pro 6. { 9. t du (viz nap . 2]) se sname ve v e uvedench intencch pracovat. Jsme p esv deni, e experimentov nm, porovn v nm situac, kter znaj z b nho ivota, hled nm skrytch z konitost, postupnm vytv enm spr vn terminologie, nen silnm vedenm ke spr vnmu vyjad ov n a oznaov n v c, jsou ci vedeni k tomu, aby matematiku ch pali jako mocn n stroj k pozn v n sv ta. Tento p stup povaujeme i za cestu k tomu, aby matematice dob e porozum li a aby se matematika stala jednm z jejich oblbench p edm t. Je n m v ak jasn, e tento postup je asov n ron a pro vyuujcho mnohem obtn j ne klasick "front ln# vuka, kdy uitel v systematickm vkladu sezn m ky s novm tmatem a db pouze na to, aby mu ci pokud mono dob e porozum li. Nyn strun pop eme jednu z monost, jak jsme testovali vhodnost vyuit informanch technologi p i samostatn pr ci k. V uebnici 2] jsme v 9. t d za adili n sledujc lohu: "T dn uitelka dala Petrovi v 8. A kol: "Pete, zbylo mi v tdnm fondu 240 K . Mohl bys mi spo tat, kolik bychom za tuto stku mohli koupit se it tak, aby dn penze nezbyly? Uvauj se it . 445 (A4 { linkovan), jeho cena je 16 K a se it . 540 (A5 { linkovan), jeho cena je 8 K .# Petr zjistil, e to bude mon a na el n kolik variant. Vytvo te n vrh v ech monch variant n kupu se it pro 8. A. Kolik jich je?# loha se uk zala pro ky z kladn koly obtn , i kdy v podstat jde o jednoduchou diofantovskou rovnici. Nalezen n jakho e en je vcemn jednoduch, nalezen v ech poadovanch e en je u sloit j a vyaduje od k promy lenou strategii a systematick p stup. Pr v na tto nestandardn loze, kter pom rn vrazn p esahuje "povinn# uivo, jsme se rozhodli otestovat, jakou roli me sehr t pota, pokud se ci k jeho vyuit rozhodnou. Na z kladn kole, kde probhalo vyuov n s na lektorkou, jsme zadali uvedenou lohu ve dvou paralelnch a prosp chov srovnatelnch t d ch. P itom jsme v jedn t d km povolili vyut pouze tuku a papr, ve druh t d mohli ci pracovat na potai, nedostali v ak dn n vod, jak pracovat, jak software mohou vyut apod. Poznamenejme je t , e ci dev tch t d na dan kole b n pracovali s programy MS Excel, GeoGebra, Derive 6, Cabri II+ a Geonext. Ke spln n danho kolu ci dostali as 20 minut, pot jsme se v no46
Matematika - fyzika - informatika 21 2011/2012
vali rozboru lohy a pro li jsme spolen mon postupy vedouc k vy e en
lohy. T dy byly prm rn a jak jsme ji uvedli, byly jejich vkony v matematice srovnateln. Ve t d ch nebyl ani jeden vrazn ji talentovan k, prosp chov lep ci ode li ji d ve na vcelet gymn zia. +kola je typickou sdli tn kolou a nem dnou specializaci. &e en p klad byl b nou sou st hodiny. Nyn strun okomentujme vsledky obou skupin. (Podrobn j popis n kterch kovskch strategi lze nalzt v pr ci 3]).
Vsledky prvn skupiny
V prvn skupin se vuky z astnilo 18 k. Sedm z nich nenalezlo ve stanovenm dvacetiminutovm limitu dn e en. , ci, kte alespo jedno e en nalezli, pracovali, a na jednu vjimku, metodou, kterou bychom mohli nazvat pokus { omyl. V echna tato e en byla n hodn , ci se bez hlub ho zdvodn n pokou eli o nalezen n jak ho e en na z klad vlastnost zadanch selnch hodnot. V t ina d t nalezla jen n kter ze 16 monch e en. Pouze jeden k na z klad jednoho e en dok zal nalzt systematick postup a nalezl e en v echna. Jedin k nehledal e en n hodn a pokou el se sestavit rovnici, kter by mu umonila v echna e en nalzt. Akoliv tuto rovnici spr vn sestavil, odvodil z n pouze t i e en.
Vsledky druh skupiny
Vuky se z astnilo 15 k. Dva z nich nenalezli dn e en, dva dal pracovali, stejn jako ci v prvn skupin , pouze s tukou a paprem, jeden ct k se rozhodlo vyut pota. Zajmav bylo, e oba ci, kte pracovali bez potae, nalezli v echna e en. Lze tedy dedukovat, e loha pro n nebyla natolik obtn , aby povaovali za nutn pota vyut. Jak si ponali ci, kte se rozhodli vyut pota? Zajmaly n s dv ot zky: a) jak software se rozhodnou vyut, b) jak budou p i e en lohy
sp n. Nejast ji vyuitm softwarem se stal, nikoliv p ekvapiv , Excel, kter zvolilo sedm k. T i ci se rozhodli pro GeoGebru a jeden pro Derive. Pot iteln bylo, e z jeden cti k, kte pota vyuili, jich deset nalezlo v ech 16 e en. Pro zajmavost uve%me e en aky, kter nalezla pouze 15 e en. Ta pracovala s Excelem a jej e en je na obr. 1. V popsanm e en chyb p pad 0 8 + 15 16. Zajmav bylo, e ani po Matematika - fyzika - informatika 21 2011/2012
47
; ; ; ; ; Obr. 1
Obr. 2
48
Matematika - fyzika - informatika 21 2011/2012
n slednm dotazu uitelky, zda by nebylo mon nalzt je t n jak dal e en, na n nep i la. Na uvedenm e en n m p itom p i lo pozoruhodn, e ve t etm sloupci aka dopotala rozdl ceny po n kupu se it za 8 K a ten pak d lila 16, co naznauje jistou strategickou manipulaci s vrazem. Zajmav a nestandardn byl Martinv postup, kter nalezl v echna e en pomoc tabulky na obr. 2. Martin si z ejm nejprve vypotal cenu n kupu obou druh se it v takovm potu, aby se ve el do stky 240 K a pot k cen m za dan poet levn j ch se it dopot val ceny se it za 16 K tak dlouho, a se dostal k clov stce. Strun se je t zmime o kovi, kter jako jedin pouil Derive. Na jeho postupu bylo zajmav, e ne e il prim rn dnou rovnici, ale sestrojil odpovdajc line rn funkci (viz obr. 3). Na ot zku, jak na line rn funkci p i el, odpov d l, e "ji vid#. , k nalezl spr vn v echna e en, z jeho postupu v ak bylo obtn rekonstruovat, do jak mry jednotliv e en tipoval a do jak mry byl jeho postup v dom.
; ; Obr. 3
V kadm p pad v ak byly vsledky ve druh skupin vrazn lep ne ve skupin prvn.
Stru n vyhodnocen
)ten e { stejn jako n s { jist p ekvapuje vysok poet d t, kter nenalezly dn e en. K tomu p ece sta v podstat velmi jednoduch Matematika - fyzika - informatika 21 2011/2012
49
sudek: protoe 16 + 8 = 24, je e enm nap klad deset velkch a deset malch se it. Dal e en pak lze snadno nalzt tak, e velk se it "vym nm# za dva mal. Pro tedy tolik d t vbec neusp lo? Vysv tlenm by mohl bt fakt, e to bylo vbec poprv, kdy se ci setkali s lohou, kde k vy e en nemaj "dost# daj a loha je zaskoila. Jsou v t inou zvykl sestavit rovnici, dosadit daje a vy e it rovnici na rovni kalkulativn bez hlub ho porozum n. Pota tak ve druh skupin zpo tku suploval nedostatenou rove kovskch sudk, pramenc t eba i z mal zku enosti s takovmi lohami. Postupn v ak pota kovsk sudek kultivoval a pozdvihl zvl dnut problematiky do vy rovn .
3. Dal postup
Dal ot zkou, na kterou jsme hledali odpov %, bylo to, zda m pouit potae vliv na strategii k p i e en podobnch loh. Proto jsme po skonen popisovan lohy v obou t d ch zad n na prvn pohled nepatrn obm nili { zm nili jsme cenu 16 K na 17 K. Vsledek v podstat odpovdal na hypotze: v prvn skupin takto pozm n nou lohu nevy e il nikdo celou- pouze osm d t si uv domilo, e e enm je evidentn monost 0 17+30 8. Druh e en, tj. 8 17+13 8, nena el nikdo, protoe metoda "pokus omyl# z kovskho pohledu "dlouho# nevedla k dnmu vsledku. Pouze jeden k pot po vyuujc cht l, aby mu vysv tlila, jak by mohl postupovat obecn . Uitelin vklad v ak zajmal evidentn pouze jeho, dal ci jeho vahy a smysl jeho dotaz vbec nech pali. Ve druh t d byl vsledek diametr ln odli n: jeden ct d t, tedy naprost v t ina, lohu kompletn vy e ila. V ichni pouili sv p edchoz e en, jen zam nili slo 16 za 17. Zejmna n s v ak pot ila dal skutenost: est k cht lo zn t obecn postup p i e en takovch loh a vklad uitelky sledovali se zaujetm. I na z klad tohoto jedinho experimentu si tak dovolujeme tvrdit, e vhodn a ve spr vnou chvli naasovan vyuit potae me p isp t k prohlouben z jmu o teoretickou str nku problematiky a vrazn tak me p isp t k hlub mu vhledu k do probranho uiva. Analogick lohy jsme pot e ili s ky obou t d ve vb rovm semin i, do n ho chodila p iblin polovina k z obou t d. I ci z t t dy, kter ve vuce potae neuvala, vcelku rychle pochopili p ednost jejich vyuit a rychle se na p slu n postupy adaptovali. V jedn hodin pak ci e ili lohy vedouc na rovnice 8x + 17y = 250 a 8x + 15y = 250. , ci v ak i nyn pracovali v podstat samostatn , mohli si zvolit software 50
Matematika - fyzika - informatika 21 2011/2012
dle vlastnho vb ru a vyuujc jen korigovala p padn nesrovnalosti. Ze zajmavch kovskch e en uv dme dv n sledujc. Honza nejprve e il rovnici 8x + 17y = 250. Otev el si GeoGebru a pomoc p kazovho dku na spodn sti n kresny sestrojil p slu nou p mku. Pot si zapnul zobrazen m ky a zjevn odhadl, e celoselnm e enm by mohlo bt x = 10, y = 10. Jako druh mon e en se mu nabzel bod x = 27, y = 2, nebyl si v ak z ejm jist. Kliknutm na tento bod (na obr. 4 bod B) mu program uk zal, e by m l dan bod leet na sestrojen p mce. Protoe tento daj nepovaoval za zcela hodnov rn, otev el si tabulkov procesor skryt v GeoGeb e a pomoc tabulky, kterou si p ipravil podobn jako jin ci v Excelu, rychle zjistil, e na el e en spr vn a jin celoseln e en zde nejsou. Postupn takto pracoval i s dal mi rovnicemi a e en vdy na el.
;; ; Obr. 4
N kolik k v semin i v ak ji necht lo pouze experimentovat, ale cht li v d t, jak by se takov rovnice daly e it obecn . V dev t t d samoz ejm nelze budovat teorii ani t ch nejjednodu ch diofantovskch rovnic. Na druh stran jsme v ak km cht li poskytnout monost do tmatu, kter je zaujalo, alespo sten proniknout. Proto jsme s nimi probrali postupy uveden na webov str nce http://www.math.uwaterloo.ca/~snburris/htdocs/linear.html, kde jsou e eny diofantovsk rovnice tvaru ax + by = c. P i studiu t chto str nek jsme se postupn zcela nen siln dostali i k Eukleidovu algoritmu, k loze parametru v obecnm e en a k dal problematice. Matematika - fyzika - informatika 21 2011/2012
51
, ci m li poslze samostatn prok zat, jak e en uvedenmu na internetovch str nk ch rozum j. Uve%me jako jeden za zajmavch p klad postup Martina. Ten pot, co pro rovnici 8x + 15y = 250 nalezl na webov str nce e en x0 = 500+15n, y0 = ;250 ; 8n, vypotal e en v kladnch celch slech, kter odpovdalo slovn loze, pomoc Excelu, viz obr. 5. Na lev stran je uvedeno standardn e en ve form , v n uv d l e en d v j ch p klad. P i odvozov n t chto vsledk z obecnho e en diofantovsk rovnice spr vn vyhodnotil, e mus volit z porn hodnoty parametru. P estoe v d l, e pro mal absolutn hodnoty parametru je hodnota y z porn a tedy neodpovd slovn loze, zahrnul do vsledn tabulky v echny hodnoty pro n = ;1 ;2 : : : , aby n kter e en nep ehldl.
; ; ; Obr. 5
52
Matematika - fyzika - informatika 21 2011/2012
Zv r
Na m z m rem samoz ejm nebylo probrat uivo o diofantovskch rovnicch. Povaovali jsme v ak tuto tematiku za vhodnou k ov en toho, do jak mry ci dovedou tvrm zpsobem vyut vpoetn techniku k e en problm, s nimi se dosud nesetkali, a zda vbec je v takov situaci vyuit potae efektivn. Obecn vzato je vdy nutno peliv zvaovat, kde le hranice mezi smysluplnm a nevhodnm vyuitm pota, a samoz ejm jsme si v domi ady problm, kter nevhodn vyuit pota p in . Domnv me se v ak, e v tomto p pad bylo vyuit pota efektivn a vhodn. Akoliv dv studijn skupiny, v nich jsme lohy e ili, byly v podstat prosp chov srovnateln, dos hli ci vyuvajc samostatn vpoetn techniku prokazateln lep ch vsledk. Za je t cenn j pak povaujeme to, e skupina vyuvajc potae n sledn projevovala v t z jem o pochopen teoretickho z zem a jejich motivace ke zvl dnut podstaty problmu byla na vy rovni ne u t ch k, kte se { v t inou marn { o vy e en loh snaili bez potae. Dky potai tak ci objevili v probran l tce matematickou "kr su# tam, kde ci bez potae vid li jen "d inu# a morn bezvsledn pot n. Literatura 1] Binterov, H. { Fuchs, E.: Pota, troj helnk a kvadratick funkce. MFI, r. 19 (2009/10), . 6. 2] Binterov, H. { Fuchs, E. { Tlust, P.: Algebra 9. Uebnice pro zkladn koly a vcelet gymnzia. Plze : Fraus 2010. 3] Binterov, H. { Fuchs, E.: Nestandardn lohy s potaem v 9. td. In: Sbornk 9. setkn uitel matematiky v ech typ a stup kol. Plze , Vydavatelsk servis, 2010, s. 63{67. 4] Moss, G. { Jewitt, C. { Levaic, R. { Armstrong, V. { Cardini, A. { Castle, F.: The Interactive Whiteboards. Pedagogy and Pupil Performance Evaluation: Evaluation of the Schools Whiteboard Expansion (SWE) Project: London Challenge, Institute of Education London, 2007.
Matematika - fyzika - informatika 21 2011/2012
53
