Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Ahoj, mám naprogramované řešení prohledáváním do hloubky. Otázka zní jak vhodně prořezávat větve abych program zrychlil.
Mám zatím jednu optimalizaci: Pokud jsem v manhattanské normě dále od startu než je zbývající počet kostek, tak větev už neprohledávám.
Teď mne ještě napadlo, že nemusím řešit případ kdy nemám 4 "kolena" a uzavřený okruh tedy nelze vytvořit.
Nějaké další nápady? Případně třeba nějak zcela alternativně to řešit? vůbec neprohledávat do hloubky?
EDIT> našel jsem nějaké (správné?) řešení zde:
https://github.com/svecon/basic-csharp- … 07_vlak.cs
tu železnici to vůbec nekontsruje, jen provádí analýzu možnosti délky trasy
Zadání je
Stavebnice obsahuje čtvercové kostičky stejné velikosti s obrázky kolejí.
Na každé kostičce je vyobrazen jeden úsek spojující dvě strany kostičky.
Kostičky nelze otáčet, takže existuje celkem šest druhů kostiček, podle toho, které strany kostičky úsek koleje spojuje:
levá-pravá
horní-dolní
levá-horní
levá-dolní
pravá-horní
pravá-dolní
Napište program, který pro dané kostičky zjistí délku nejdelší uzavřené trati, kterou z nich lze sestavit. Trať se nesmí nikde křížit.
Vstup: Šest čísel udávajících počty kostiček typů levá-pravá, horní-dolní, levá-horní, levá-dolní, pravá-horní, pravá-dolní, v tomto pořadí.
Čísla jsou v rozsahu 0..100.
Výstup: Délka nejdelší uzavřené trati, kterou lze z daných kostiček sestavit.
Například pro vstup
3 0 1 2 1 1
bude výstup 6 odpovídající trati
+- -- -+
| |
| |
+- -- -+
, dvě kostičky v tomto případě zůstanou nevyužity.Offline
Stránky: 1