Matematické Fórum

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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 13. 03. 2018 14:35

awatar
Příspěvky: 129
Reputace:   
 

Optimalizačná úloha

Zdravím, prosím o overenie riešenia tejto úlohy, je možné prejsť po všetkých políčkach? Skúšal som to viacero krát ale vychádza mi 6 políčok nezafarbených. Aká je najvhodnejšia stratégia riešenia? Prípadne dá sa to naprogramovať a overiť softvérovo?Zadanie úlohy:



Máme tabuľku 7 × 7. Do všetkých políčok okrem jedného napíšeme číslo od 1 do 6 a šípku v jednom z 8 smerov, pričom každá možná dvojica šípka + číslo tam bude práve raz. Potom do ľavého horného rohu položíme figúrku a spravíme s ňou ľubovoľne veľa ťahov. Jeden ťah prebieha takto:
1. Zafarbíme políčko, na ktorom figúrka stojí.
2. Pohneme figúrku o toľko políčok, aké je na políčku číslo a v smere, ktorým ukazuje šípka.
Hra sa končí v momente, keď sa figúrka dostane na políčko, do ktorého sme nenapísali číslo ani šípku. Figúrka sa nikdy nemôže ocitnúť mimo hracieho plánu alebo na políčku, ktoré je už zafarbené. Spočítame, koľko políčok je zafarbených (nerátajúc posledné políčko) a to je naše skóre. Nájdite také rozloženie, kde sa dá získať čo najväčšie skóre.


Ďakujem vopred za pomoc.

Offline

 

#2 13. 03. 2018 17:34

awatar
Příspěvky: 129
Reputace:   
 

Re: Optimalizačná úloha

Prikladám aj jedno z riešení ale podľa mňa to nie je dobre

http://forum.matematika.cz/upload3/img/2018-03/58871_65634DC0-19D4-4DCB-96DE-D310C660683B.jpeg

Offline

 

#3 13. 03. 2018 19:46 — Editoval laszky (13. 03. 2018 20:18)

laszky
Příspěvky: 1045
Škola: MFF UK, FJFI CVUT
Reputace:   73 
 

Re: Optimalizačná úloha

Ahoj, pokud chces najit nejlepsi reseni, musis pouzit tzv. rainbow matching (duhove parovani) z teorie grafu. Sestavis si bipartitni graf (tvoren dvema mnozinami vrcholu=bodu, vrcholy v mnozine nejsou spojeny). Jedna mnozina bude mit 49 vrcholu a budou ji tvorit policka tabulky, druha mnozina bude mit 6x8=48 vrcholu a budou ji tvorit pripustne tahy. Mezi vrcholy bude hrana (budou spojeny) pokud je z nejakeho mista tabulky mozne pouzit dany tah. Pokud bys ted hledal maximalni parovani v bipartitnim grafu, mohlo by se stat, ze vyberes nektere hrany, ktere odpovidaji tahu koncicimu ve stejnem miste tabulky. Tomu zamezis tak, ze hrany grafu obarvis 49 barvami, podle toho, kde odpovidajici tah konci. Napr hrany [(3,3),1 vpravo], [(3,6), 2 vlevo] a [(6,4), 3 nahoru]  budou mit stejnou barvu. Cilem je nalezt maximalni parovani v bipartitnim grafu, ktere je tvorene hranami, jez maji ruzne barvy. ;-)

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson