[ Predrag Supurovic @ 27.04.2012. 16:23 ] @
Ima jedan neobičan matematički problem.

Imam koordinatni sistem u kome po x osi koordinate mogu biti od 0 do 400000 a po y osi od 0 do 530000.

Zadatak je da koordinatu izrazim kroz jedan niz znakova, ali tako da upotrebim najmanji moguci niz znakova, ali tako da ne može da se desi da dve različite koordinate dobiju istu oznaku. Oznaka može sadržati samo brojeve i znakove engleske abecede, a valjalo bi da sve oznake imaju isti broj znakova.

Najbolje što sam uspeo da smislim to je da koordinate pretvorim u broj sa osnovom 36. Tako za 400000 dobijam 8KN4 a za 530000 dobijam BCY8. Kada to sastavim dobijam oznaku 8KN4BCY8. U slučaju da se dobije broj sa osnovom 36 koji ima manje od tri znaka, dodavala bi mu se vodeća nula, tako da oznaka uvek sadrži 8 znakova.

Ima li neko ideju kako bi ovo moglo da se izvede a da bude manje znakova?


[ Almedin @ 27.04.2012. 17:00 ] @
Ako mora biti 'citljivo' treba ti osnova 81 i broj ce biti 3 'cifre'. Mala i velika slova, cifre i .,'?!"-()@/:_+*#&%=<>[]. Ima i viska. Kada bi zapisivao i binarno, vjerovatno znas da je minimum 20 bitova.
[ Predrag Supurovic @ 27.04.2012. 17:48 ] @
Mogu da koristim samo brojeve i slova engleske abecede.
[ djoka_l @ 27.04.2012. 18:24 ] @
Da bi našao koliko ti treba cifara u osnovi 36 za prikazivanje koordinata, treba da nađeš logaritam od maksimalne veličine koordinate sa osnovom 36.
Tako za x osu ispada da ti treba log(400000)/log(36)=3.6 "bajtova", a za y log(530000)/log(36)=3,68 "bajtova". Zajedno za oba podatka ti treba (log(400000)+log(530000))/log(36)=7,28 "bajtova"

Dakle, nema načina da uštediš, moraš da upotrebiš po 4 znaka za svaku koordinatu, odnosno 8 za kombinaciju ove dve koordinate bez obzira da li radiš konkatenaciju ili radiš nekakvu drugu transformaciju...

Sa druge strane, ako razlikuješ velika i mala slova, tada radiš u sistemu sa brojnom osnovom 62. U tom slučaju bi ti za x i za y opet trebalo po 4 znaka, ali bi 400001*y+x mogao da izraziš sa samo 7 znakova.

[Ovu poruku je menjao djoka_l dana 27.04.2012. u 19:37 GMT+1]
[ Predrag Supurovic @ 27.04.2012. 19:34 ] @
Ma da, to sam i ja zakljucio. Ne mogu dobiti jednoznačnu transformaciju sa manje znakova. Da bih smanjio broj znakova moram smanjiti rezoluciju koordinatnog sistema, i to bar 32 puta.

Kao neko alternativno rešenje, podelio sam koordinatni sistem na zone koje su dimenzija 46656 * 46656, pa tako dok sam u okviru jedne zone mogu da koristim šestocifrene oznake. I to je nešto.

Ne mogu da koristim mala i velika slova kao razlicita.
[ zzzz @ 27.04.2012. 20:42 ] @
Piši do pola horizontalno,a od 300 001 kreni zapisivati vertikalno.
Dodaj još i kose zapise, uvedi razne boje za znakove,bold itd pa ćeš možda stjerati na samo jednu cifru.
[ Nedeljko @ 27.04.2012. 22:13 ] @
Evo, kako bi izgledala C++ imlementacija. Parametri X i Y su najveće vrednosti za x i y uvećane za 1.

Code:
template<unsigned X, unsigned Y>
string toString(unsigned x, unsigned y)
{
    unsigned long long z = x;
    string result;
    unsigned long long Z = X;
    unsigned long long base = 1;

    Z *= Y;
    z *= Y;
    z += y;

    while (base < Z) {
        unsigned long long z1 = z/36;
        unsigned digit = z - z1*36;

        z = z1;
        base *= 36;

        if (digit < 10) {
            result += '0' + digit;
        } else {
            result += 'A' + digit - 10;
        }
    }

    return result;
}

template<unsigned X, unsigned Y>
void fromString(const string &str, unsigned &x, unsigned &y)
{
    unsigned long long result = 0;

    for (unsigned i = str.size(); i > 0;) {
        --i;

        char c = str[i];
        unsigned digit;

        if (c >= '0' && c <= '9') {
            digit = c - '0';
        } else if (c >= 'a' && c <= 'z') {
            digit = c - 'a' + 10;
        } else {
            digit = c - 'A' + 10;
        }

        result *= 36;
        result += digit;
    }

    x = result/Y;
    y = result - x*Y;
}