TechBlog cikkei

Néhány megoldatlan probléma megoldása

Rég írtam bármit a lapra. Most sem fogok sokat, de a Minecraft írójának volt egy blogbejegyzése, amit meg kell osszak veletek:

http://notch.tumblr.com/post/10309613883/the-solutions-to-a-few-unsolved-problems

Szégyenlem, de több, mint 33 évet leéltem anélkül, hogy találkoztam volna ezzel a problémával:

http://en.wikipedia.org/wiki/Collatz_conjecture

Milyen egyszerűnek tűnő probléma, és mégis milyen csodálatos gráfot feszít ki. No, megyek is pelenkát teregetni.

Tagek:
 
Utoljára módosította Wigy 2011.IX.17 15:28-n; 0 hozzászólás
Bejegyzés módosítása | PermaLink
Szavazás letiltva.

Fibonacci-feladat

Unknown magic content: 'mathml'

Előrebocsátom, hogy a feladatnak semmi konkrét motivációja nincs, pusztán eszembe jutott, és mivel most nem sok időm van végiggondolni, de az eredmény érdekelne, ezért kidobom ide, hátha megragadja valakinek a fantáziáját.

Szóval a kérdés:

Igaz-e minden N-jegyű természetes számra, hogy létezik legalább egy olyan eleme a Fibonacci-sorozatnak, melynek első (!) N számjegye megegyezik e kiszemelt számmal?

Várom a megoldási ötleteket (nyilván utolsó N jegyre a feladat némi maradékosztályos blablával megoldható, de most hirtelen nem tudom, hogy első N jegyre hogy indulnék neki).

SAdam

Tagek:
 
Utoljára módosította UPi 2011.VI.02 15:11-n; 2 hozzászólás
Bejegyzés módosítása | PermaLink
Szavazás letiltva.

Részfa lekérdezése

Van egy javaslatom UPi feladatára. A cél az volt, hogy olyan relációs adatbázist tervezzünk, ami egy fát reprezentál úgy, hogy egy részfa lekérése, egy új elem beillesztése, valamint az út meghatározása a gyökértől egy adott elemig a lehető leggyorsabb legyen.

Az implementációhoz két oszlopra van szükség. Az első oszlop (nevezzük IDnek) egy egyéni karaktersor, ami az adott elemet azonosítja. Az egyedi azonosító előállításához a következő algoritmust használjuk:

  1. Tegyük fel, hogy az adatbázis N különböző karaktert képes megkülönböztetni (sajnos nem emlékszem, hogy egy "mezei" karaktermezőbe mind a 256 karakter szerepelhet-e, vagy sem, ezért inkább általánosan beszélek N karakterről, ami, ha az adatbázis képes char*ban gondolkodni, akkor N=256, ha meg nem, akkor valamivel kevesebb).
  2. Ekkor az egyedi azonosítók előállításához N-1 karaktert használhatunk fel. Kinevezünk egy karaktert "érvénytelennek". A továbbiakban erre a speciális karakterre "szóköz" címen fogok hivatkozni, de nem feltétlen a valódi szóköz karakter (lehet a 0-ás karakter is, amennyiben N=256). Az érvényes karakterek gyűjtőhalmazát a továbbiakban "szótár"-nak hívom (vagyis a "szóköz" + "szótár" halmaz az összes érvényes karakter halmazát adja az adott adatbázis-implementációban).
  3. Az első egyedi azonosító egyetlen karakterből áll, mégpedig a szótár legelső eleméből.
  4. Minden további egyedi azonosító úgy képezendő, hogy (amennyiben a legutoljára képzett azonosító n karakterből áll) képezzük a szótár szerint a legnagyobb azonosítóra közvetlenül rákövetkező n karakteres karakterláncot. Amennyiben ilyen karakterlánc nem képezhető, úgy azt az azonosítót képezzük, ami n+1 karakterből áll, melyek mindegyike a szótár legelső karaktere.

A második oszlop (nevezzük PATHnak) az adott elem teljes elérési útvonalát tartalmazza a gyökértől, oly módon, hogy a szülők egymás után szerepelnek benne a gyökérig visszamenőleg, a "szóköz" karakterrel elválasztva.

Ha az adatokat a data tábla tartalmazza és a lekérendő részfa csúcsán levő elem PATH oszlopának a tartalma s, akkor

 SELECT *
 FROM data
 WHERE PATH LIKE s%

(Itt jegyzem meg, hogy évek óta nem írtam SQL kódot, szóval a szintaktika lehet, hogy nem stimmel.)

Út meghatározása a gyökértől

Triviális, a PATH oszlop tartalmazza

Új elem beillesztése

Tekintsük azt az elemet, amelynek ID mezőjének értéke parent és PATH mezőjének értéke parentPath. Ez esetben az ez alá beszúrandó elem ID mezője az általános ID-generáló algoritmussal áll elő, míg PATH mezőjének értéke parentPath+parent+szóköz lesz.

A módszer egyetlen hátránya, hogy amennyiben m helyiértéket engedünk meg az ID mezőnek, úgy maximum mN-1 darab eleme lehet a fának. Ennél nagyobb korlát, hogy amennyiben a fa maximális mélysége k, úgy a PATH oszlopnak (m+1)*k szélesnek kell lennie (a +1 a szóközök miatt, bár némi spórolást el lehet követni, ha az ember a gyökér azonosítóját nem írja be a PATH mezőbe, mivel az triviálisan mindenhol szerepelni fog, bár akkor bizonyos lekérdezéseket külön kell szedni, így a program lesz valamivel bonyolultabb). 64 lehetséges karakterrel számolva a szótárban (lásd pl. base64) ez azt jelenti, hogy N=65, így m=3 esetén 262.144 sor tárolható. Ha egy szöveges oszlop maximum 65.535 karakterből állhat (nem tudom, milyen korlátok vannak az egyes SQL implementációkban, de még anno egy évtizeddel ezelőttről az rémlik, hogy ez valamilyen korlát volt), akkor tehát az ábrázolt fa maximális mélysége k=16.383 lehet. Mindenki döntse el, hogy ez megfelel-e, vagy sem..

Tagek:
 
Utoljára módosította SAdam 2011.V.15 19:23-n; 9 hozzászólás
Bejegyzés módosítása | PermaLink
Szavazás letiltva.

Napi vicc

Inkább le sem írom, hogy milyen problémába futottam bele, miközben egy projectet portoltam Windowsra a Visual C++ segítségével. Elég legyen az a link, ami a megoldást megadta. Szerintem dolog önmagáért beszél, és már olyan siralmas, hogy csak röhögni tudok rajta:

http://connect.microsoft.com/VisualStudio/feedback/details/344610/visual-c-2008-standard-m-pi-is-not-defined

De most őszintén, magyarázza már nekem el valaki, hogy mire jó az, ha a <cmath> inkludálása csak akkor fog a szabvány szerint elvárt módon működni, ha az ember betesz elé egy Microsoft-specifikus #define direktívát? Mármint azon kívül, hogy csúnyává tudnak tenni vele egy platformfüggetlennek szánt kódot...

Tagek:
 
Utoljára módosította SAdam 2010.X.19 02:30-n; 0 hozzászólás
Bejegyzés módosítása | PermaLink
Szavazás letiltva.

And now something that everyone can enjoy!

upload:Descant/N%C3%83%C2%A9vtelen.jpg

És ki nem találjátok mitől jött elő: a start menüre kattintástól

Tagek:
 
Utoljára módosította Descant 2010.IX.23 13:37-n; 1 hozzászólás
Bejegyzés módosítása | PermaLink
Szavazás letiltva.