Forum » Šola » Matematični problem- mreža
Matematični problem- mreža
Buddah ::
Pozdravljeni,
ker je od mojih dnevov v šolskih klopeh (kar se tiče matematike) minilo že kar nekaj časa vas prosim za pomoč pri reševanju sledečega problema. Trenutno ga rešujem z "brute force" metodo, kar pomeni, da v excelu preverjam rešitve na roko. To mi seveda vzame precej časa zato me zanima ali je možna matematična rešitev, ki bi jo kasneje apliciral na različne velikosti mreže. Problem bom poizkusil opisati s pomočjo časovnih obdobij in grafičnim prikazom. Mreža, ki jo uporabljam v tem primeru je velika 11 x 11 polj.
Opis naloge/problema:
1. V času t0 imamo pred seboj sledečo sliko:
2. V času t1 se zgodi naslednje: polje označeno s št.1 se izprazni, zasedeta pa se 2 sosednji polji. Pogoj za premik na sosednji polji je da se vsa polja zasedejo po istem principu- ali LEVO-DESNO, ali GOR-DOL. Kombinacija LEVO-GOR ali LEVO-DOL itd. zaenkrat ni možna! Možna pa je kombinacija DIAGONALNO DESNO GOR-DIAGONALNO LEVO GOR ali pa celo DIAGONANO DESNO GOR-DIAGONALNO LEVO GOR. Prikazana je rešitev LEVO-DESNO.
3. V času t2 se zgodi naslednje: polji označeni s št.2 se izpraznita, zasedejo pa se 4 poleg ležeča polja (po 2 na vsaki strani). Ponovno morajo biti premiki na obeh straneh enaki (simetrični?). Torej na obeh straneh se mora zgoditi premik LEVO-DESNO ali pa GOR-DOL ipd. V tem primeru je prikazan premik GOR-DOL.
4. Rešitev, ki jo želim doseči je prikazana spodaj. To naj bi bil sedmi korak (2^7). Določena polja se bodo seveda podvojila glede zasedenosti saj je na mreži prostora le za 121 točk in ne 128. Pa vendar...kako bi izvedel čim lepšo prerazporeditev čez celotno mrežo? Ali obstaja neka univerzalna rešitev ali gre za step-by-step rešitev? Ali se da rešitev prilagoditi za 64 (6 korakov, 2^6 točk) polj oz. 256 (2^8 točk) polj?
Upam da je naloga jasno definirana in nisem izpustil kakšnih ključnih podatkov. V kolikor je mogoče prosim za čimbolj "simpl" razlago :)
Že v naprej se zahvaljujem vsem za pomoč!
Buddah
ker je od mojih dnevov v šolskih klopeh (kar se tiče matematike) minilo že kar nekaj časa vas prosim za pomoč pri reševanju sledečega problema. Trenutno ga rešujem z "brute force" metodo, kar pomeni, da v excelu preverjam rešitve na roko. To mi seveda vzame precej časa zato me zanima ali je možna matematična rešitev, ki bi jo kasneje apliciral na različne velikosti mreže. Problem bom poizkusil opisati s pomočjo časovnih obdobij in grafičnim prikazom. Mreža, ki jo uporabljam v tem primeru je velika 11 x 11 polj.
Opis naloge/problema:
1. V času t0 imamo pred seboj sledečo sliko:
2. V času t1 se zgodi naslednje: polje označeno s št.1 se izprazni, zasedeta pa se 2 sosednji polji. Pogoj za premik na sosednji polji je da se vsa polja zasedejo po istem principu- ali LEVO-DESNO, ali GOR-DOL. Kombinacija LEVO-GOR ali LEVO-DOL itd. zaenkrat ni možna! Možna pa je kombinacija DIAGONALNO DESNO GOR-DIAGONALNO LEVO GOR ali pa celo DIAGONANO DESNO GOR-DIAGONALNO LEVO GOR. Prikazana je rešitev LEVO-DESNO.
3. V času t2 se zgodi naslednje: polji označeni s št.2 se izpraznita, zasedejo pa se 4 poleg ležeča polja (po 2 na vsaki strani). Ponovno morajo biti premiki na obeh straneh enaki (simetrični?). Torej na obeh straneh se mora zgoditi premik LEVO-DESNO ali pa GOR-DOL ipd. V tem primeru je prikazan premik GOR-DOL.
4. Rešitev, ki jo želim doseči je prikazana spodaj. To naj bi bil sedmi korak (2^7). Določena polja se bodo seveda podvojila glede zasedenosti saj je na mreži prostora le za 121 točk in ne 128. Pa vendar...kako bi izvedel čim lepšo prerazporeditev čez celotno mrežo? Ali obstaja neka univerzalna rešitev ali gre za step-by-step rešitev? Ali se da rešitev prilagoditi za 64 (6 korakov, 2^6 točk) polj oz. 256 (2^8 točk) polj?
Upam da je naloga jasno definirana in nisem izpustil kakšnih ključnih podatkov. V kolikor je mogoče prosim za čimbolj "simpl" razlago :)
Že v naprej se zahvaljujem vsem za pomoč!
Buddah
- spremenil: Buddah ()
stapler rump ::
Tako kot razumem tvoja navodila imaš v vsakem koraku vedno lahko označena samo liha ali samo soda polja, tako da se zdi, da zadnja slika ni mogoča. Povedano drugače: zdi se nemogoče, da bi imel v enem koraku lahko označeni sosednji polji.
BRBR ::
Določena polja se bodo seveda podvojila glede zasedenosti
po moje je pač zadnja slika mogoča, če zgornji citat pomeni da na isto polje lahko prideš večrat, zraven tega na robu mreže ne moreš ven in moraš nazaj noter (manj možnosti, ampak greš v smeri zasedanja še nikoli zasedenih polj)
Brute force z excelom pač ni good, napiši si en program, magariu v java scriptu, tule maš en primer s katerim sem se enkrat ukvarjal:
igrica
Klik na random sivo polje (siva polja: random start, prverjanje random logčnih možnih naslednjih pozicij). Dovoljeni premiki kot konj pri šahu, samo po sivih poljih.
Če boš prišel dovolj daleč boš videl (kao javascript slowmotion) kako se na začetku 'plate' rišejo (računajo) logično pravilna polja. Vsaka stopnja je 100% rešljiva vsaj na 2 načina.
Da se bo pa čim lepše in čim hitreje zapolnilo - morda odkriješ kaj v teku programiranja.
Zgodovina sprememb…
- spremenil: BRBR ()
stapler rump ::
BRBR, lahko daš primer, kako bi dobil dve sosednji polji označeni v istem koraku?
Naloga, ki jo je opisal Buddah je drugačna od konjevega obhoda, ki ga omenjaš. Pri obhodu konja barvaš polja, ki si jih z konjem že obiskal.
Pri zadnji sliki v tem problemu so pa vsa polja hkrati zasedena v enem koraku. Vsaj tako jaz to razumem - v vseh poljih je "128", ne kombinacija "1", "2", "4" ... "128". Za kombinacijo je rešitev trivialna.
Naloga, ki jo je opisal Buddah je drugačna od konjevega obhoda, ki ga omenjaš. Pri obhodu konja barvaš polja, ki si jih z konjem že obiskal.
Pri zadnji sliki v tem problemu so pa vsa polja hkrati zasedena v enem koraku. Vsaj tako jaz to razumem - v vseh poljih je "128", ne kombinacija "1", "2", "4" ... "128". Za kombinacijo je rešitev trivialna.
maco-maco ::
Možna pa je kombinacija DIAGONALNO DESNO GOR-DIAGONALNO LEVO GOR ali pa celo DIAGONANO DESNO GOR-DIAGONALNO LEVO GOR.
A ni to isto?
Jaz bi pogledal iz končne pozicije, kaj je predzadnja možnost. Da bi zapolnil oba roba (vrh/dno ali levo/desno), je edina možnost, da si šel v zadnjem koraku dol/gor ali levo/desno. No, nevem, malo sem zbegan.
Kaj?
smacker ::
Lahko napišeš program, ki bo to rekurzivno reševal. Algoritem rahlo spominja na Flood Fill, ta se uporablja npr. v slikarju za barvanje ploskev. Link: Flood fill @ Wikipedia
Ni pa problem čisto enak, ker pri flood fillu si zapomniš že obiskana polja, pri tvojem primeru pa jih pozabiš.
Vidim eno trivialno rešitev:
- izvajaš polnitve v smeri gor-dol, dokler ne prideš do robov (zapolnil si en stolpec, porabil si toliko potez kot je od začetne točke do spodnjega/zgornjega roba - vzameš daljšo razdaljo.
- potem izvajaš polnitve v smeri levo-desno v vseh stolpcih, dokler ne prideš do vseh robov. Zapolniš vse vrstice, porabiš pa tolkio potez kot je od začetne točke do levega/desnega roba - vzameš spet daljšo razdaljo.
Zaradi večkratnih polnitev istih polj rešitev ni optimalna (dalo bi se rešit v manj korakih), si pa zagotoviš konstantno polnjenje že obiskanih polj.Problem pri tej nalogi je, da ko skočiš iz polja A v polji B in C, ostane polje A prazno. Torej bi v zadnjem koraku moral iz nekega četrtega polja D skočit v A. Pri tem bi spet D ostal prazen,....
Da bi to rešil kako drugače kot z brute force ne vidim, se pa da napisat program, ki brute-force izvede namesto tebe in ti samo izpiše rešitev - pogoj znanje programiranja.
Ni pa problem čisto enak, ker pri flood fillu si zapomniš že obiskana polja, pri tvojem primeru pa jih pozabiš.
Vidim eno trivialno rešitev:
- izvajaš polnitve v smeri gor-dol, dokler ne prideš do robov (zapolnil si en stolpec, porabil si toliko potez kot je od začetne točke do spodnjega/zgornjega roba - vzameš daljšo razdaljo.
- potem izvajaš polnitve v smeri levo-desno v vseh stolpcih, dokler ne prideš do vseh robov. Zapolniš vse vrstice, porabiš pa tolkio potez kot je od začetne točke do levega/desnega roba - vzameš spet daljšo razdaljo.
Zaradi večkratnih polnitev istih polj rešitev ni optimalna (dalo bi se rešit v manj korakih), si pa zagotoviš konstantno polnjenje že obiskanih polj.Problem pri tej nalogi je, da ko skočiš iz polja A v polji B in C, ostane polje A prazno. Torej bi v zadnjem koraku moral iz nekega četrtega polja D skočit v A. Pri tem bi spet D ostal prazen,....
Da bi to rešil kako drugače kot z brute force ne vidim, se pa da napisat program, ki brute-force izvede namesto tebe in ti samo izpiše rešitev - pogoj znanje programiranja.
maco-maco ::
Samo čim greš iz 1ke 2x levo/desno, prideš do tega, da prideta in leva in desna trojka na mesto, kjer si začel-1. A to se sme?
Kaj?
maco-maco ::
Sem razumel, da ne 2x v isti potezi, ampak posamično (npr. v koraku 2 in koraku 3). Je pa najbrž res, da če ne smeta se 2 delit v isti kvadratek, sploh ni rešitve.
Zato je pomembno, da OP razjasni, kakšne so možnosti diagonalne delitve.
Zato je pomembno, da OP razjasni, kakšne so možnosti diagonalne delitve.
Kaj?
Zgodovina sprememb…
- spremenilo: maco-maco ()
Buddah ::
OP (jaz) je idiot! Predvsem zato ker je slabo definiral problem in postavil napačne omejitve.
Velikost mreže ni poglavitnega pomena in se lahko poljubno spreminja (torej 11x11 ni omejitev).
Bom poizkusil še enkat definirati problem čeprav sem sedaj do neke rešitve že prišel. Uspelo mi je ko sem spremenil velikost mreže :):
Skratka imamo omejenen prostor (kvadrat...100x100cm). Začnemo "na sredini" mreže. Cilj, ki ga skušamo doseči je, da bi na koncu imeli 32/64/128 točk enakomerno razporejenih po celotnem prostoru. Mreža nam (meni) je le v pomoč. Točka na sredini je naš začetek. Ko pritisnem "START" se točka razdeli v "dva kraka". Te dva kraka sta vedno drug drugemu nasproti ležeča (lahko jih kasneje upognemo npr. diagonalno). Smer v katero sta obrnjena lahko izberemo. Recimo da sta na začeku obrnjena v smeri GOR-DOL. Za ponazoritev vzemimo da sta kraka dolga 1cm. Če bi želeli ustvariti situacijo GOR-LEVO bi morali krak, ki je prej gledal DOL upogniti v LEVO. Če je ta krak iz npr.žice bomo končali v naslednji situaciji GOR (1cm)- LEVO (nekaj manj kot 1cm ker smo določeno dolžino žice izgubili ker jo je bilo potrebno upogniti). To se ne sme zgoditi saj naj bi bile dolžine krakov v vse smeri ves čas enake (simetrija?). Prav tako lahko potujemo v določeno smer več kot samo eno obdobje oz. 1 dolžino. Prej ali slej pa se morata kraka ponovno razcepiti, da na koncu iz njiju dobimo 32/64 ali pa 128 točk. Želja je, da bi bili vsi premiki kar se da enakomerno porazdeljeni skozi celotno obdobje (maximum je t12) od začetka do rešitve. Na ta način bi dobili predvidljivo okolje oz. ponavljajoč se sistem.
Rešitev sem sicer že našel, ko sem se znebil tistih prvi (neumnih) omejitev. Če ima kdo od vas slučajno še kak predlog kako to najbolj preprosto izpeljati ga bom definitivno zelo vesel. Je pa celotna zadeva precej bolj preprosta kot je izgledala na začetku :) se opravičujem za slabo zastavljeno nalogo!
Velikost mreže ni poglavitnega pomena in se lahko poljubno spreminja (torej 11x11 ni omejitev).
Bom poizkusil še enkat definirati problem čeprav sem sedaj do neke rešitve že prišel. Uspelo mi je ko sem spremenil velikost mreže :):
Skratka imamo omejenen prostor (kvadrat...100x100cm). Začnemo "na sredini" mreže. Cilj, ki ga skušamo doseči je, da bi na koncu imeli 32/64/128 točk enakomerno razporejenih po celotnem prostoru. Mreža nam (meni) je le v pomoč. Točka na sredini je naš začetek. Ko pritisnem "START" se točka razdeli v "dva kraka". Te dva kraka sta vedno drug drugemu nasproti ležeča (lahko jih kasneje upognemo npr. diagonalno). Smer v katero sta obrnjena lahko izberemo. Recimo da sta na začeku obrnjena v smeri GOR-DOL. Za ponazoritev vzemimo da sta kraka dolga 1cm. Če bi želeli ustvariti situacijo GOR-LEVO bi morali krak, ki je prej gledal DOL upogniti v LEVO. Če je ta krak iz npr.žice bomo končali v naslednji situaciji GOR (1cm)- LEVO (nekaj manj kot 1cm ker smo določeno dolžino žice izgubili ker jo je bilo potrebno upogniti). To se ne sme zgoditi saj naj bi bile dolžine krakov v vse smeri ves čas enake (simetrija?). Prav tako lahko potujemo v določeno smer več kot samo eno obdobje oz. 1 dolžino. Prej ali slej pa se morata kraka ponovno razcepiti, da na koncu iz njiju dobimo 32/64 ali pa 128 točk. Želja je, da bi bili vsi premiki kar se da enakomerno porazdeljeni skozi celotno obdobje (maximum je t12) od začetka do rešitve. Na ta način bi dobili predvidljivo okolje oz. ponavljajoč se sistem.
Rešitev sem sicer že našel, ko sem se znebil tistih prvi (neumnih) omejitev. Če ima kdo od vas slučajno še kak predlog kako to najbolj preprosto izpeljati ga bom definitivno zelo vesel. Je pa celotna zadeva precej bolj preprosta kot je izgledala na začetku :) se opravičujem za slabo zastavljeno nalogo!
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Na svidenje, Pluton, pozdravljen Kuiperjev pas (strani: 1 2 )Oddelek: Novice / Znanost in tehnologija | 26780 (21485) | bMozart |
| » | igra s figurami za šah (s kmeti)Oddelek: Igre | 3595 (2298) | burek17 |
| » | 100x100 šahovnicaOddelek: Programiranje | 6954 (5130) | techfreak :) |
| » | Thomasov problem (strani: 1 2 3 )Oddelek: Znanost in tehnologija | 9831 (5648) | Pixy222 |
| » | [JAVA] helpOddelek: Programiranje | 1591 (1305) | keworkian |