navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha2-2013 [2013/10/07 11:11] milanec |
courses:a4m33pal:uloha2-2013 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 3: | Řádek 3: | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
| Ja to treba delal tak, ze mam algoritmus na hledani nejmensi kostry - Kruskal (hrany ulozene v ArrayListu). Vedle toho mam int[pocetVrcholu] pole, ktere obsahuje pocet stupnu jednotlivych vrcholu. Pak si z mnoziny A vyberu vsechny kombinace K-tic - pro example na strankach zadani (12,13,16,23,26,36) a ulozim do ArrayListu. Ty mi znaci, ktere z tech hran budou mit stupen 1 pri hledani kostry. | Ja to treba delal tak, ze mam algoritmus na hledani nejmensi kostry - Kruskal (hrany ulozene v ArrayListu). Vedle toho mam int[pocetVrcholu] pole, ktere obsahuje pocet stupnu jednotlivych vrcholu. Pak si z mnoziny A vyberu vsechny kombinace K-tic - pro example na strankach zadani (12,13,16,23,26,36) a ulozim do ArrayListu. Ty mi znaci, ktere z tech hran budou mit stupen 1 pri hledani kostry. | ||
| - | vysledek = maxInt | + | * Nečíslovaný seznamvysledek = maxInt |
| * while (mamNejakeKombinace K-tic) { | * while (mamNejakeKombinace K-tic) { | ||
| * - vyndej jednu K-tici k | * - vyndej jednu K-tici k | ||
| * - hledej kostru, pro vrcholy z k tak, ze do vrcholu z k povede jen jedna hrana (logicky ta nejlevnejsi) | * - hledej kostru, pro vrcholy z k tak, ze do vrcholu z k povede jen jedna hrana (logicky ta nejlevnejsi) | ||
| - | * - do kostry nepridavej hrany mezi vrcholy A | + | * * - do kostry nepridavej hrany mezi vrcholy A |
| * - uloz vysledek, pokud je nizsi | * - uloz vysledek, pokud je nizsi | ||
| * } | * } | ||
| Řádek 14: | Řádek 14: | ||
| 10/10 | 10/10 | ||
| + | |||
| + | ---- | ||
| + | |||
| + | By bilymare: | ||
| + | Jak myslíš to nepřidávej do kostry hrany mezi vrcholy z A... vždyt někdy tam hrany být mohou? | ||
| + | --- //[[[email protected]|Marek Bílý]] 2013/10/08 19:22// | ||
| + | |||
| + | By vlcekvl2: | ||
| + | Podle mě má zde autor na mysli nepřidávat hrany mezi vybranou K-ticí k vrcholů. Poté by totiž nebylo možné vytvořit souvislý graf (což kostra musí být), jelikož tyto vrcholy mohou být maximálně stupně jedna. | ||
| + | |||
| + | |||
| + | By roziana: | ||
| + | chci se jen zeptat, jak vytvorit k-tici kombinaci z mnoziny A? | ||
| + | |||
| + | By milanec: | ||
| + | jo, přesně, nepřidávat mezi tou K-ticí .. to jsem se přepsal :) Na výběr K-tice z množiny A si musíš vymyslet nějaký šikovný algoritmus, nebo, jako já, najít si něco na netu a přizpůsobit si to svým potřebám :P | ||
| + | |||
| + | By bilymare: | ||
| + | - A na co máš to pole stupnů vrcholů? | ||
| + | - já to napsal celé dost objektově. a mám 6 z 10 (3 neustíhám a 1 je špatně). | ||
| + | - mám ještě dotaz nepřeteče cena přes velikost intu? | ||
| + | - implementoval si union-find stromově nebo projíždíš to pole lineárně? | ||
| + | ........ Díky --- //[[[email protected]|Marek Bílý]] 2013/10/09 21:01// | ||
| + | |||
| + | By milanec: | ||
| + | Pole stupňů vrcholů mi pomáhá zjišťovat, jestli jsem u té K-tice nepřekročil jejich stupeň. Velikost intu mi nepřetekla a union find jsem měl polem :) | ||
