zapocet 2008
zapocet 2008
ahojte,mohli by ste sem napisat,ake programy dava kryl na praktickom teste?
-
- Matfyz(ák|ačka) level I
- Příspěvky: 4
- Registrován: 3. 12. 2007 17:09
- Typ studia: Matematika Bc.
Re: zapocet 2008
Doporučuji projít veškeré algoritmy z této stránky:
http://ksvi.mff.cuni.cz/~kryl/Avyuka/20078/PRM044.htm
Potom doporučuji všechny testy z jeho sbírky testů. Koluje po netu v několika podáních, v příloze je jedno z nich. Jinak záleží na tom, co si vylosuješ. Kolega, co seděl vedle mě si vytáhl latinské čtverce, přede mnou měli šachovnice - no, moc jsem jim to nezáviděl.
http://ksvi.mff.cuni.cz/~kryl/Avyuka/20078/PRM044.htm
Potom doporučuji všechny testy z jeho sbírky testů. Koluje po netu v několika podáních, v příloze je jedno z nich. Jinak záleží na tom, co si vylosuješ. Kolega, co seděl vedle mě si vytáhl latinské čtverce, přede mnou měli šachovnice - no, moc jsem jim to nezáviděl.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 28
- Registrován: 28. 6. 2006 22:51
- Typ studia: Matematika Mgr.
- Kontaktovat uživatele:
Re: zapocet 2008
Ahoj!
Dnes som bol na teste z programka (neuspel som
). Co sa tyka prikladov, tak boli aj tieto: najst najkratsiu cestu na sachovnici, premutacie, morseovka, nasobenie matic(chcel aby to pracovalo v lepsom case ako N), zlozene zavorky, sifra Monte Christo, zaplatit danu ciastku pomocou sady minci, latinske stvorce, zarovnanie textu do bloku. Ja som si vsak vytiahol nieco, co som nevedel, ze tam byva. Zadanie bolo dlhe, ale priklad sa volal ''Krvna banka'' a ulohou bolo podat krvne transfuzie chorym ludom tak, aby som ich co najviac zachranil....(ak by mal niekto zaujem, mozem sem hodit presne zadanie). Ja som velmi nevedel, co s tym robit. Ak by ste niekto vedeli, ako na to, tak pls napiste postup....
Vdaka!
Dnes som bol na teste z programka (neuspel som
![Sad :(](./images/smilies/icon_sad.gif)
Vdaka!
Re: zapocet 2008
Ahoj, ja som mal tiez krvnu banku cize mozem napisat, ako to cca islo.
Zadanie:
Mame nejake typy krvi. Kazda krv je bud RH+ alebo RH- a nezavisle na tom este moze byt 0, A, B alebo AB (cize dokopy 8 typov krvi).
My sme nemocnica a na sklade mame dany pocet konzerv z kazdeho typu krvi (to bolo treba nacitat zo suboru). Tiez mame dva druhy pacientov:
Ulohou je transplantovat krv podla nasledujucich pravidiel:
i) Najprv sa transplantuje krv kritickym pacientom:
Riesenie:
Ta druha cast bola lahsia. Po prvej casti nam zostali nejake krvne konzervy, a kedze nemozme miesat krv, tak transplantujeme najviac krvi, ako sa da.
Napr. ak na sklade mame 4 konzervy A+ a mame 5 pacientov so skupinou A+, tak urobime transfuziu styrom. (Ak by bolo konzerv viac ako pacientov, "transfuzovali" by sme vsetkym pacientom a nejake konzervy by zostali).
Ta prva cast je na prvy pohlad zlozita, ale slo ju relativne jednoducho riesit. Najprv sa da vsimnut si, ze medzi RH+ a RH- nejde miesat,
cize akoby sme mali 2 rovnake navzajom nezavisle problemy len so skupinami 0, A, B a AB. No a riesenie vyzera tak, ze transplantujeme
co najviac krvi v tomto poradi (nezavisle pre RH+ a RH-):
Nejakym dokazom na styl diskretky ide ukazat, ze ked to spravime takto, splnime vsetky podmienky zo zadania, ale Kryl to odo mna nechcel. Takze tak, snad to niekomu pomoze.
Zadanie:
Mame nejake typy krvi. Kazda krv je bud RH+ alebo RH- a nezavisle na tom este moze byt 0, A, B alebo AB (cize dokopy 8 typov krvi).
My sme nemocnica a na sklade mame dany pocet konzerv z kazdeho typu krvi (to bolo treba nacitat zo suboru). Tiez mame dva druhy pacientov:
- - kritickych (ktori zomru ak im netransplantujeme krv)
- nekritickych (to su ti ostatni)
Ulohou je transplantovat krv podla nasledujucich pravidiel:
i) Najprv sa transplantuje krv kritickym pacientom:
- - treba ich zachranit najviac ako sa da
- co najviac z nich ma dostat rovnaky typ krvi, aku maju
- ak inac nejde, moze sa "miesat krv" tak, ze 0 moze dostat kazdy (0 je univerzalny darca) a AB moze prijat hocijaku krv
(AB je univerzalny prijemca), pricom ale RH faktor musi byt zachovany.
- - zase treba transplantovat najviac, ako ide
- pacient moze dostat len rovnaku krv, aku ma (nemoze sa "miesat")
Riesenie:
Ta druha cast bola lahsia. Po prvej casti nam zostali nejake krvne konzervy, a kedze nemozme miesat krv, tak transplantujeme najviac krvi, ako sa da.
Napr. ak na sklade mame 4 konzervy A+ a mame 5 pacientov so skupinou A+, tak urobime transfuziu styrom. (Ak by bolo konzerv viac ako pacientov, "transfuzovali" by sme vsetkym pacientom a nejake konzervy by zostali).
Ta prva cast je na prvy pohlad zlozita, ale slo ju relativne jednoducho riesit. Najprv sa da vsimnut si, ze medzi RH+ a RH- nejde miesat,
cize akoby sme mali 2 rovnake navzajom nezavisle problemy len so skupinami 0, A, B a AB. No a riesenie vyzera tak, ze transplantujeme
co najviac krvi v tomto poradi (nezavisle pre RH+ a RH-):
Kód: Vybrat vše
[konzerva] -> [pacient]
// vsetku AB dame AB, pretoze ju aj tak nikto iny nemoze dostat
AB -> AB
// co najviac B dame B, ak nejaka este zvysi, mozme ju dat ABcku
B -> B
B -> AB
// co najviac A dame A, ak nejaka este zvysi, mozme ju dat ABcku
A -> A
A -> AB
// co najviac 0 dame 0, ak este zvysi, postupne ju mozme dat ostatnym
0 -> 0
0 -> A
0 -> B
0 -> AB
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: zapocet 2008
Je tam jen jeden problem, ktery neni ze zadani jednoznacne zda se ma resit (se mi zda) .. kdyz se pouzije pravidlo B->AB, tak se muze stat, ze kdyby se byvalo bylo pouzilo pravidlo A->AB, tak je mozne zachranit vic nekritickych pacientu. (situace nekriticti jsou sami B, ale B nam dojde na kriticke AB, na ktere by ale stacila zbyla A).
EDIT:
resenim by bylo napriklad:
1) udelat nemichane kriticke (zbyde X),
2) nasimulovat si nekriticke (z X, zbyde Y),
3) ze zbytku po simulaci (Y) udelat michane kriticke (zbyde Z), -- tady se zajisti aby se pouzilo to co je vhodnejsi i s ohledem na nekriticke a muzeme normalne pokracovat
4) pak z toho ce se zatim skutecne nepouzilo (zbytek: Z a simulace: X-Y) kriticke (zbyde W)
5) ze zbytku (W) obslouzit nekriticke
druha moznost je obslouzit nejprv nekriticke, pak ze zbytku kriticke a pak se kouknout kteremu nekritickemu by se dalo vzit na ukor kritickeho (to mi prijde nejsnazsi, ale nejsem si ted uplne jist korektnosti)
EDIT:
resenim by bylo napriklad:
1) udelat nemichane kriticke (zbyde X),
2) nasimulovat si nekriticke (z X, zbyde Y),
3) ze zbytku po simulaci (Y) udelat michane kriticke (zbyde Z), -- tady se zajisti aby se pouzilo to co je vhodnejsi i s ohledem na nekriticke a muzeme normalne pokracovat
4) pak z toho ce se zatim skutecne nepouzilo (zbytek: Z a simulace: X-Y) kriticke (zbyde W)
5) ze zbytku (W) obslouzit nekriticke
druha moznost je obslouzit nejprv nekriticke, pak ze zbytku kriticke a pak se kouknout kteremu nekritickemu by se dalo vzit na ukor kritickeho (to mi prijde nejsnazsi, ale nejsem si ted uplne jist korektnosti)
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
-
- Matfyz(ák|ačka) level I
- Příspěvky: 28
- Registrován: 28. 6. 2006 22:51
- Typ studia: Matematika Mgr.
- Kontaktovat uživatele:
Re: zapocet 2008
Dakujem za prispevky, mne to velmi pomohlo, aspon som zistil, co sa to v tom priklade malo vlastne robit.... Este by som sa chcel spytat na jednu vec. Vraj sa na zapoctovych testoch vyskytol priklad s nazvom ''dominancia damy na sachovnici''. Neviete niekto nejake presnejsie zadanie a ak by ste vedeli, tak aj strucny popis riesenia???
Dakujem!
Dakujem!
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: zapocet 2008
muj tip podle nazvu je umistit damu tak, aby napadala co nejvic policek:) .. ale vazne je to jen tip
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
-
- Matfyz(ák|ačka) level I
- Příspěvky: 28
- Registrován: 28. 6. 2006 22:51
- Typ studia: Matematika Mgr.
- Kontaktovat uživatele:
Re: zapocet 2008
A ako by sa to malo riesit???hippies píše:muj tip podle nazvu je umistit damu tak, aby napadala co nejvic policek:) .. ale vazne je to jen tip
![Shocked :shock:](./images/smilies/icon_eek.gif)
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: zapocet 2008
v kazdem policku mam record (pocet volnych v kazdem z 8 smeru), vyplnuji po radcich, obsazene policko ma vsechny polozky 0, prazdne policko ma hodnoty stejne jako predchudce v danem smeru(+/- 1), pokud je predchudce obsazen (tj. vsechny polozky ma 0), tak se musi ve smeru dopredu (tam co jsem zatim nehledal) delka vyhledu pocitat (jdu dokud nenarazim na kamen/konec, pro jednoduchost je vhodne sachovnici olemovat kameny [souradnice 0, 9])
x kamen, o aktualne vyplnuju -> kolik je volnych dolu neni x-1 (jak by bylo kdyby x byl volny), ale musim ten sloupec opravdu projit.
vysledek je policko s nejvetsim souctem danych osmi cisel.
slozitost je 2*m*n, kde m,n jsou rozmery sachovnice.
Kód: Vybrat vše
. . x . .
. . o . .
. . . . .
vysledek je policko s nejvetsim souctem danych osmi cisel.
slozitost je 2*m*n, kde m,n jsou rozmery sachovnice.
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Re: zapocet 2008
Pytal som sa Kryla, ci bolo treba brat do uvahy aj toto. Odpovedal, ze nie, teda ze najprv treba zachranit hocijako co najviac kritickych a potom co najviac nekritickych. Ale tvoje riesenie toho rozsireneho znie celkom rozumne.hippies píše:Je tam jen jeden problem, ktery neni ze zadani jednoznacne zda se ma resit (se mi zda) .. kdyz se pouzije pravidlo B->AB, tak se muze stat, ze kdyby se byvalo bylo pouzilo pravidlo A->AB, tak je mozne zachranit vic nekritickych pacientu. (situace nekriticti jsou sami B, ale B nam dojde na kriticke AB, na ktere by ale stacila zbyla A).
Re: zapocet 2008
Neznelo zadani "dominance dam na sachovnici"? To je totiz jedna z docela beznych uloh, ktere se u testu vyskytuji. Presne zadani: umistete na sachovnici o rozmerech m krat n co nejmene dam tak, aby ovladly celou sachovnici.quark87 píše:Vraj sa na zapoctovych testoch vyskytol priklad s nazvom ''dominancia damy na sachovnici''. Neviete niekto nejake presnejsie zadanie a ak by ste vedeli, tak aj strucny popis riesenia???
Reseni je na strance http://vyuka.pavel-rimsky.cz/wiki/doku.php . Princip: hledame nejmensi p takove, pro ktere p vhodne rozmistenych dam ovladne celou sachovnici. Pro dane p a danou sachovnici m*n hledame vsechny p-prvkove kombinace jejich policek (tedy p-prvkove podmnoziny mnoziny jejich policek). Pro kazdou takovou kombinaci overime, jestli by damy rozmistene na techto p policek ovladly sachovnici. Pokud jo, vypiseme toto rozmisteni.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 28
- Registrován: 28. 6. 2006 22:51
- Typ studia: Matematika Mgr.
- Kontaktovat uživatele:
Re: zapocet 2008
Ahoj!
Ak niekto viete, mohli by ste sem, pls, napisat proceduru, ktora umocni maticu (na velku mocninu), ale v logaritmickom case??? Velmi vam budem vdacny, ja s tym moc neviem pohnut![Sad :(](./images/smilies/icon_sad.gif)
Ak niekto viete, mohli by ste sem, pls, napisat proceduru, ktora umocni maticu (na velku mocninu), ale v logaritmickom case??? Velmi vam budem vdacny, ja s tym moc neviem pohnut
![Sad :(](./images/smilies/icon_sad.gif)
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: zapocet 2008
Mocni si ty matice chytře, po mocninách dvojky:quark87 píše:Ahoj!
Ak niekto viete, mohli by ste sem, pls, napisat proceduru, ktora umocni maticu (na velku mocninu), ale v logaritmickom case??? Velmi vam budem vdacny, ja s tym moc neviem pohnut
Priklad
13 = 8 + 4 + 1, budes potrebovat 3 nasobeni na predpripravu matic a 3 nasobeni vysledne
45 = 32 + 8 + 4 + 1, budes potrebovat 5 nasobeni na predpripravu a 4 nasobeni vysledne
Osiris
-
- Matfyz(ák|ačka) level I
- Příspěvky: 28
- Registrován: 28. 6. 2006 22:51
- Typ studia: Matematika Mgr.
- Kontaktovat uživatele:
Re: zapocet 2008
Osiris píše:Mocni si ty matice chytře, po mocninách dvojky:quark87 píše:Ahoj!
Ak niekto viete, mohli by ste sem, pls, napisat proceduru, ktora umocni maticu (na velku mocninu), ale v logaritmickom case??? Velmi vam budem vdacny, ja s tym moc neviem pohnut
Priklad
13 = 8 + 4 + 1, budes potrebovat 3 nasobeni na predpripravu matic a 3 nasobeni vysledne
45 = 32 + 8 + 4 + 1, budes potrebovat 5 nasobeni na predpripravu a 4 nasobeni vysledne
Vdaka! Toto som si uvedomil, ale problem je, ze to neviem napisat v pascale...nemohol by si, pls, napisat tu proceduru, ktora to bude mocnit? Fakt ti budem vdacny
Re: zapocet 2008
Vysvetlim to na prikladu celych cisel, jsi-li chytry matfyzak, bude pro tebe prevedeni na matice brnkacka.
Uvažte tento postup hledání 215:
215 =
= (1)*215
= (2)*214
= (2)*47
= (2*4)*46
= (2*4)*163
= (2*4*16)*162
= (2*4*16)*2561
= (2*4*16*256) = 32768.
V každém okamžiku se dá výsledek zapsat jako prubezny_vysledek*zakladzbyva, kde prubezny_vysledek je "průběžným výsledkem" (na začátku má hodnotu 1, na konci obsahuje skutečný výsledek umocňování, tj. 215), zaklad má na začátku hodnotu 2 a zbyva říká, na kolik je ještě potřeba umocnit základ. V každém kroku se provede toho:
zbyva je liché - zmenšíme zbyva o 1 a zakladem vynásobíme prubezny_vysledek
zbyva je sudé - zaklad umocníme na druhou a zbyva vydělíme dvěma
Platí tedy tento invariant:
xn = prubezny_vysledek*zakladzbyva
Na začátku položíme:
prubezny_vysledek := 1
zaklad := x
zbyva := n
Je třeba se zamyslet, že kroky nemění invariant (je to vidět z příkladu počítání 215).
Kód programu, který řeší daný problém:
Uvažte tento postup hledání 215:
215 =
= (1)*215
= (2)*214
= (2)*47
= (2*4)*46
= (2*4)*163
= (2*4*16)*162
= (2*4*16)*2561
= (2*4*16*256) = 32768.
V každém okamžiku se dá výsledek zapsat jako prubezny_vysledek*zakladzbyva, kde prubezny_vysledek je "průběžným výsledkem" (na začátku má hodnotu 1, na konci obsahuje skutečný výsledek umocňování, tj. 215), zaklad má na začátku hodnotu 2 a zbyva říká, na kolik je ještě potřeba umocnit základ. V každém kroku se provede toho:
zbyva je liché - zmenšíme zbyva o 1 a zakladem vynásobíme prubezny_vysledek
zbyva je sudé - zaklad umocníme na druhou a zbyva vydělíme dvěma
Platí tedy tento invariant:
xn = prubezny_vysledek*zakladzbyva
Na začátku položíme:
prubezny_vysledek := 1
zaklad := x
zbyva := n
Je třeba se zamyslet, že kroky nemění invariant (je to vidět z příkladu počítání 215).
Kód programu, který řeší daný problém:
Kód: Vybrat vše
uses crt;
var n,
zbyva: integer;
zaklad,
prubezna,
x: real;
begin
writeln('Zadej x: ');
read(x);
writeln('Zadej n: ');
read(n);
zbyva := n;
prubezna := 1;
zaklad := x;
while (zbyva > 0) do begin
if zbyva mod 2 = 0 then begin
zaklad := zaklad*zaklad;
zbyva := zbyva div 2;
end else begin
zbyva := zbyva - 1;
prubezna := prubezna*zaklad;
end;
end;
writeln('Vysledek je ', prubezna);
readkey;
end.