Fórum studentů MFF UK

Ahoj Navstevnik!
Velmi pekne Ti dakujem za ten super navod, velmi mi to pomohlo. :)

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.

Vysvetlim to na prikladu celych cisel, jsi-li chytry matfyzak, bude pro tebe prevedeni na matice brnkacka.

Uvažte tento postup hledání 2[sup]15[/sup]:

2[sup]15[/sup] =
= (1)*2[sup]15[/sup]
= (2)*2[sup]14[/sup]
= (2)*4[sup]7[/sup]
= (2*4)*4[sup]6[/sup]
= (2*4)*16[sup]3[/sup]
= (2*4*16)*16[sup]2[/sup]
= (2*4*16)*256[sup]1[/sup]
= (2*4*16*256) = 32768.

V každém okamžiku se dá výsledek zapsat jako prubezny_vysledek*zaklad[sup]zbyva[/sup], 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. 2[sup]15[/sup]), 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:
x[sup]n[/sup] = prubezny_vysledek*zaklad[sup]zbyva[/sup]
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í 2[sup]15[/sup]).

Kód programu, který řeší daný problém:

[code]

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.

[/code]

[quote="Osiris"][quote="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 :([/quote]

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[/quote]


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

[quote="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 :([/quote]

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

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

[quote="quark87"]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???
[/quote]

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.

[quote="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).[/quote]

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 [u]potom[/u] co najviac nekritickych. Ale tvoje riesenie toho rozsireneho znie celkom rozumne.

. . x . .
. . o . .
. . . . .

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])
[code]
. . x . .
. . o . .
. . . . .
[/code]

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.

[quote="hippies"]muj tip podle nazvu je umistit damu tak, aby napadala co nejvic policek:) .. ale vazne je to jen tip[/quote]

A ako by sa to malo riesit??? :shock:

muj tip podle nazvu je umistit damu tak, aby napadala co nejvic policek:) .. ale vazne je to jen tip

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!

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)

[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

Ahoj, ja som mal tiez krvnu banku cize mozem napisat, ako to cca islo.

[line][/line]
[u][b]Zadanie[/b][/u]:

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:
[list]- kritickych (ktori zomru ak im netransplantujeme krv)
- nekritickych (to su ti ostatni)[/list]
(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:
[list] - 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.[/list]
ii) Potom sa transplantuje krv nekritickym:
[list] - zase treba transplantovat najviac, ako ide
- pacient moze dostat len rovnaku krv, aku ma (nemoze sa "miesat")[/list]
[line][/line]

[u][b]Riesenie[/b][/u]:
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-):

[code][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
[/code]

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.

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!

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.
[attachment=0]test.zip[/attachment]
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.