Matematické Fórum

↑ case_fcs:
Ehm tak to sem z toho nejak jelen :) Chapu tak trochu co chces udelat ale vubec mi nejsou jasny ty tvoje priklady...
1)Dostanes dylku strany ctverce, coz musi byt mocnina 2
2)Dostanes souradnice volnyho policka... To pocitas od nuly nebo od 1???
3)Mas vygenerovat rozmisteni "obrazcu" tak aby se neprekryvaly... Ty obrazce maji byt co? To jsou jako ctverce nebo obdelniky nebo trojuhelniky???
4)Vystupem ma byt co? Souradnice vrcholu (u trojuhelnika), souradnice vrcholu na uhlopricce (u obdelnika, ctverce)???

↑ case_fcs:
Hele ten postup neni tezkej, nakreslil sem ti to tady na ctvereckovanej papir...



Vsimni si, ze v kazdym ctverci o dylce hrany 2^n kdyz do nej delas ty L-ka tak ti v kazdym zbyde 1 nevyplnenej bod. Kdyz mas 2x2 tak je to jasny.
Kdyz mas 4x4 tak to rozdelis na 4 mensi ctverce 2x2. V jednom mas tu diru, tam to je jasny, no a zbydou ti tam tri ctverce okolo o rozmerech 2x2.
Prvni L-ko udelas tak aby prochazelo vsema temahle trema 2x2 ctvercema. No a tim ziskas diru v kazdym z tech trech ctvercu a je pak jasny kam v kazdym tom ctverci 2x2 udelat L-ko.
No a takhle pokracujes dal...

Takze proste tu ctvercovou plochu si delis rekurzivne az do urovne 2x2. Nedelil bych to ale uplne hned do 2x2 a teprv pak neco chaosit...Proste takhle:
Rozdelis velkej ctverec na 4 mensi -> spojis tri ctverce, ktery v sobe nemaj zadnej bod Lkem
Rozdelis velkej ctverec na 4 mensi -> spojis tri ctverce, ktery v sobe nemaj zadnej bod Lkem
.
.
.
Mozna nekdo pride na neco lepsiho, ale tohle mi ted pripada jako nejlepsi postup

↑ case_fcs:
Ahoj ahoj,
hele abys moh něco začít psát tak tomu musíš nejdřív rozumnět a podle toho co píšeš mi je jasný, že v tom zatim dost plaveš. :)
Ten postup co sem ti ukazoval platí samozřejmě pro libovolnou velikost pole a libovolný umístění toho bodu. To, že sem tam nakreslil zrovna pole 16x16 je prostě proto, že mi to přišlo tak akorát aby se to na tom dobře ukazovalo a tu počáteční tečku sem prostě někam na začátku dal (je jedno kde je).
Vem si čtverečkovej papír, nakresli si nějaký to pole, někam si do něj dej tu počáteční tečku a zkus to udělat podle toho postupu jak sem ti psal v minulym příspěvku...
Zkusim ti to vysvětlit ještě jednou, nemám teď jak fotit tak to bude v Excelu...
Pole, který v tý rekurzivní funkci právě teď počítáš je vždycky zeleně
1)Na začátku si vezmu nějaký čtvercový pole s dýlkou hrany 2^n (zase si beru 16x16 aby se to dobře ukazovalo) a někam do něj dáš počáteční prázdný políčko - viz obr.1
2)V tý rekurzivní funkci se ptáš: jsou rozměry toho pole 2x2? -> ne momentálně sou 16x16
3)Rozdělíš to pole na čtvrtiny a zároveň dáš L-ko do těch sub-polí, ve kterých ještě není žádnej bod. Tohle je důležitý... viz obr.2
4)Zavoláš rekurzivně tu stejnou funkci pro to první sub pole 8x8.

A jede ti to znova od 2) pro pole velikosti 8x8 viz obr.3
Zas zjistíš, že pole neni velikosti 2x2 tak ho rozdělíš a tam kde neni žádnej bod dáš L-ko - obr.4 a voláš rekurzivně pro to první sub pole velikosti 4x4

Jede to znova od 2) pro pole velikosti 4x4 obr.5
Pole fůrt neni velikosti 2x2, dělíš a dáváš L-ko - obr.6 a voláš pro pole velikosti 2x2

