DevProTalk

Forumi IT profesionalaca
web development, web design, e-business, SEO


Idite nazad   DevProTalk > Web development i web aplikacije > Programiranje
Želite da se reklamirate ekskluzivno na ovoj poziciji? Javite se

Programiranje Java, Perl, VB, ASP, .NET, C, C++, Pascal, Delphi Sponzor: VIP izazov 3

Odgovori
 
Alati teme Način prikaza
Staro 15. 02. 2006.   #41
BraMom
Branimir Momcilovic
Qualified
 
Datum učlanjenja: 15.02.2006
Lokacija: Beograd
Poruke: 167
Hvala: 47
25 "Hvala" u 8 poruka
BraMom is on a distinguished road
Default 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.
BraMom je offline   Odgovorite uz citat
Staro 15. 02. 2006.   #42
bluesman
Goran Pilipović
Sir Write-a-Lot
 
Avatar bluesman
 
Datum učlanjenja: 18.05.2005
Lokacija: Beograd
Poruke: 5.450
Hvala: 288
1.247 "Hvala" u 446 poruka
bluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušati
Pošaljite ICQ poruku za bluesman
Default

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.
__________________
Goran Pilipović a.k.a. Ugly Fingers Bradley f.k.a. bluesman
I don't always know what I'm talking about but I know I'm right!
bluesman je offline   Odgovorite uz citat
Staro 16. 02. 2006.   #43
BraMom
Branimir Momcilovic
Qualified
 
Datum učlanjenja: 15.02.2006
Lokacija: Beograd
Poruke: 167
Hvala: 47
25 "Hvala" u 8 poruka
BraMom is on a distinguished road
Default

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"?
BraMom je offline   Odgovorite uz citat
Staro 16. 02. 2006.   #44
bluesman
Goran Pilipović
Sir Write-a-Lot
 
Avatar bluesman
 
Datum učlanjenja: 18.05.2005
Lokacija: Beograd
Poruke: 5.450
Hvala: 288
1.247 "Hvala" u 446 poruka
bluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušatibluesman je osoba koju treba slušati
Pošaljite ICQ poruku za bluesman
Default

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
__________________
Goran Pilipović a.k.a. Ugly Fingers Bradley f.k.a. bluesman
I don't always know what I'm talking about but I know I'm right!
bluesman je offline   Odgovorite uz citat
Staro 16. 02. 2006.   #45
Petar Marić
Python Ambassador
Master
 
Avatar Petar Marić
 
Datum učlanjenja: 06.06.2005
Lokacija: Novi Sad
Poruke: 602
Hvala: 28
27 "Hvala" u 17 poruka
Petar Marić će postati "faca" uskoro
Pošaljite ICQ poruku za Petar Marić
Default

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?
__________________
Python Ambassador of Serbia
Petar Marić je offline   Odgovorite uz citat
Staro 16. 02. 2006.   #46
Petar Marić
Python Ambassador
Master
 
Avatar Petar Marić
 
Datum učlanjenja: 06.06.2005
Lokacija: Novi Sad
Poruke: 602
Hvala: 28
27 "Hvala" u 17 poruka
Petar Marić će postati "faca" uskoro
Pošaljite ICQ poruku za Petar Marić
Default

PHP kôd:
$code = ($start $i $seed) % 10000
Videvši ovu liniju koda zasvrbeo me je mozak, a sad vidim i zašto:
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.
__________________
Python Ambassador of Serbia

Poslednja izmena od Petar Marić : 16. 02. 2006. u 03:29.
Petar Marić je offline   Odgovorite uz citat
Staro 16. 02. 2006.   #47
ivanhoe
Ivan Dilber
Sir Write-a-Lot
 
Avatar ivanhoe
 
Datum učlanjenja: 18.10.2005
Lokacija: Bgd
Poruke: 5.320
Hvala: 104
2.344 "Hvala" u 583 poruka
ivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svimaivanhoe je ime poznato svima
Pošaljite poruku preko Skype™ za ivanhoe
Default

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
__________________
Leadership is the art of getting people to want to do what you know must be done.
ivanhoe je offline   Odgovorite uz citat
Staro 16. 02. 2006.   #48
nixa
Nikola Denić
Sir Write-a-Lot
 
Avatar nixa
 
Datum učlanjenja: 18.05.2005
Lokacija: Beograd
Poruke: 3.694
Hvala: 160
458 "Hvala" u 164 poruka
nixa ima spektakularnu aurunixa ima spektakularnu aurunixa ima spektakularnu aurunixa ima spektakularnu aurunixa ima spektakularnu auru
Pošaljite poruku preko Skype™ za nixa
Default

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
__________________
Do not ask yourself what the world needs. Ask yourself what makes you come alive, and then go do that. Because what the world needs is people who have come alive
nixa je offline   Odgovorite uz citat
Staro 16. 02. 2006.   #49
Petar Marić
Python Ambassador
Master
 
Avatar Petar Marić
 
Datum učlanjenja: 06.06.2005
Lokacija: Novi Sad
Poruke: 602
Hvala: 28
27 "Hvala" u 17 poruka
Petar Marić će postati "faca" uskoro
Pošaljite ICQ poruku za Petar Marić
Default

@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.
__________________
Python Ambassador of Serbia

Poslednja izmena od Petar Marić : 16. 02. 2006. u 10:40.
Petar Marić je offline   Odgovorite uz citat
Staro 16. 02. 2006.   #50
BraMom
Branimir Momcilovic
Qualified
 
Datum učlanjenja: 15.02.2006
Lokacija: Beograd
Poruke: 167
Hvala: 47
25 "Hvala" u 8 poruka
BraMom is on a distinguished road
Default

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...
BraMom je offline   Odgovorite uz citat
Odgovori


Alati teme
Način prikaza

Pravila pisanja
Možete ne započinjati nove teme
Možete ne slati odgovore
Možete ne slati priloge
Možete ne izmeniti svoje poruke
vB kôd je Uključen
Smajliji su Uključen
[IMG] kod je Uključen
HTML kôd je Isključen
Pogledajte forum

Slične teme
Tema Početna poruka teme Forum Odgovori Poslednja poruka
random + mysql mega023 PHP 9 09. 03. 2010. 17:08
random select na velikoj tabeli kodi SQL baze podataka - Sponzor: Baze-Podataka.net 14 09. 04. 2008. 13:46
random koji favorizuje kodi Programiranje 16 29. 04. 2007. 22:09
java.util.Random security Ivan Programiranje 0 02. 01. 2007. 19:43
Random image - preraditi za flash... headcutter (X)HTML, JavaScript, DHTML, XML, CSS 4 02. 09. 2005. 23:14


Vreme je GMT +2. Trenutno vreme je 18:47.


Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.
Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.