Keresés

Részletes keresés

PikkPukk Creative Commons License 2013.10.12 0 0 9074

A feladat szöveges része csak annyi volt, amit leírtam. Azért is kérdeztem, hogy kinek mi a véleménye, hogy ki, hogyan értelmezi egyáltalán a feladatot. :D

Ha nem szó szerint értelmezzük, akkor van egyszerűbb megoldás is: pl. az átmeneti bufferes, de igazából még azt is el lehet hagyni.

Sokat nem akarok/akartam foglalkozni a dologgal, az általatok összehozott logika alapján összedobtam egy kódot, hogy lássam működik a gyakorlatban is. (működni látszik)Megnéztem a Wiki-n a moho-t, de én semmi hasonlóságot nem látok a moho és az itt leírt logika között, bár egyáltalán nem vagyok egy elméleti matekos...

 

(a fórummotornak meg ny..gem)

Előzmény: Axióma (9069)
Axióma Creative Commons License 2013.10.10 0 0 9073

Szuper. [Nem ugy mint a forummotor, szerintem ismet jopar honap mire meggyogyitjak...]

Igazabol mivel majdnem fuggetlen az egymas utani valasztas, csak arra nem jottem ra, hogy hogyan lehet jol megfogalmazni (elindultam forditva, hogy a doboz + kovetkezoben mind a 26 betu szerepel, de ebbol nem jon ki me'g).

Előzmény: attoparsec (9072)
attoparsec Creative Commons License 2013.10.10 0 0 9072

moho = optimalis.

 

a moho algoritmus a leheto leghosszabb karaktersort "eszi meg" az input string elejerol ami meg dobozvaltas nelkul lehetseges.

legyenek a dobozvaltas karakter-indexei i1, i2, .. ip, vagyis az elso valtas az input string i1-edik karakterenel tortenik, a masodik az i2-nel stb. (a dobozvaltasok szama p).

legyen egy A algoritmus, ahol a dobozvaltas-indexek j1, j2, .. jq.

ekkor j1 <= i1, mivel legkesobb i1-nel kotelezo dobozt valtani.

a (j1, i2] szekvencia tartalmazza az (i1, i2] szekvenciat, ami azt jelenti, hogy legkesobb i2 elott dobozt kell valtani, amibol kovetkezik, hogy j2 <= i2.

indukcioval belathato, hogy jx <= ix barmely x-re, ahol x eleme [1 .. p].

az A algoritmusnak tehat lagalabb annyi doboz-valtasra van szuksege, mint a moho algoritmusnak.

 

 

// bocs, ha ez esetleg duplan jelenne meg. majd kitoroltetem a modikkal.

Előzmény: Axióma (9069)
attoparsec Creative Commons License 2013.10.10 0 0 9071

// megjavithatnak mar a forummotort

Előzmény: Axióma (9069)
attoparsec Creative Commons License 2013.10.10 0 0 9070

moho = optimalis.

 

a moho algoritmus a leheto leghosszabb karaktersort "eszi meg" az input string elejerol ami meg dobozvaltas nelkul lehetseges.

legyenek a dobozvaltas karakter-indexei i1, i2, .. ip, vagyis az elso valtas az input string i1-edik karakterenel tortenik, a masodik az i2-nel stb. (a dobozvaltasok szama p).

legyen egy A algoritmus, ahol a dobozvaltas-indexek j1, j2, .. jq.

ekkor j1 <= i1, mivel legkesobb i1-nel kotelezo dobozt valtani.

a (j1, i2] szekvencia tartalmazza az (i1, i2] szekvenciat, ami azt jelenti, hogy legkesobb i2 elott dobozt kell valtani, amibol kovetkezik, hogy j2 <= i2.

indukcioval belathato, hogy jx <= ix barmely x-re, ahol x eleme [1 .. p].

az A algoritmusnak tehat lagalabb annyi doboz-valtasra van szuksege, mint a moho algoritmusnak.

Előzmény: Axióma (9069)
Axióma Creative Commons License 2013.10.10 0 0 9069

Ugyan mar, nem a koszonet miatt kerdeztem vissza, hanem mert azt remeltem, hogy tovabbi dolgok is kiderulnek a feladatrol. Mert a moho = optimalis bizonyitasa nem mozgatta meg senki fantaziajat, es ladapakolaskent is lehetne rajta csemegezni attol fuggoen, hogy mit tudunk az inputrol.

Előzmény: PikkPukk (9068)
PikkPukk Creative Commons License 2013.10.10 0 0 9068

A feladatban előre felcímkézett dobozok vannak, ezért kellett Sirpi módosítása is, bár az alapötlet a tiéd volt. Köszi neked is. :)

Előzmény: Axióma (9067)
Axióma Creative Commons License 2013.10.09 0 0 9067

Hat ezt nem ertettem az elobb sem, hogy miert nem ugyanaz? HA elore nezheted az inputot, akkor nem mindegy, hogy az elejen megnezed, addig nem rakod sehova, majd kivalasztod a dobozt, es belerakod az addigi betuket, vagy azt mondod, hogy most rakod mar egy dobozba, ami egy betus, de a vegen mondod meg, melyik betu volt az? Ha jol ertem, a minimalizalasi feladatnak inputja a hosszu string amit be kell tenni, az outputja absztrakt ertelemben a minimum valtasok szama, de gyakorlatban sokkal jobb azt mondani, hogy egy rovid string, ami azt mutatja, hogy melyik dobozokat hasznalod (es mindig akkor valtasz, amikor a doboz jelevel egyezo betuhoz jutsz); es persze aminel nincs rovidebb megfelelo string. [Az sztem veheto trivialisnak, hogy ha a rovid string minimalis hosszu, akkor tok mind1, hogy hogyan volt a valtasok hatara eredetileg, a fenti "akkor valtok amikor muszaj" algoritmus ugyanugy alkalmas lesz, csak a valtasok koruli invarians - egyikbe se tartozo - betuket csoportositja mashova.]

En nem latok kulonbseget a ket interpretacio kozott. Azt viszont nem latom me'g egzakt modon bizonyitottnak, hogy a moho algoritmus az egyuttal mindig minimalis lesz. Erzesre igen, de ennek a matematikai kerdese szerintem ez lenne.

Előzmény: Sirpi (9065)
PikkPukk Creative Commons License 2013.10.09 0 0 9066

Ok, ez már elég jó logika.

A feladat az (gondolom), hogy a dobozváltások számát a minimálisra csökkentsük, erre ez tökéletesen megfelel.

Már csak 1-2 számláló kell, hogy mettől meddig tart az a blokk, amit a kiválasztott dobozba rakunk.

Köszi a segítséget. :)

Előzmény: Sirpi (9065)
Sirpi Creative Commons License 2013.10.09 0 0 9065

Ahogy olvasom, utólag akarod felcimkézni a dobozokat, pedig előre rá vannak írva a betűk a feladat szerint.
Az alapján viszont azt a betűt kéne választani, amelyikből az első példány legutolsóként fordul elő. Ezután dobozváltás, és a következőnek megint azt a betűt kell választani, amelyikből az innentőli első előfordulás utolsóként fordul elő stb. Érzésre ez az optimális. Ennek eldöntésére pedig nem jó egy 26 bites számot használni? Elindulunk a betűkön sorba, és minden talált betűhöz tartozó bitet 1-re állítunk. Amikor a számunk minden bitje 1-essé válik, megvan, melyik dobozzal kell kezdeni.

 

Előzmény: Axióma (9064)
Axióma Creative Commons License 2013.10.09 0 0 9064

Ujraolvasva a hsz-od veget, mi a baj a cimke nelkuli dobozzal? Az elvi szinten nincs, ha barhova beleolvashatsz az inputba, vagy tenyleg a feladatot nem ugy ertem, ahogy irod.

Mindig elore kene eldonteni az input ismerete nelkul, hogy melyikbe rakod, kvazi ladapakolasi algoritmus-szeru dolgot kene keresni?

Előzmény: PikkPukk (9062)
Axióma Creative Commons License 2013.10.09 0 0 9063

Eloszor azt hittem, ez a KMP mintaillesztesi algoritmus elofeldolgozasahoz lesz hasonlo, de nem tunik ugy, sztem az egyetlen kerdes, hogy a moho algoritmus jo-e a feladat megoldasahoz. Mohonak itt azt hivom, hogy mindegyik pozicioban az elozoleg hasznalt dobozt hasznaljuk mindaddig, amig van legalabb egy betu ami me'g nem volt benne; es amikor az utolsot is elhasznalnank, akkor a regi dobozt lezarjuk es megcimkezzuk azzal, es az uj dobozba pakoljuk az aktualisat meg onnan a tobbit. (A vegen az utolsora barmely lehetseges cimket raragasztod). Ehhez csak 26 bitet kell allitgatnod, uj doboznal inicializalas es szamlalo allitas, uj betunel kihuz vagy sem, semmi extra algo.

Kerdes, hogy betlizhet-e a moho? Elsore azt mondanam, hogy nem hiszem, de most nem allnek neki bizonyitgatni. Az trivialisan kijon belole, hogy a szoveg hossza per 25 a worst case csereigeny (-1 ha az elso nem szamit cserenek).

Előzmény: PikkPukk (9062)
PikkPukk Creative Commons License 2013.10.09 0 0 9062

Sziasztok!

Elkezdtem én is ilyen logikai feladatokkal foglalkozni. Van jó pár amit én is ki tudok találni, vagy ha nem akkor kigúglizható, de erre sehol nem találtam válasz. Ez alapvetően egy programozási kérdés, és programozási megoldást tudok is rá néhányat, csak az a kérdés, hogy esetleg van-e rá jó logikai megoldás is?

 

Van 26 dobozunk az angol abc egy-egy betűjével ellátva. A dobozokba betűket lehet rakni, kivéve az adott dobozon szereplőt. A kérdés az, hogy minimum hány dobozváltás szükséges, hogy az összes betűt behelyezzük a dobozokba egy adott karaktersorozatra. 

- Egy dobozba akármennyi betűt belerakhatunk egymás után is és egy dobozt akárhányszor használhatunk újra. 

- Dobozváltás alatt azt értjük, hogy ha az adott ponton egy másik dobozba kezdjük rakosgatni a betűket. 

- A sorozat bármilyen hosszú lehet, egy karakter természetesen többször is előfordulhat.

Milyen algoritmussal lehetne az optimális (tehát minimális dobozváltásos) megoldást megtalálni?

Milyen adatszerkezettel lehetne ezt hatékonyan?

 

Könnyítés lehet az, hogy az input string-hez bármilyen sorrenben hozzáférünk, de a dobozokba az eredeti sorrenben kell, hogy kerüljenek a betűk.

 

Szóval hogy lehet ezt a feladatot megoldani annélkül, hogy plusz buffert (egy címke nélküli üres dobozt) használnék?

asx Creative Commons License 2013.10.01 0 0 9061

Én is megoldottam, trükk nélkül. Három gyufaszálat helyeztem át más helyre. Viszont nekem a jelek közötti szabad helyekkel és az esztétikai szempontokkal van gondom...

Előzmény: Vad (9059)
Vad Creative Commons License 2013.10.01 0 0 9060

Egyébként kemény tíz másodpercbe tellett kb, mert meglehetősen korlátolt a feladat. Kicsit nagyképű ez a karácsonyos határidő

Előzmény: Vad (9059)
Vad Creative Commons License 2013.10.01 0 0 9059

Megfejtettem, de ha arról ír, hogy semmi trükk, ne tegye szürke keretbe, mert akkor a szavai alapján nem lehet megoldani. Csak szólok.

Előzmény: Prof. Mózes (9053)
Axióma Creative Commons License 2013.09.30 0 0 9058

Nem igazan ertem ra eddig komolyabban foglalkozni vele, csak raneztem, annyibol me'g nem trivialis. De majd ha kialszom magam rendesen, kivancsi vagyok, hogy megoldom-e... programot tuti nem irok most, annyi idom nincs.

Előzmény: Prof. Mózes (9057)
Prof. Mózes Creative Commons License 2013.09.27 0 0 9057

Azt hiszem az a lényeg, hogy arab számokat használ, és nem keveri római vagy egyéb számokkal. Az arab számok egyik lehetséges megjelenítési formája a digitális számjegy, amiket pálcikákkal meg lehet jeleníteni, és mivel mindenk ismeri ezt a jelrendszert, ezért ezt használja, és amíg egyértelmű, hogy milyen számjegyekről van szó, addig megfelelő. Neked sikerült megoldani? 

Axióma Creative Commons License 2013.09.26 0 0 9056

Hat en me'g palcikas szamologepbol proporcionalisat nem lattam. Letezik? Link?

Előzmény: Prof. Mózes (9055)
Prof. Mózes Creative Commons License 2013.09.25 0 0 9055

Nem tisztem magyarázni, de azt hiszem elsiklottál pár dolog fölött. Egyrészt a többnyire szót nem vetted észre a mondatban. Másrészt sokféle számológép kijelző létezik. 

Előzmény: Axióma (9054)
Axióma Creative Commons License 2013.09.25 0 0 9054

Nem tudom, hogy te vagy-e a rejtveny kozzetevoje, de eleg erdekes a hosszu bevezeto utan, hogy mar az elso rejtveny nem felel meg a sajat leirasanak. Nevezetesen az elejen azt allitja, hogy a rejtvenyek megjelenesi formaja a szamologepeken szokasos, kulon kiter az egyes szamjegyek kozotti helyekre, illegalisnak ertekelve a csusztatasokat, erre a peldaban az 1-es szamjegyet ugy rajzolta fel, hogy egy fel helyen van.

