Staonův svět - Zapocet C/C++

Zapocet C/C++ – 9.6.2006

Tak sem dneska zase uspesne neco zmrvil. Ale muze za to i to debilni skolni visual studio, na kterym sem se asi trictvrte hodiny snazil neuspesne rozchodit nacitani ze souboru (a fakt si myslim, ze sem to mel napsany spravne). Ale stejne sem moc nevedel, jak to resit :o)

Zadani:
Mate orientovany graf zadany seznamem nasledovniku ve tvaru:
uzel1:uzel2,uzel3
uzel2:uzel1
uzel3:

Za dvojteckou jsou ti nasledovnici oddelni carkou. Poradi uzlu i poradi nasledovniku je lexikograficky usporadane. A ma se udelat doplnek grafu. Ale aby to bylo tezky, tak nazev uzlu i pocet uzlu neni omezeny.

Co s tim? Udelat spojak spojaku a pak to nejak projizdet nebo co?

Pavel


Tak ja neviem, zas až také to nebolo, teda s použitím c++ stringov, ktoré našťastie povolené bolo :-), keď tie názvy uzlov nemali mať obmedzenú dĺžku. :-(

Graf som mal reprezentovaný spojákom štruktúr, kde bol jeden string názov_vrcholu a druhý string ,názvy_následníkov, a samozrejme pointer na ďalšieho. Môj algoritmus na doplnok grafu bol O(N^2), veď komu by sa to v danej chvíli chcelo robiť rozumnejšie :-). Pre jeden cyklus po spojáku vrcholov bežal druhý cyklus, ktorý vyhľadal daný názov vrcholu v stringu názvy_následníkov toho vrcholu, akurát trebalo hľadať čiarkanázovčiarka, aby som nenašiel niečo iné. A to bolo hádam všetko.

Tomu chalanovi to stačilo, vyzeral byť celkom v pohode. Povedal, že máme čas 2 a pol hodiny, ale čo bolo potom, neviem, lebo som odišiel ako prvý po hodine a pol.

Jaj a ešte parametre príkazového riadku: program(.exe) [-ivstup] [-ovýstup] tie boli nepovinné, bez nich sa berie zo štandartného i/o

PeterP

Matfyz | 9.6.2006 Pá 12:37 | <<< trvalý odkaz >>> | tisk | 3 komentáře

Komentáře k textu

Rss komentářů tohoto textu

[1] reaguj
Tass 9.6.2006 Pá 13:38

To se nám daří, co? Napoprvé to udělal jen Ondra :-). Snad příště…

[2] reaguj
Tiboh 9.6.2006 Pá 13:49

[1] Tass : No jo :o) Tak jeste aby to Ondra neudelal :o) To doufam, ze priste. Kdyz mam zkousku, tak neudelat zapocet by nastvalo… :o)

[3] reaguj
Staon mejl web 9.6.2006 Pá 19:05

[2] Tiboh : to by ani moc nenaštvalo, protože zkoušku ti příští rok rovnou uznají :)

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Kolik je 3 x 5?
Odpověd: nevím, ale násobení na reálných číslech tvoří komutativní grupu. 237

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).