TechBlog cikkei
2013-08
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):
- Legyen q=1.
- Legyen p=1.
- Ha p/q nem eleme a készítendő listának, tegyük bele.
- 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!
IE=hate
Tudjátok, miért utálom az Internet Explorert?
Egyebek között, ezért. (Figyelmeztetés: a link erősen károsíthatja az ön és környezete intellektuális békéjét.)
(Kis háttér: A napokban találkoztam a következő Apache direktívával, ami arra szolgál hogy az Internet Explorer kevésbé legyen hülye:)