Egyebkent meg ehhez a rejtvenytipushoz egyszer kell felepiteni egy adatbazist, az N darab gyufaszalbol ervenyes egyenlosegek halmazat, utana mar csak a "tavolsagot" kell nezni. Aki algoritmusok tantargyat tanit, feladhatna' mint backtrack keresesi feladat:)

Előzmény: Prof. Mózes (9053)
Prof. Mózes Creative Commons License 2013.09.24 0 0 9053

Sziasztok! Itt van egy nagyon érdekes gyufafeladvány:

http://duplapluszjo.blogspot.hu/2013/09/gyufafeladvany-8241.html

És könyvet is lehet nyerni, ha valaki megoldja!

Törölt nick Creative Commons License 2013.09.16 0 0 9052

ahh, jogos, igazad van, benéztem

 

azt nem vettem észre, hogy nem kell "optimálisnak" lennie a módszernek, azaz nem az első lehetséges alkalommal kell szólni, hanem ráér valamikor később is, amikor már tuti a dolog

 

 

Előzmény: FASIRT (9051)
FASIRT Creative Commons License 2013.08.23 0 0 9051

Kimész a 4. napon, ég a lámpa, mert előtted már voltak kint, az első meggyújtotta, a többi nem bántotta, te eloltod. Kimész a 15. napon, megint ég a lámpa, tehát volt kint valaki más is, mint aki először meggyújtotta, mert ő már többször nem gyújthatja meg, eloltod, és tudod, hogy két különböző ember már járt kint. Kimész a 32. napon, nem ég a lámpa, tehát közben csak az első két ember volt kint, akik már nem gyújthatják meg. Ahányszor égve találod, eloltod, és tudod, hogy egy-egy új ember is kint járt. A kilencediknél biztos lehetsz benne, hogy ha nem vertek át, akkor mindenki járt már kint.

Előzmény: Törölt nick (9050)
Törölt nick Creative Commons License 2013.08.23 0 0 9050

Szerintem nem ezt jelenti a feladat... hanem azt, hogy ha mondjuk én vagyok az az adott ember, akinek ezt tudnia kell, akkor amikor alkalmanként pont rám kerül a sor, akkor meg kell tudnom mondani, hogy volt-e már mindenki vagy még nem. De lehet, hogy én értem félre.

 

Tehát mondjuk kimegyek a 4. napon, ekkor nyilván még nem, aztán kimegyek mondjuk a 15-en, még ekkor sem, aztán a 32-en, na ekkor már igen... vagy valami ilyesmi.

Előzmény: FASIRT (9047)
H.A.P.C.I.gépek láz adása Creative Commons License 2013.08.14 0 0 9049

lállálááákakukktojás

kakukktojás

kakukkHAPCItojás

gaguggdojázs

gagugg...ööö...dojázs

gag...dözs

emlékezzünk együtt szetetett testvérünkre

 

Hasas a s a sas a, s a sas a s a sasasszony közé nem kell vessző.(12) 

H.A.P.C.I.gépek láz adása Creative Commons License 2013.08.13 0 0 9048

Hasas a, sas a, sasasszony szerint.

 

Hasas a s a sas, a sas a s a sasasszony közé nem kell vessző.

Előzmény: gligeti (8382)
FASIRT Creative Commons License 2013.08.10 0 0 9047

Jelölj ki egy lámpaoltogatót, a többinek meg mondd meg, hogy egyszer meggyújthatja a villanyt, ha éppen nem ég, amikor bemegy a mosdóba. A lámpaoltogató meg csak számlálja, hogy hányszor kellett eloltania a lámpát. A kilencediknél kiabáljon az őrnek.

Előzmény: Karika Alma (9046)
Karika Alma Creative Commons License 2013.08.09 0 0 9046

Valaki segítene megoldani ezt a feladatot? Van 10 ember, akiket egyesével bezárunk egy szobába. Naponta kiengedünk közülük egyet a mosdóba, majd vissza kell mennie. Majd másnap megint kiengedünk valakit, azonban a kiválasztás véletlenszerűen működik, tehát ha valaki volt már kint, attól még ugyanolyan eséllyel mehet ki újra. A mosdóban a villanyt szabadon fel ill. lekapcsolhatják, ez az egyetlen jel, amivel kommunikálhatnak egymás között. A feladat lényege egy olyan módszer kidolgozása a kommunikációra a villanykapcsolón keresztül, amivel egy adott bemenő ember tudja, hogy rajta kívül mindenki volt-e már bent.

attoparsec Creative Commons License 2013.04.23 0 0 9045

igazabol nincs is szukseg irogepre, eleg egy vonalzo.

 

Előzmény: Vad (9026)

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!