Zas ti to jede od 2) pro pole velikosti 2x2 obr.7
Pole teď konečně je velikosti 2x2. Máš jedinou možnost kam vrazit to finální L-ko viz obr.8
Prima, teď máš vyplněnej první čtverec, rekurzivně se teď nic nevolá a pokračuje se k tomu druhýmu čtverci...
Ten má zas rozměry 2x2, zas jediná možnost kam vrazit to L-ko - obr.9
No a takhle ti to prostě pofrčí...

Obr. 1


Obr. 2


Obr. 3


Obr. 4


Obr. 5


Obr. 6


Obr. 7


Obr. 8


Obr. 9



No jinak co se týká toho jak to udělat programově... Nenapsal si v čem to máte programovat, ale to je skoro i jedno protože si to musíš stejně naprogramovat sám, programovat ti to tady nebudu :) To dělení toho pole jak sem o tom psal výš bych prostě udělal tak, že máš nějaký globální pole a hlavička tý funkce kdyby to bylo v javě by mohla vypadat takhle

void vyplnPole(int x, int y, int velikost)

kde x,y jsou prostě souřadnice levýho horního rohu toho čtverce, který teď počítěš a velikost je velikost toho čtverce.

↑ case_fcs:
Prima, takze ted ti je jasnej postup, ale nevis jak to napsat v tom Cecku?
Tak ja bych to udelal asi tak, ze bych mel jedno globalni pole int-u, ktery bude inicializovany treba na samy nuly. Do nej ulozis to volny misto. Ulozis to tam treba tak, ze na to misto das jednicku. Dal bych si udelal 4 dvojrozmerny pole kam budes ukladat souradnice tech L-ek. Prvni bude proste pole souradnic obrazcu typu A, dalsi pole souradnic obrazcu typu B, atd atd
Tohle myslim, ze by melo byt jasny, ok?

Jak delit ctverce na ctvrtiny?
Uplne jednoduse...udelal bych to nejak takhle:

void vyplnPole(int x, int y, int velikost){
.
.
.
vyplnPole(0,0,velikost/2);
vyplnPole(velikost/2,0,velikost/2);
vyplnPole(0,velikost/2,velikost/2);
vyplnPole(velikost/2,velikost/2,velikost/2);
.
.
.

}

x,y jsou souradnice levyho horniho ctverecku v tom ctverci...
Tohle je jasny?

Jak zjistis jestli je nejakej ctverec prazdnej?
Normalne proste projdes vsechny jeho prvky a kdyz v nem budou samy nuly tak je prazdnej. Nejlip si na to napsat nejakou pomocnou funkci, neco jako

boolean jePrazdny(int x, int y, int velikost)

bude ti to vracet true kdyz je to sub pole prazdny, vyznam parametru je stejnej jako v predchozi funkci. Tady to proste v nejakym for cyklu projdes...
Tohle to si budes muset zjistit pri kazdym tom deleni na 4 sub pole...Kdyz se na to podivas dobre tak zjistis, ze ti vzdycky u trech sub poli vyjde, ze sou prazdny a jedno, ze prazdny neni no a podle toho poznas jak bude to Lko natoceny.
Napr. ten druhej obrazek v predchozim prispevku - 1. 2. 3. kvadrant je prazdnej -> je jasny, ze tam bude L-ko typu D (beru to podle tech tvych obrazku). Ted se asi ptas jak zaznacis to L-ko do toho pole a jak s teme souradnicema...
Do toho globalniho pole, ktery delis proste na misto tech policek kde je L-ko das treba jednicky (na zacatku to pole je inicializovany na samy nuly) no a tim to odlisis kde je prazdny misto a kde ne. Dal je dulezity do toho globalniho pole kam ukladas souradnice typu D ulozit souradnici toho L-ka...

xxsawerův algoritmus je elegantní, ale jde to řešit i tak, že nejprve pomocí bloků

AA
AD
DD

pokryjeme trojice řádků, až nám zbude pás 8xn nebo 4xn. Z něj oddělíme bloky

AAD
ADD

a zbude nám buď čtverec 4x4 nebo 8x8 obsahující volné pole. Výhoda tohoto postupu je v tom, že nevyužívá tak masivně rekurzi -- na opravdu velkých polích by se to mohlo měřitelně projevit v rychlosti běhu. Navíc funguje pro pole obecné velikosti větší než 5 (nedělitelné třemi -- pokud 3|n, nemá úloha řešení).

↑ case_fcs:
Co konkrétně ti neni jasný?
Sepisovat to určitě nebudu protože si myslim, že de o to aby ses to naučila a navíc mam teď kopec jiných starostí, ale když nahodíš icq tak to můžem ještě probrat tam...