Jos joku viisas viitsii neuvoa kun x juoksee silmukassa 0-64000 ja sitten pitäisi tehdä yhtälö, jonka lopputulos yhden silmukan aikana on "satunnainen", mutta ei sama kuin x ja väliltä 0-64000 ja sama luku esiintyy vain kerran.
Dissolve - algoritmi?
????
13416
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 13
Vanhimmat
Alusta taulukko valmiiksi satunnaisluvuilla.
Tee about näin se taulukko:
for i:=0 to 64000 do
taulukko[i]:=i; // taulukossa luvut 0-64000
end for
for i:=0 to 64000 do
j:=random(64001) // arvo satunnaisluku 0-64000
k:=random(64001) // samma här
swap(taulukko[j],taulukko[k]) // vaihda taulukon j:s ja k:s alkio keskenään
end for
// nyt taulukossa on luvut 0-64000 satunn. järjestyksessä
//jos tuosta ei tule tarpeeksi satunnainen, laita lisää kierroksia viimeiseen silmukkaan
Olihan idea!!! Entä jos vaadittu lukualue olisikin 32-bittinen???
Kysymykseesi on vastaus ja varsin helppo sellainen, JOS lukualueesi maksimi voisi olla jokin kahden potenssi -1, siis esim. 65535. Onko näin, eli kumman vastauksen haluat?
>Olihan idea!!! Entä jos vaadittu lukualue olisikin 32-bittinen???
64000 alkiolla helppo ja nopea toteuttaa. toimii myös nopeasti O(n). jos nyt ajattelee dissolvea, niin oiskohan tällä hetkellä max. resot jotain 2048x1536 luokkaa eli reilu 3 milj. pistettä.
seuraava pätkä alustaa em. kokoisen taulukon käsipelillä mitattuna noin 2,5 sekunnissa 1,4GHz Athlon (256MB DDR 266MHz), MDK Linux 9.0 -koneella.
#include
int main(){
const long lkm=2048*1536;
unsigned long taulu[lkm];
unsigned long temp;
long i,j,k;
for (i=0;i
..jos omaksi ilokseen näprää. Mutta jos edes ajattelee joskus koodaavansa ammatikseen, tällaiset ratkaisut kannattaa unohtaa heti alkuunsa. Ja kysehän oli algoritmista...
Käytännön maksimiresoluutiot ovat todellakin mainitsemaasi luokkaa tällä hetkellä -- yhdellä monitorilla. TFT-näyttöjen yleistyessä kovaa vauhtia tilanne muuttuu ja saattaa muuttua nopeastikin jonkin teknisen läpimurron myötä.
"640 kilon työmuisti riittää takuulla kaikkeen mahdolliseen..."
>..jos omaksi ilokseen näprää. Mutta jos edes ajattelee joskus koodaavansa ammatikseen, tällaiset ratkaisut kannattaa unohtaa heti alkuunsa.
Sinä siis olet ammattilainen? No sitten voit kertoa, miten tuo ongelma kannattaa ratkaista.
> Ja kysehän oli algoritmista...
Niin oli. Ja sellaisen kysyjä sai.
Jos algoritmia etsimme, helppo sellainen on tietenkin "sekoittaa" silmukan x:n arvo sopivalla yhtälöllä siten, että informaatiota ei katoa. Kun lopputulos z on "saman kokoinen" kuin x, on saavutettu se mitä kysyjä haki, eli näennäisen satunnainen muunnos x-->z.
Yhtälössä voi käyttää aritmeettisia operaatioita kuten summaus ja XOR, shiftauksia, bittien swappauksia, mutta myös XLAT-taulu(j)a. Varsinkin XLAT-taulu(j)a, esim. 256 tavua, käyttäen toimintaan saadaan "satunnaisuutta". Tällöin taulussa ovat luvut 0...255 satunnaisessa järjestyksessä.
Kuten edellä mainitsin, homma on erittäin helppo tehdä jos x:n maksimi on jokin 2:n potenssi -1. Silloin bittien pyörittäminen on jokseenkin vapaata.
Yllytyksestäsi kokeilin asiaa VGA-resoluutiolla (640x480 pikseliä), jossa x = 0...307199. x:n maksimi ei ole 2:n potenssi -1, mutta hyödynsin tässä pikseleiden määrän jaollisuutta 256:lla ja 256x40:llä. Ruutu on ikäänkuin jaettu 16x16 pikselin osiin.
Ratkaisuja on useita, tämä on niistä vain eräs yksinkertaisin...
unsigned i, xCoord, yCoord;
i = (unsigned)(x / 1200);
x = x % 1200;
xCoord = (unsigned) x % 40 * 16 + xlat256[i] % 16;
yCoord = (unsigned) x / 40 * 16 + xlat256[i] / 16;
>Algoritmi vai ohjelma
Algoritmi = rajallinen määrä tarkoin määrättyjä askelia/toimenpiteitä halutun ongelman ratkaisemiseksi. Mun algoritmi oli kirjoitettu pseudokielellä (joka muistuttaa basicia/pascalia). Yhtä hyvin olisin voinut kirjoittaa sen suomeksi tai C:llä. En nyt ihan ymmärrä mitä ajat takaa tuolla algoritmijutullasi...
>...homma on erittäin helppo tehdä jos x:n maksimi on jokin 2:n potenssi -1
Jep,tiedän
>...Ruutu on ikäänkuin jaettu 16x16 pikselin osiin.
Tuo sinun algoritmisi on varmasti ihan käyttökelpoinen, mutta se ei valitettavasti ratkaise alkup. ongelmaa.
Algoritmisi oli aivan OK ja sen etu omaani nähden on "todellinen satunnaisuus". Tapauksesta ja painotuksista tietenkin riippuu, millaista algoritmia milloinkin on parasta käyttää.
Kritisoin ratkaisuasi lähinnä sen vuoksi, että tunnut suhtautuvan resursseihin ikäänkuin ne olisivat automaattisesti rajattomat. PC:ssä näin voi ollakin, mutta sovita algoritmisi vaikka kännykkään niin huomaat missä mennään.
Esittämäni ratkaisu ei suoraan vastannut alkuperäiseen kysymykseen, tiedän, mutta koska alkuperäinen kysyjä ei tarkentanut tehtävää kuten edellä pyysin, otin vapauden esittää asian omalla tavallani. Pienellä soveltamisella...
ruudulla on jokin kuva. No siihen pitäisi saada mustia pisteitä "satunnaisesti", mutta sama arvo vain yhden kerran ja kaikki arvot pitää käydä läpi. Eli tarvitsen pelkän yhtälön, joka tuottaa esim. 0-63999 väliltä "satunnaisesti" luvun joka loopin aikana, sama luku esiintyy kerran ja kaikki luvut pitää tulla.
Jossain näin siitä yhden ratkaisun aikoinaan, mutta en muista missä ja siinä oli vain muutama rivi koodia. Taisi olla jotain loogisia operaattoreita mukana. Tietenkin pitäisi olla mahdollisimman optimoitu, jos vain on tai osaa.
z = 250 * (x % 256 ^ 99) + xlat250[x / 256];
Muuttujan x on syytä olla etumerkitön. "Xor 99" on periaatteessa tarpeeton, mutta se hieman "sekoittaa pakkaa". Jätä pois jos haluat. xlat250-taulu (const unsigned char) sisältää luvut 0..249 satunnaisessa järjestyksessä.
Taulun saat generoitua näppärästi Excelistä: Ensimmäiseen sarakkeeseen em. luvut (0, 1, 2...249), toiseen 250 kpl satunnaislukuja (=rand()), sitten järjestelet rivit toisen sarakkeen perusteella suuruusjärjestykseen ja kopsaat ensimmäisen sarakkeen talteen.
Soveltuuko tuo myös lukujen 0-63999 satunnaiseen järjestykseen? Ei ole matematiikka niin paljon hallussa, että heti hoksaan miten tuo sen tekee.
Yhtälö muuttaa laskurin x lukeman "satunnaiseksi" samalla lukuarvoalueella eli 0-63999. "Satunnaisuus" on tietenkin suhteellista, mutta riittävää kuvaefekteihin, uskoisin.
Jos todellista satunnaisuutta kaipaat, on turvauduttava vaikkapa arvon kollegoitteni Punikin & 7 hyypiön edellä esittämään periaatteeseen. Siitäkin löytyy optimoitu toteutus, vaikka väistämättä vaatiikin huomattavasti enemmän resursseja.
En nyt kuitenkaan ryhdy tarkemmin selvittämään miten yhtälö toimii. Periaatteet esitin jo aikaisemmin ja esim. Excel on oiva väline tällaisten tutkimiseen... Onnea matkaan!