navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:zkouska2014_4 [2014/01/24 16:27] pm vytvořeno |
courses:a4m33pal:zkouska2014_4 [2025/01/03 18:29] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | Zadání: http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=isomers2 | + | Zadání: http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=isomers2 "Acyclic Isomers" |
| + | |||
| + | Zadání je stejné jako u jedné zkouškové úlohy loni, až na to, že N může mít 3 nebo 5 vazeb, ne jen 3 vazby. | ||
| + | |||
| + | Vstupem je chemický vzorec, např. "C2H2N2O2", výstupem je počet acyklických izomerů splňující tento vzorec. Jde o počet všech navzájem izomorfních grafů (dokonce stromů, protože tam nejsou cykly), kde jsou uzly označeny jako C, N, O nebo H a mají takový stupeň, kolik ten prvek má vazeb (C 4 vazby, H 1, O 2, N 3 nebo 5). | ||
| Řešil bych to nějak takhle: https://gist.github.com/messa/68a04aac63e092da0d09 | Řešil bych to nějak takhle: https://gist.github.com/messa/68a04aac63e092da0d09 | ||
| + | |||
| + | Postup: | ||
| + | |||
| + | - Generování stromů, které splňují vstup | ||
| + | - Vytvořit certifikát stromu, pokud není unikátní, přeskočit strom. Toto lze už během generování, tím se významně sníží počet generovaných stromů. | ||
| + | - Vypsat počet stromů | ||
| + | |||
| + | |||
| + | ---- | ||
| + | |||
| + | S kamarádem jsme to diskutovali a navrhoval bych jiné řešení. Není ověřené, ale má myšlenku. V každém stromě můžeme nalézt jeden či dva uzly, které mají největší hloubku. Tím pádem můžeme začít od tohoto "kořene" a navěšovat na něj podstromy patřičných velikostí. Je to potřeba dobře promyslet, protože na pořadí navěšených podstromů nezáleží. Certifikáty je potřeba porovnávat pouze u těchto podstromů a to bude značně jednodušší a je možno to také dělat při generování. Mělo by to být efektivnější než přímé generování všech možných stromů. | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
