Třetí série třináctého ročníku KSP

Řešení úloh

13-3-1 Hip hop (Zadání)

A jak to všechno dopadlo? Vašek i s jeho hrou by byl asi spokojen, protože větsina z vás napsala funkční program. Samozřejmě se našli i tací, jejichž řešení by mu spíše zamotala hlavu a nebo, kterých by se už pro malé hrací plány ve svém životě nedočkal.

Většina z vás tento problém řešila tzv. Dijkstrovým algoritmem, který je v tomto případě ve své standarní podobě spíše pověstným kanónem na vrabce.

A teď již k našemu algoritmu. Nejprve načteme na vstupu N vrcholů a M hran. Protože víme, že délka těchto hran je přirozené číslo menší nebo rovné dvanácti, můžeme každou hranu rozdělit na tolik hran, kolik je její délka. Tak nám vznikne neohodnocený graf. Na tento graf již můžeme použít algoritmus prohledávání do šířky, který všichni jistě dobře znáte.

Algoritmus má časovou i paměťovou složitost O(N+M).

Poznámka pro chytré hlavy: Pokud by konstanta omezující délku hrany byla větší, není toto řešení moc praktické, protože pro omezení d se paměťová složitost zvětší d-krát. Na tento případ lze s úspěchem použít modifikaci Dijkstrova algoritmu, kde se místo obvyklé haldy na dosud nezpracované vrcholy vhodně použije pole velikosti d (všimněte si, že při omezení délky hrany na d se bude vzdálenost libovolných dvou dosažených ale dosud nezpracovaných vrcholů lišit nejvýše o d).

Program

Tomáš Vyskočil

13-3-2 Fairies rights (Zadání)

Jak jeden z našich řešitelů konstatoval: je to jednoduchá dynamika. Budeme počítat cenu převodu prvních k písmen originálu na prvních l písmen výtisku (označme si ji c[k,l]). Je-li k-té písmeno originálu shodné s l-tým písmenem výtisku, je tato cena c[k-1,l-1] (k-té písmeno necháme beze změny). Jinak můžeme tento převod provést jedním z těchto způsobů:

Z těchto možností si vybereme tu nejlepší (tj. s minimální cenou). Pro výpočet c[k,l] tedy potřebujeme znát pouze c[k-1,l], c[k-1,l-1] a c[k,l-1], budeme-li při výpočtu postupovat ve vhodném pořadí (např. po řádcích matice c), budeme je už ve chvíli zjišťování c[k,l] znát. Hledanou cenu na konci snadno zjistíme jako c[M,N], kde M je délka originálu, N délka výtisku. Správnost algoritmu je zřejmá z popisu. Algoritmus je konečný, neboť nepoužívá žádné netriviální cykly.

Kdybychom chtěli znát pouze cenu převodu, stačilo by nám ukládat si pouze aktuální řádek a dosáhli bychom lineární paměťové složitosti. Chceme však také vědět, jakým způsobem jsme této ceny dosáhli. Budeme si tedy navíc ukládat, kterou z možností jsme si zvolili, a paměťová složitost tedy bude O(MN).

Na výpočet jednoho prvku c potřebujeme konstantní počet akcí, tedy časová složitost bude dohromady také O(MN).

Program

Zdeněk Dvořák

13-3-3 Konvertor (Zadání)

Tato úloha se řadí bezesporu mezi ty techničtější v našem semináři. V zadání úlohy nikde nebylo řečeno, že převáděné číslo je natolik malé, že ho lze uložit do standartního číselného typu v pascalu či céčku. Proto jsem řešení, která byla založena na tom, že si převáděné číslo uložila do proměnné, ohodnotil nejvýše 9 body.

Pokud přijmeme omezení, že převáděné číslo nelze uložit do proměnné, nezbývá nic jiného, než si naprogramovat několik procedur pro práci s dlouhými čísly. Zkusme si rozmyslet, jak by vypadala procedura, která sečte dvě čísla v soustavě o základu z. Algoritmus pro z>0 zná jistě většina z vás: Nechť A=an… a1a0 a B=bn… b1b0 jsou sčítaná čísla. První cifra výsledku bude v0=(a0+b0) mod z a přenos (kolik musíme přičíst k další cifře) bude c0=(a0+b0)/ z. Obecně vi=(ai+bi+ci-1) mod z a ci=(ai+bi+ci-1)/ z. Jak se situace změní, když bude z<0? Přenos ci se nebude k součtu následujících cifer přičítat, ale odčítat (a to pro i sudé i liché). Tedy vi=(ai+bi-ci-1) mod |z| a ci=(ai+bi+ci-1)/ |z|; zde by stálo zato podotknout, že a mod b v předchozím vzorečku je vždy číslo mezi 0 a b-1 (a to i pro a záporné) a a/ b je největší celé číslo menší než a/b. Podrobný důkaz těchto formulek je snadné cvičení na matematickou indukci. Povšimněte si, že naše vzorečky jdou snadno zobecnit na přičtení čísla α·B (α je nezáporné celé číslo uložitelné do proměnné) k číslu A:

Pro z>0:

vi=(ai+αbi+ci-1) mod z
ci=(ai+αbi+ci-1)/ z

Pro z<0:

vi=(ai+αbi-ci-1) mod |z|
ci=(ai+αbi-ci-1)/ |z|

Časová složitost přičtení (malého) násobku jednoho čísla k druhému je pak lineární v délce výsledného součtu.

Zbývá tedy dořešit problém, jak využít právě popsaný algoritmus k převodu mezi různými soustavami. Nechť máme číslo A=an… a0 v soustavě o základu z a chceme ho převést na A' do soustavy o základu z'. Nechť Zi je číslo zi vyjádřené v soustavě o základu z'. Pak A'=(anz2+an-1z)Zn-2+… +(a2z2+a1z)Z0+a0Z0. Pokud by všechny výrazy (anz2+an-1z),… ,(a2z2+a1z) byly nezáporné, byli bychom hotovi: Nejprve bychom k nule přičetli a0-násobek čísla Z0, potom k takto získanému výsledku (a2z2+a1z)-násobek Z0, k tomuto součtu (a4z2+a3z)-násobek Z2 atd. Pokud známe Zi, pak Z2i snadno spočteme jako z2-násobek Zi. Časová složitost takto navrženého algoritmu je kvadratická v délce zadaných čísel – počet kroků je lineární a časová složitost každého kroku je též lineární. Bohužel svět není takto jednoduchý a může se stát, že například d=(a2z2+a1z) je záporné číslo. Potom místo d-násobku přičteme (|z|3+a2z2+a1z) (což bude jistě nezáporné číslo) a v následujícím kroku přičteme místo (a4z2+a3z)-násobku Z2, (a4z2+a3z+z)-násobek. Vzhledem k tomu, že A je kladné, nebude toto přesouvání zápornosti nekonečné. Tím je popis našeho algoritmu ukončen.

Program se drží výše uvedeného postupu. Procedura nacti, resp. vypis, načte, resp. vypíše, číslo uložené v typu cislo. Procedura pricti_nasobek implementuje přičítání násobku tak, jak je popsané v druhém odstavci. Procedura convert provádí konverzi tak, jak je popsaná ve třetím odstavci. V proměnné rad si pamatujeme postupně hodnoty Z0,Z2,… , v proměnné nove pak součty po jednotlivých krocích.

Program

Dan Kráľ

13-3-4 Šťastná čísla (Zadání)

Pro tentokrát byli zlí skřítkové radílkové obzvláště potměšilí a rozdělili řešitele na dva zcela odlišné typy.

Zatímco prví se šťourají pouze ve svých „šč“, druzí studují ve svém entuziasmu každé číslo na šťasnost - potměšilost spočívá v tom, že „šč“ jsou rozmístěna na číselné ose velmi řídce a my musíme zkoumat exponenciální počet číslíček (a to věčně věkův), což nadšení nejednoho človíčka pochroumá, stejně tak jako pana Una, kterýžto ve své zběsilé honbě za čísly nemá pro podobné výstřednosti pochopení.

Vydáme se proto ve stopách prvých.

Dohoda: Píšu-li číslo, myslím tím šťastné číslo.

Šťastná čísla budeme postupně ukládat do fronty. Uvažujme první verzi algoritmu: Jsme ve frontě u čísla k (stanovme první k=1). Na konec fronty dáme všechna další čísla, která vzniknou jako k·3, k·7, k·11 (def. „šč“). Přesuneme se k dalšímu číslu ve frontě a opakujeme tentýž postup. Nejprve nahlédněme, že tímto postupem nagenerujeme libovolné číslo v konečném počtu kroků (Sporem). Problém zde spočívá v tom, že budeme zbytečně generovat mnoho vysokých čísel, která nebudou ve výsledku vůbec třeba, krom toho nebudeme vědět kdy přestat atp. Tomu se vyhneme vzestupným generováním čísel – tj. v každém kroku dostaneme vždy nejmenší možné číslo, které jsme dosud nenalezli (po n krocích budeme proto mít požadovaných n šťastných čísel). Tím odstraníme náš problém, který vznikl např. tím, že jsme číslo 11·k zařadili do fronty dříve než 3·3·k.

