navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha3-2013 [2013/10/13 23:24] milanec |
courses:a4m33pal:uloha3-2013 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 12: | Řádek 12: | ||
| By stradja3: Udělal jsem to pomocí té rekurze s tím, že když je to orientovaný graf tak si neustále aktualizuju vstupní a výstupní stupně pro každý uzel, abych náhodou předčasně nevlezl do koncového uzlu (který má výstupní stupeň 0). A funguje to. Problém je, že mi to počítá pomalu - pouze 5/10. Jakým způsobem se to udělá přes ty spojové seznamy? | By stradja3: Udělal jsem to pomocí té rekurze s tím, že když je to orientovaný graf tak si neustále aktualizuju vstupní a výstupní stupně pro každý uzel, abych náhodou předčasně nevlezl do koncového uzlu (který má výstupní stupeň 0). A funguje to. Problém je, že mi to počítá pomalu - pouze 5/10. Jakým způsobem se to udělá přes ty spojové seznamy? | ||
| - | By milanec: Já mám vrchol - ten má nějaké číslo a linkedList čísel vrcholů, do kterých má orientovanout hranu (tzn. vedou-li z vrcholu 2 do vrcholu dvě hrany do 4, jedna do 1 a jedna do 2, má linked list hodnoty - 4,4,1,0. Find mám stejný jako v přednáškách. Namísto push(new edge(from,to)) mám push(new int[]{from,to})... když jsem tam měl objekt, tak jsem těžce nestíhal. | + | By milanec: Já mám vrchol - ten má nějaké číslo a linkedList čísel vrcholů, do kterých má orientovanout hranu (tzn. vedou-li z vrcholu 2 do vrcholu dvě hrany do 4, jedna do 1 a jedna do 0, má linked list hodnoty - 4,4,1,0. Find mám stejný jako v přednáškách. Namísto push(new edge(from,to)) mám push(new int[]{from,to})... když jsem tam měl objekt, tak jsem těžce nestíhal. |
| --- //[[[email protected]|Milan Černil]] 2013/10/13 23:17// | --- //[[[email protected]|Milan Černil]] 2013/10/13 23:17// | ||
| + | |||
| + | By stradja3: A jak řešíš to, abys předčasně nevlezl do koncového uzlu, který má výstupní stupeň v danou chvíli 0 (pokud měl třeba 1 a už jsme ho jednou prošli)? Já to udělal podle tebe - mám u každého uzlu seznam následovníků a ty procházím do hloubky. Ale udržuju si informaci o výstupním stupni toho koncového uzlu. Když na něj narazím a ten stupeň je 0, tak ho v tom seznamu následovníků přesunu úplně na konec. Tím zaručím, že do něj vlezu až na závěr. Vypadá to jednoduše a jasně, jenže mi to u poloviny testovacích dat na webu hází špatné řešení nebo segmentation fault, takže tam mám nějakou chybu a nemůžu na ni přijít.. | ||
| + | |||
| + | By milanec: Máš teda 2 situace | ||
| + | * Buď sudé stupně u všeho - je jedno kde začneš | ||
| + | * 2 s lichým - musíš začít u toho, který má více výstupních vrcholů | ||
| + | Já to dělám tak, že při načítání u všech uzlů mám field stupeň. Pokud do něj vede hrana, přidám jedničku, pokud vychází hrana, odeberu 1. Tím pádem najdeš výchozí tím, že bude mít stupeň -1. Takže si pak projedeš všechny vrcholy a tím, že najdeš ten s -1, tak víš, že začneš prohledávat cestu od něj. Udržuji si i nějaký count, kolik jsem jich našel - když jich najdu víc, tak nemá řešení samozřejmě :) Pokud takový nemám, tak jedu klasicky odkud chci. A do toho druhého lichého to vleze samo :) | ||
| + | --- //[[[email protected]|Milan Černil]] 2013/10/15 00:12// | ||
| + | |||
| + | By stradja3: tak 9/10 :-( u test06 mám špatné řešení, nevím co tam je jinak oproti ostatním variantám. Píšou, že je to "random directed multigraph". Nicméně teď už to asi nedávám.. Kdyby se sem náhodou ještě někdo podíval - nevíte čím by to mohlo být? | ||
| + | |||
