|
ciklicna grupa
Nisam citao celu diskusiju tako da se unapred izvinjavam ako je neko vec dao ovu ideju.
Problem se svodi na teoriju brojeva, dakle ciklicna grupa i njen generator. npr. trebaju mi sve cifre (0-9) oznacicu skup za Z10, teorija kaze da ako uzmem bilo koji broj, zvacemo ga g, koji je uzajamno prost sa 10, on je generator grupe Z10 u odnosu na sabiranje po modulu 10 da ne davim mnogo, uzmimo g=3, 3 i 10 su uzajamno prosti, ok, generator dobijam samo sabiranjem po modulu 10, znaci: 3 mod 10 = 3 6 mod 10 = 6 9 mod 10 = 9 12 mod 10 = 2 ... teorija kaze da ce se ovako dobiti svi elementi grupe, tj. u nasem slucaju cifre od 0-9, nema ponavljanja I, sto je najlepse, tacno znas koji je i-ti clan, tj. mozes da ga izracunas, a kako je ovakav generator i bijekcija, da se napraviti i inverz, tj. moze se izracunati da je npr. cifra 9, dobijena kao treci clan niza. Ovu ideju treba malo razraditi i nema potrebe za smestanjem kodova u bazu. |
Posto nisi procitao od pocetka: traze se cifre 0..9 i karakteri a..z (case insensitive), ne samo cifre.
Iskreno, nisam bas najbolje shvatio tvoj predlog. |
Nisam čitao celu diskusiju, a postavku problema sam pročitao detaljno.
Možda je moj odgovor bio malo štur, ajde da probam detaljnije. Pretpostavio sam da je svejedno da li si dobio kodove od cifara i slova, kakve tražiš, ili samo od cifara, jer kod od npr. 10 (ili više) cifara lagano možeš da prekodiraš u kod od 8 slova i cifara, ok? Izgleda i da je osim jedinstvenosti, bitno da kodovi ne mogu da se "provale", tj. da bude onemogućeno da se na osnovu određenog broja kodova generiše sledeći. Evo mog rešenja za 4 cifre od 0..9 (napisao bih i za 2 miliona, ali je potpuno isto). Izabereš prvi kod, neka je to 7777 (nije bitno kakav je) i uzajamno prost broj sa 10000, bilo bi idealno da je to prost broj, tako je najteže za razbijanje, ali za primer će biti dobar i 7811 i pustiš ovako nešto (nemam instaliran paint :) ): <?php $start = 7777; $seed = 7811; for($i=0; $i<100; $i++) { $code = ($start + $i * $seed) % 10000; echo $i, ' : ', $code, '<br>'; }?> Ovo ti daje (teorija brojeva garantuje) sve brojeve od 0 do 9999. Jasno dobijaćeš i brojeve sa manje cifara od 4, ali uvek možeš da dopišeš nule ispred. Još koja random cifra između da skreneš trag i izbegneš kodove tipa 1111, i prekodiraš dve tri cifre u slova da dobiješ ono što si tražio, to bi bilo to. Je l' sad bolje? P.S. Mislim da sam zaslužio veći rejting od "novi član"? |
Off Topic: Nešto sam sada umoran da čitam pažljivo, hoću samo da ti odgovorim za "novi član"... samo ti piši i promeniće ti se status onoliko brzo koliko doprinosiš forumu :) |
Napiši implementaciju svog rešenja da uradimo benchmark i da vidimo imamo li novog šampiona, način rešavanja problema mi je interesantan.
Nekoliko puta si spomenuo termin "teorija brojeva". Koja i imaš li link ka dodatnim informacijama o njoj? My geek sense is tingling, ovo može da bude nešto jako interesantno. Eh da, imam jedno offtopic pitanje za tebe: Dolaziš nam sa PMF-a? |
PHP kôd:
Formula za izračunavanje koju si naveo me je jako podsetila na ovu (A, B i M su const.):  što je opšti oblik formule za LCG (linearni kongruentni generator) što je jedan od načina za generisanje pseudo-slučajnih brojeva. Iskreno rečeno, sad mi se tvoje rešenje i ne čini toliko hot. U ovom članku jasno piše da je korišćenje LCG-a u bilo kakvoj formi izrazito loša ideja u slučajevima kada je potreban visok kvalitet slučajnih brojeva (kao što je ovde slučaj). Ipak je Wikipedia: Mersenne Twister algoritam zakon za ovakve stvari ;) PS: Eh, da ima li ko da preporuči neki softver i/ili MATLAB kod/funkciju/biblioteku/toolkit za spektralnu/frekvencijsku analizu (inače ću ponovo morati da pišem svoje funkcije)? Mogli bismo da napravimo benchmark kvaliteta rešenja koji nam daju programi, tj. ako ima zainteresovanih. |
ovo je varijanta linearnog kongruentnog generatora... ako se dobro secam formula kojom se dobija sledeci pseudo-slucajn broj je:
x(i+1) = (A*x(i) + C) mod OPSEG gde je x(i) prethodni rnd broj (ili seed za prvi u nizu), a A i C proizvoljne konstante...ono za uzajamno proste brojeve je uslov za dobijanje max. duzine ciklusa... Koliko ja znam ovo se smatra kriptografski najslabijim pseudo-rnd generatorom (ne pitaj me zasto ga je najlakse razbiti, nemam pojma, ali tako pise u svim knjigama...) EDIT: ostao mi otvoren prozor, pa nisam video da je petar u medjuvremenu napisao ovo isto...sorry |
Off Topic: ( ne osećam sebe da sam dovoljno geek da dodam nešto ) Drug novi član BraMom dobrodošao bluesman sad si nadrljao počinje da se pravi i Niški lobi ovde :) Imate be svi da propričate po naški |
@invanhoe: Ako nacrtaš parove (x(i-1), x(i)) primetićeš strukturu rešetke. Ako uzmeš tri uzastopna pseudo-slučajna broja dobićeš nešto vrlo slično ovom:
 I šta nama rešetka u suštini znači? Ako znamo jedan pseudo-slučajan broj i znamo algoritam (što skoro uvek znamo) onda možemo generisati sve pseudo-slučajne brojeve nakon njega. |
Hvala svima na dobrodošlici...
@BlueIce Da, dolazim sa PMF-a u Nišu, u pravu si da ovo nije ništa novo, čista primena Teorije Brojeva koju sam slušao kod prof Žikice Peroviča na I godini studija. Pogledaću Mersenne twister kad imama vremena, toga nije bilo kad sam učio ovu oblast, jer još nije bio ni napravljen (1997). Što se tiče linkova, ne bavim se profesionalno matematikom, ali sigurno možeš da nađeš masu toga po netu (Number theory). Nije mi bila ideja da pišem gotovo rešenje, a ni da postanem "šampion", čisto sam hteo da skrenem pažnju da postoji teorija koja pokriva temu i dam najjednostavniji primer... |
| Vreme je GMT +2. Trenutno vreme je 21:52. |
Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.