Elegantní způsob, jak čísla vzestupně generovat, využívá tří ukazatelů p3, p7, p11. Ty ukazují na nejmenší taková čísla, že 3·fronta[p3]>k, 7·fronta[p7]>k, 11·fronta[p11]>k. Na konec fronty pak připojím nejmenší z čísel i·fronta[pi], i∈{3,7,11}.

Poslední detail – mohlo by se stát, že nějaké číslo vygenerujeme dvakrát (fronta[p3]=3x-1·7y·11z, fronta[p7]=3x·7y-1·11z). Musíme tedy při generování každého čísla zkontrolovat, jestli nevznikne i při vynásobení čísel, na která ukazují ostatní ukazatelé a v tom případě inkrementovat i tato pi.

Odhad složitostí: Časová složitost bude lineární vzhledem k počtu hledaných šťastných čísel. Paměťová složitost našeho programu je taktéž lineární.

Opravdová legračina začíná v okamžiku, kdy si všimneme, že čísla, která byla vynásobena 3, 7 i 11 už nikdy během výpočtu nebudou třeba – mohli bychom je zapomínat (implementace např. dynamickým seznamem).

Otázka, jaká by byla paměťová složitost nyní, pana Una velmi rozrušila (zjistil totiž mystickou souvislost s jeho teorií šťastných čísel – víc mu žel vědomo není). Rozhodl se proto vykonat Vám návštěvu a vyškemrat nové rady. Za důkaz paměťové složitosti (zajímal by nás její co nejlepší jak horní, tak dolní odhad) je možno získat až 4 body.

Program

Pavel Šanda

13-3-5 LISP (Zadání)

a)  Na funkci Map nebylo opravdu nic těžkého – stačilo si uvědomit, že v LISPu lze funkce předávat jako cokoliv jiného a místo pevného jména volané funkce drze napsat proměnnou. A pak použít už několikrát popisované rekurzivní procházení seznamů:

   (define (Map f l)
     (if l
       (cons (f (geta l)) (Map f (getb l)))
       nil
     ))

Tento program má lineární časovou i paměťovou složitost (ovšem nepočítaje v to funkci f), a to je evidentně nejlepší možné.

b)  Prohledávání stromu do šířky se ukázalo být poněkud zapeklitějším. Náš vzorový řešitel mohl uvažovat třeba takhle: Prohledávání do šírky, to se přeci odjakživa dělalo pomocí fronty, ve které se schovávaly už nalezené, ale ještě nezpracované vrcholy – prostě se začalo s kořenem a v každém kroku se odebral první vrchol z fronty a na konec se přihodili jeho synové. Hmmm, fronta … to je přeci seznam, takže věc dočista lispovská, že lispovštější si snad už ani nejde představit. Aha, ale jak přidávat na konec seznamu bez toho, abychom ho pokaždé museli znovu hledat? Co na tom, tak si budeme pamatovat, kde končí. A tak se zrodilo následující řešení:

   (define (append last v)
     (if v
       (block
          (setb last (list v))
          (getb last))
       last))

   (define (BFS2 last first)
     (if first           ; fronta není prázdná
       (let ((v (geta first))      ; vrchol
             (w (geta v))          ; hodnota
             (l (geta (getb v)))   ; levý syn
             (r (getb (getb v))))  ; pravý syn
         (cons w
           (BFS2
              (append (append last l) r)
              (getb first))))
       nil))

   (define (BFS t)
     (let ((q (list t))) (BFS2 q q)))

Funkce BFS založí jednoprvkovou frontu obsahující kořen stromu t a předá řízení funkci BFS2, která provádí samotné prohledávání a předává si přitom dva parametry: first ukazující na počátek fronty a last ukazující na konec. Pokud fronta ještě není prázdná, odebere z ní první vrchol v a vrátí seznam obsahující hodnotu tohoto vrcholu připojenou před výsledek téže funkce rekurzivně zavolané na frontu, do níž jsme zavoláním funkce append přidali syny vrcholu v a samotný vrchol v odebrali (na tomto místě se dopouštíme drobné podlosti: využíváme toho, že se argumenty funkce vyhodnocují zleva doprava a schválně předáváme nejdříve last a pak teprve first, takže nejdříve vrcholy přidáváme a pak teprve odebíráme, tudíž se nám fronta nemůže před koncem výpočtu nikdy ani na chvilku vyprázdnit, a tak v append nemusíme ošetřovat přidávání k prázdné frontě).

Co dodat? Snad jen to, že časová i paměťová složitost jsou lineární, že rekurze je nejlepším přítelem programátora a že venku nádherně svítí měsíc.

Martin Mareš