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!

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:)

Header set X-UA-Compatible "IE=edge" # `mod_headers` can't match based on the content-type, however, we only # want to send this header for HTML pages and not for the other resources Header unset X-UA-Compatible