zapocet 2008

Návštěvník

zapocet 2008

Příspěvek od Návštěvník »

ahojte,mohli by ste sem napisat,ake programy dava kryl na praktickom teste?
milda231
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 3. 12. 2007 17:09
Typ studia: Matematika Bc.

Re: zapocet 2008

Příspěvek od milda231 »

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.
test.zip
(29.83 KiB) Staženo 937 x
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.
quark87
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

Příspěvek od quark87 »

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!
misko sz

Re: zapocet 2008

Příspěvek od misko sz »

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:
  • - kritickych (ktori zomru ak im netransplantujeme krv)
    - nekritickych (to su ti ostatni)
(Pocty pacientov aj s ich skupinami znovu bolo treba nacitat zo suboru.)

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.
ii) Potom sa transplantuje krv nekritickym:
  • - 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
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.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: zapocet 2008

Příspěvek od hippies »

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)
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ů..
quark87
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

Příspěvek od quark87 »

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!
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: zapocet 2008

Příspěvek od hippies »

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ů..
quark87
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

Příspěvek od quark87 »

hippies píše:muj tip podle nazvu je umistit damu tak, aby napadala co nejvic policek:) .. ale vazne je to jen tip
A ako by sa to malo riesit??? :shock:
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: zapocet 2008

Příspěvek od hippies »

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])

Kód: Vybrat vše

. . x . .
. . o . .
. . . . .
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.
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ů..
misko sz

Re: zapocet 2008

Příspěvek od misko sz »

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).
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.
Návštěvník

Re: zapocet 2008

Příspěvek od Návštěvník »

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???
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.

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.
quark87
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

Příspěvek od quark87 »

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 :(
Osiris
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

Příspěvek od Osiris »

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 :(
Mocni si ty matice chytře, po mocninách dvojky:

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
quark87
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

Příspěvek od quark87 »

Osiris píše:
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 :(
Mocni si ty matice chytře, po mocninách dvojky:

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
Návštěvník

Re: zapocet 2008

Příspěvek od Návštěvník »

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:

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.

Odpovědět

Zpět na „PRM044 Programování I“