Čokoláda – Delphi – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Čokoláda – Delphi – Fórum – Programujte.comČokoláda – Delphi – Fórum – Programujte.com

 

Luky10
~ Anonymní uživatel
2 příspěvky
26. 8. 2010   #1
-
0
-

Dobrý den, chtěl bych váš poprosit o nějaký nápad (kód), pro tuto zákeřnou úlohu:

Je dána čokoláda o rozměrech 3xN čtverečků. Čokoláda má na některých čtvereččích umístěnu hrozinku. V zadání je dáno číslo N ("délka čokolády") a souřadnice [x;y] políček s hrozinkami. Určete počet způsobů, kolika můžeme rozdělit čokoládu na obdélníky 1x2, aby žádný z obdélníků neobsahoval hrozinku a tak byla čokoláda rozdělena na bezhrozinkové obdélníky 2x1 a čtverečky 1x1 s hrozinkou.

K zadání byl přiložen tento obrázek:



A jeho řešení: Pro čokoládu vlevo je 0 možností a pro čokoládu vpravo 3 možnosti.

Zkoušel jsem vyřešit případy, kdyby čokoláda hrozinky neobsahovala, a to pro N=2 a N=3. Přišel jsem na to, že pro případ N=2 jsou 3 možnosti a pro N=3 je 0 možností (je lichý počet políček, tak jedno vždy zbyde). Můj závěr pro čokoládu bez hrozinek je 3^(N/2) možností pro sudé N a 0 možností pro každé liché N. Bohužel ale nevím jak vytvořit algoritmus, který by to zjistil i pro čokoládu s hrozinkami :(.

Už jsem se ptal na konkurenčním fóru, bohužel nikdo mi nedokázal odpovědět a s problémem si nevěděli rady. Děkuji za případné odpovědi a doufám, že jste tu větší machři než na jiném nejmenovaném fóru.

Nahlásit jako SPAM
IP: 94.136.50.–
RePRO0
Super člen
26. 8. 2010   #2
-
0
-

>> bipartitní graf

Nahlásit jako SPAM
IP: 83.240.104.–
Software: C; C++; C#; Pascal; Delphi; Java Webdesign: PHP; MySQL; CSS; jQuery; Ajax; Javascript; OOP
Luky10
~ Anonymní uživatel
2 příspěvky
26. 8. 2010   #3
-
0
-

Vím přibližně o jaký typ grafu se jedná, bohužel to neumím implementovat do kódu, jelikož jsem s ním nikdy nezacházel.

Nahlásit jako SPAM
IP: 82.150.169.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 4 hosté

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý