TechBlog cikkei

Az n-edik racionális


Közismert, hogy a racionális számok megszámlálhatóak. A következő algoritmussal ugyanis fel tudjuk őket mind sorolni (az egyszerűség kedvéért, most csak a 0 és 1 közöttieket, a többiek negálással és invertálással adódnak):

  1. Legyen q=1.
  2. Legyen p=1.
  3. Ha p/q nem eleme a készítendő listának, tegyük bele.
  4. Ha p=q, akkor legyen q=q+1 és folytasd a 2. lépéstől. Különben legyen p=p+1.

Így előáll egy lista, ami tartalmazza az összes racionális számot 0 és 1 között. A kérdés: hogyan lehet meghatározni ennek a listának az n-edik elemét?

Nyilvánvaló, a fenti algoritmus egyben meg is határozza a lista elemeit, de ez az algoritmus O(n) nagyságrendű. A kérdés tehát az, hogy létezik-e (létezhet-e) olyan algoritmus, ami a lista n-edik elemét ennél gyorsabban (mondjuk O(ln(n)), esetleg O(1) rendben) képes meghatározni? Ja, a "felírom a listát egy papírra és kikeresem az n-edik elemet. O(1), nyertem" típusú megoldás nem játszik...

Faites vos jeux!

Utoljára módosította SAdam 2013.VIII.21 11:52-n
Bejegyzés módosítása | PermaLink
Votes disabled.

Hozzászólások (6)

SAdam hozzászólása 2013-08-21 11:54-kor

Amúgy az a sejtésem, hogy a fentinél jobb algoritmust csak úgy lenne lehetséges írni, ha ismernénk az n-edik prímet meghatározó függvényt. Gyanítom, hogy enélkül esélytelen a fentinél gyorsabb algoritmust adni a problémára, de hátha valakinek mégis eszébe jut valami. ;-)


UPi hozzászólása 2013-08-21 13:26-kor

Ugye jól értem, hogy a 4. lépés közepe az, hogy "Legyen q=q+1 és p=1"?

Egyébként mi a gyakorlati alkalmazás?

Ja és a naiv algoritmus nem O(n) hanem O(n^2), ha tényleg ellenőrzöd berakáskor, hogy a szám már a listában van-e....


SAdam hozzászólása 2013-08-21 15:51-kor

Igen, úgy értettem.

Az ellenőrzés maga nem O(n) nagyságrendű, ugyanis a konstrukcióból (szerintem) következik, hogy p/q akkor és csak akkor eleme a listának, ha p és q relatív prímek, vagyis az "ellenőrzöm, hogy benne van-e már a listában" ekvivalens annak az eldöntésével, hogy p és q relatív prímek, ez pedig általában kevesebb, mint O(n) lépésben eldönthető (a megoldás, amit ismerek – bináris euklideszi algoritmus –, legrosszabb esetben a nagyobbik szám bitjeinek a számával négyzetesen arányos rendű, vagyis csak n>36 esetén lesz gyorsabb, mint O(n)). De tény, valóban rosszabb a naív algoritmus, mint O(n).

Igazából ezt nem a gyakorlati felhasználás miatt kérdeztem, csak a reggeli kutyaséta közben jutott eszembe a probléma. Amúgy az inspirált, hogy frekvencia- és amplitúdó-modulációnál az, hogy milyen hangszínt kap az ember, azzal függ össze, hogy a moduláló- és vivőfrekvenciák aránya milyen (minél kisebb nevezőjű racionális, annál "harmonikusabb" a hangszín). Azon kezdtem el agyalni, hogy hogy tudnék az egyik példaprogramba beilleszteni egy olyan csúszkát, ahol a csúszka egyik vége 1, a másik vége meg valami batár nagy nevezőjű racionális szám, és az átmenet viszonylag folytonosan megy végig a "hangszíntérben" (vagyis, a fent leírt módszer szerint megy végig a racionális számokon).

Természetesen a gyakorlatban ezt táblázatos kiolvasással fogom implementálni, mivel a csúszka-objektum, amit a Max kínál, amúgy is diszkrét értékeket ad vissza – az isten (jelen esetben, Miller Puckette) is arra teremtette, hogy táblázatból olvasson ki értékeket. Inkább csak "elgondolkodtató érdekességként" jutott eszembe, hogy ha nem a táblázatban eltárolásra szavaznék, akkor vajon hogyan lehetne egy gyors algoritmust írni a problémára? Szóval a problémafelvetés inkább elméleti...


UPi hozzászólása 2013-08-22 07:57-kor

Szerintem ezt nem lehet O(1) alatt megoldani. Nincs erre bizonyításom, csak egy olyan heurisztikám, hogy nagyon hasonlít a prímfelbontásra amit szintén nem tudunk megoldani.

Viszont létezik olyan megszámoló algoritmus, ami nem optimális (ugyanazt a számot többször számolja), viszont tényleg O(n) a megszámolás és O(1) a sorszám keresés. Érdekel?


SAdam hozzászólása 2013-08-22 12:09-kor

For the record, írd le. :-)

A konkrét felhasználás szempontjából az fontos, hogy a számok pontosan abban a sorrendben jöjjenek, mint a fenti buta algoritmussal (vagyis, ha azt mondom, hogy a 6. elemet kérem, akkor valóban 3/4-et kapjak vissza, és ne 2/4-et), de mondom, a konkrét szoftverben ezt nagy valószínűséggel táblázatos kiolvasással fogom megoldani, mivel memória van bőven, és a táblázatos kiolvasásnál gyakorlatilag semmi sem gyorsabb.


UPi hozzászólása 2013-08-22 18:29-kor

q > p > 0

n = q * (q+1) / 2 + p;

Tagek: