| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
 Postano: 22:39 uto, 22. 10. 2002 Naslov: Nagradni zadatak br. 1 |
    |
|
|
Uzmite cetiri najjace karte (B, Q, K, A) u cetiri boje (pik, karo, herc, tref). Po principu produkta trebali biste imati 16 karata u ruci - u suprotnom birajte ponovo :D
Zadatak je sloziti karte u matricu 4x4, ali tako da se u svakom retku i stupcu svaka vrsta karte i svaka boja javlja tocno jednom. Ako ne uspijete odmah nemojte odustajati, zadatak ima rjesenje!
Uzmite cetiri najjace karte (B, Q, K, A) u cetiri boje (pik, karo, herc, tref). Po principu produkta trebali biste imati 16 karata u ruci - u suprotnom birajte ponovo 
Zadatak je sloziti karte u matricu 4x4, ali tako da se u svakom retku i stupcu svaka vrsta karte i svaka boja javlja tocno jednom. Ako ne uspijete odmah nemojte odustajati, zadatak ima rjesenje!
_________________
Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
| [Vrh] |
|
Nesi
Inventar Foruma
(Moderator)
Pridružen/a: 14. 10. 2002. (14:27:35)
Postovi: (E68)16
Spol: 
Sarma: -
|
| Postano: 20:02 čet, 24. 10. 2002 Naslov: |
|
|
|
jel smijem napisati rjesenje sada, il da cekam? :twisted:
btw, onome tko rjesava: ima bar tri rjesenja, pa ono, malo strpljenja, malo logike... i ide
:D
jel smijem napisati rjesenje sada, il da cekam? 
btw, onome tko rjesava: ima bar tri rjesenja, pa ono, malo strpljenja, malo logike... i ide
_________________
It's not who you love. It's how.
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 1:48 sub, 26. 10. 2002 Naslov: Rjesenje? |
|
|
|
Sorry, Krcko, nisam mogao izdrzati... :)
[code:1]
#!/usr/bin/env perl
# Uzmite cetiri najjace karte (B, Q, K, A) u cetiri boje
# (pik, karo, herc, tref).
# Zadatak je sloziti karte u matricu 4x4, ali tako da se
# u svakom retku i stupcu svaka vrsta karte i svaka boja
# javlja tocno jednom.
use strict;
use integer;
my $cnt = 0;
my @desc;
foreach my $kind (qw(decko baba kralj as)) {
foreach my $color (qw(pik karo herc tref)) {
push @desc, sprintf("%10s", "$color $kind");
}
}
my $used = [ map { 0 } (0..15) ];
sub check1 {
my ($m, $el, $i, $step, $pos) = @_;
while ($i < $pos) {
return 0 unless ($m->[$i] - $el) % 4;
return 0 unless $m->[$i] / 4 - $el / 4;
$i += $step;
}
return 1;
}
sub check {
my ($m, $pos, $el) = @_;
return 0 unless check1($m, $el, $pos % 4, 4, $pos);
return check1($m, $el, 4 * ($pos / 4), 1, $pos);
}
sub put {
my ($m, $pos, $el) = @_;
if ($pos + 1) {
return unless check(@_);
$m->[$pos] = $el;
$used->[$el] = 1;
}
if ($pos >= 15) {
print "Rjesenje ".++$cnt.":\n";
for my $i (0..3) {
for my $j (0..3) {
print $desc[$m->[4 * $i + $j]], " ";
}
print "\n";
}
print "\n";
} else {
foreach my $e (grep { !$used->[$_] } 0..$#$used) {
put([ @$m ], $pos + 1, $e);
}
}
$used->[$el] = 0 if $pos + 1;
}
my $start = time();
put([], -1);
print "Time elapsed: ".(time() - $start)." sec\n";
[/code:1]
Ispada da rjesenja ima 6912 (sto je slucajno 27*256=3^3*16^2). Malo sam ispao iz stosa, pa ne znam kako bih izracunao da li je to tocan rezultat.
Generiranje, ispis na ekran i u file, traju 91 sekundu na P2/333, s Perlom 5.6.0 na RedHatu 7.2. Dobiveni file je oko 1.5MB.
Btw, Nesi, mislim da nagrada ipak pripada tebi, jer sam ja koristio "tesku" artiljeriju... :) U svakom slucaju, cestitke na 3 kombinacije - ja nisam ni to nasao na ruke. :oops:
Pozdrav!
Sorry, Krcko, nisam mogao izdrzati... 
| Kod: |
#!/usr/bin/env perl
# Uzmite cetiri najjace karte (B, Q, K, A) u cetiri boje
# (pik, karo, herc, tref).
# Zadatak je sloziti karte u matricu 4x4, ali tako da se
# u svakom retku i stupcu svaka vrsta karte i svaka boja
# javlja tocno jednom.
use strict;
use integer;
my $cnt = 0;
my @desc;
foreach my $kind (qw(decko baba kralj as)) {
foreach my $color (qw(pik karo herc tref)) {
push @desc, sprintf("%10s", "$color $kind");
}
}
my $used = [ map { 0 } (0..15) ];
sub check1 {
my ($m, $el, $i, $step, $pos) = @_;
while ($i < $pos) {
return 0 unless ($m->[$i] - $el) % 4;
return 0 unless $m->[$i] / 4 - $el / 4;
$i += $step;
}
return 1;
}
sub check {
my ($m, $pos, $el) = @_;
return 0 unless check1($m, $el, $pos % 4, 4, $pos);
return check1($m, $el, 4 * ($pos / 4), 1, $pos);
}
sub put {
my ($m, $pos, $el) = @_;
if ($pos + 1) {
return unless check(@_);
$m->[$pos] = $el;
$used->[$el] = 1;
}
if ($pos >= 15) {
print "Rjesenje ".++$cnt.":\n";
for my $i (0..3) {
for my $j (0..3) {
print $desc[$m->[4 * $i + $j]], " ";
}
print "\n";
}
print "\n";
} else {
foreach my $e (grep { !$used->[$_] } 0..$#$used) {
put([ @$m ], $pos + 1, $e);
}
}
$used->[$el] = 0 if $pos + 1;
}
my $start = time();
put([], -1);
print "Time elapsed: ".(time() - $start)." sec\n";
|
Ispada da rjesenja ima 6912 (sto je slucajno 27*256=3^3*16^2). Malo sam ispao iz stosa, pa ne znam kako bih izracunao da li je to tocan rezultat.
Generiranje, ispis na ekran i u file, traju 91 sekundu na P2/333, s Perlom 5.6.0 na RedHatu 7.2. Dobiveni file je oko 1.5MB.
Btw, Nesi, mislim da nagrada ipak pripada tebi, jer sam ja koristio "tesku" artiljeriju... U svakom slucaju, cestitke na 3 kombinacije - ja nisam ni to nasao na ruke. 
Pozdrav!
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.  |
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
| Postano: 20:02 sub, 26. 10. 2002 Naslov: |
|
|
|
VSego, VSego..
Em se guras tamo gdje ti nije mjesto (koliko se sjecam polozio si kombinatoriku), em koristis kompjuter umjesto mozga...
Ali dobro, koristenje kompjutera i ostalih ortopedskih pomagala za mozak je legitimno. Problem je u tome sto se na taj nacin najcesce mogu rijesiti samo "mali" kombinatorni problemi, a za vece dolazi do pojave poznate kao kombinatorna eksplozija (samo bez straha, nece vam se raspuknuti vas novi PC :) )
Na primjer, problem s kartama zapravo je pitanje o postojanju ortogonalnih latinskih kvadrata reda 4. Detalje cete naci u Veljanovoj knjizi iz kombinatorike (novoj i staroj). Lako je napisati program koji ce rijesiti problem za red 4, ali pokusajte za red 10..
Evo precizne formulacije "Krcko's computer challenge"-a..
Treba konstruirati dvije 10x10 matrice A=[a_ij] i B=[b_ij] sa svojstvima:
1. Matrice su popunjene brojevima od 1 do 10
2. U svakom retku i stupcu svaki od brojeva javlja se tocno jednom (ovo vrijedi za matricu A i za matricu B)
3. Kad se matrice "poklope" svaki od 100 mogucih parova brojeva od 1 do 10 javit ce se tocno jednom. Preciznije, skup
{(a_ij,b_ij) | i=1..10, j=1..10}
ima 100 razlicitih clanova.
Dakle, trazi se par ortogonalnih latinskih kvadrata reda 10. Jedno rjesenje imate u knjizi, a zadatak je napisati program koji ce u razumnom vremenu pronaci nekoliko (ne sva!) rjesenja. Mislim da ce VSegov algoritam biti prespor, ali postoje algoritmi s kojima se to moze.
[b]Upozorenje:[/b] ovaj problem potjece od L.Eulera iz 1782. i bio je nerijesen sve do 1959. Dakle, uhvatite se toga samo ako vas stvarno zanima i ako imate vremena.. svi osim VSege, koji ga mora rijesiti za domacu zadacu :twisted:
VSego, VSego..
Em se guras tamo gdje ti nije mjesto (koliko se sjecam polozio si kombinatoriku), em koristis kompjuter umjesto mozga...
Ali dobro, koristenje kompjutera i ostalih ortopedskih pomagala za mozak je legitimno. Problem je u tome sto se na taj nacin najcesce mogu rijesiti samo "mali" kombinatorni problemi, a za vece dolazi do pojave poznate kao kombinatorna eksplozija (samo bez straha, nece vam se raspuknuti vas novi PC )
Na primjer, problem s kartama zapravo je pitanje o postojanju ortogonalnih latinskih kvadrata reda 4. Detalje cete naci u Veljanovoj knjizi iz kombinatorike (novoj i staroj). Lako je napisati program koji ce rijesiti problem za red 4, ali pokusajte za red 10..
Evo precizne formulacije "Krcko's computer challenge"-a..
Treba konstruirati dvije 10x10 matrice A=[a_ij] i B=[b_ij] sa svojstvima:
1. Matrice su popunjene brojevima od 1 do 10
2. U svakom retku i stupcu svaki od brojeva javlja se tocno jednom (ovo vrijedi za matricu A i za matricu B)
3. Kad se matrice "poklope" svaki od 100 mogucih parova brojeva od 1 do 10 javit ce se tocno jednom. Preciznije, skup
{(a_ij,b_ij) | i=1..10, j=1..10}
ima 100 razlicitih clanova.
Dakle, trazi se par ortogonalnih latinskih kvadrata reda 10. Jedno rjesenje imate u knjizi, a zadatak je napisati program koji ce u razumnom vremenu pronaci nekoliko (ne sva!) rjesenja. Mislim da ce VSegov algoritam biti prespor, ali postoje algoritmi s kojima se to moze.
Upozorenje: ovaj problem potjece od L.Eulera iz 1782. i bio je nerijesen sve do 1959. Dakle, uhvatite se toga samo ako vas stvarno zanima i ako imate vremena.. svi osim VSege, koji ga mora rijesiti za domacu zadacu
_________________
Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
| [Vrh] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol:
Lokacija: /sbin/init
|
| Postano: 2:55 uto, 29. 10. 2002 Naslov: |
|
|
|
Sreca moja da smo ovdje svi anonimni, pa nitko ne zna tko se krije iza nicka "vsego". 8)
Ostavio sam gore spomenutu masinicu da rijesi problem za n=6 (u malo modificiranom pocetnom programu). Naime, za n=6 nema rjesenja, dok za ostale ima. Eto, proslo je ravno 50 sati i masinica nije nista dala; opterecenje procesora je stalno bilo na 100%. Racunajte da je to masina od 663 MIPSa (millions instructions per second) i da 50 sati ima 180000 sekundi. Ako uzmemo da postoji overhead Perla i Linuxa, ali da nije velik (recimo 15ak MIPSa, mada mislim da je i to pretjerivanje), ostaje 650*180000 milijuna operacija. To je oko [b]117 trilijuna[/b] (ono iza milijarde) operacija, tj 117*10^12. Ipak, nije to nista naspram ukupnog broja kombinacija (kad se zanemare uvjeti na stupce i retke): 372*10^39. :shock:
Mislim da cemo masinica i ja na podulji odmor od Krckovih zadataka...
Sreca moja da smo ovdje svi anonimni, pa nitko ne zna tko se krije iza nicka "vsego". 
Ostavio sam gore spomenutu masinicu da rijesi problem za n=6 (u malo modificiranom pocetnom programu). Naime, za n=6 nema rjesenja, dok za ostale ima. Eto, proslo je ravno 50 sati i masinica nije nista dala; opterecenje procesora je stalno bilo na 100%. Racunajte da je to masina od 663 MIPSa (millions instructions per second) i da 50 sati ima 180000 sekundi. Ako uzmemo da postoji overhead Perla i Linuxa, ali da nije velik (recimo 15ak MIPSa, mada mislim da je i to pretjerivanje), ostaje 650*180000 milijuna operacija. To je oko 117 trilijuna (ono iza milijarde) operacija, tj 117*10^12. Ipak, nije to nista naspram ukupnog broja kombinacija (kad se zanemare uvjeti na stupce i retke): 372*10^39. 
Mislim da cemo masinica i ja na podulji odmor od Krckovih zadataka...
_________________ U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju. |
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
| Postano: 0:16 sri, 30. 10. 2002 Naslov: |
|
|
|
Eto, VSegovi trilijuni su pravi primjer kombinatorne eksplozije. Problem je za n=6 poznat kao "Eulerov problem 36 oficira". Taj problem nema rjesenja, tj. ne postoji par ortogonalnih latinskih kvadrata reda 6.
Zanimljivo je da je to dokazao izvjesni G.Tarry davne 1900. godine, dok racunala jos nisu ni postojala. Tarry naravno nije mogao ispitati trilijune mogucnosti. Identificirao je latinske kvadrate koji su ekvivalentni obzirom na permutacije redaka, stupaca, simbola i operacije slicne transponiranju. Postoji samo 12 neekvivalentnih latinskih kvadrata reda 6. Dovoljno je za tih 12 kvadrata dokazati da ne posjeduju ortogonalni par. To bi se danas pomocu racunala napravilo za cas, no Tarry se ipak posteno namucio. Njegov dokaz poznat je upravo po "mukotrpnosti" - konkurira mu jedino Hermesova konstrukcija pravilnog 65537-terokuta.
No vratimo se problemu s kartama. Pozivam Nesi da napise rjesenje, pa cemo proglasiti pobjednika i preci na novi zadatak...
Eto, VSegovi trilijuni su pravi primjer kombinatorne eksplozije. Problem je za n=6 poznat kao "Eulerov problem 36 oficira". Taj problem nema rjesenja, tj. ne postoji par ortogonalnih latinskih kvadrata reda 6.
Zanimljivo je da je to dokazao izvjesni G.Tarry davne 1900. godine, dok racunala jos nisu ni postojala. Tarry naravno nije mogao ispitati trilijune mogucnosti. Identificirao je latinske kvadrate koji su ekvivalentni obzirom na permutacije redaka, stupaca, simbola i operacije slicne transponiranju. Postoji samo 12 neekvivalentnih latinskih kvadrata reda 6. Dovoljno je za tih 12 kvadrata dokazati da ne posjeduju ortogonalni par. To bi se danas pomocu racunala napravilo za cas, no Tarry se ipak posteno namucio. Njegov dokaz poznat je upravo po "mukotrpnosti" - konkurira mu jedino Hermesova konstrukcija pravilnog 65537-terokuta.
No vratimo se problemu s kartama. Pozivam Nesi da napise rjesenje, pa cemo proglasiti pobjednika i preci na novi zadatak...
_________________
Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
| [Vrh] |
|
Nesi
Inventar Foruma
(Moderator)
Pridružen/a: 14. 10. 2002. (14:27:35)
Postovi: (E68)16
Spol:
Sarma: -
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
|
| [Vrh] |
|
Nesi
Inventar Foruma
(Moderator)
Pridružen/a: 14. 10. 2002. (14:27:35)
Postovi: (E68)16
Spol:
Sarma: -
|
|
| [Vrh] |
|
|
) da se ukljuce. Ne dopustite brucosima da budu brzi od vas! 