[es] - Zanimljiv zadatak za razmisljanje.

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
..-chandran.sbs.auckland.ac.nz

Profil

^{02.02.2004. u 03:38}

Ko hoce da vezba vijuge moze da pokusa da resi ovaj zadatak.

Prvo mali zadacic za vezbu. Ako imamo neku permutaciju brojeva od 1 do n i ako ta prva permutacija predstavlja nacin kako premestamo brojeve koliki je minimalni broj koraka da bismo dobili pocetnu permutaciju. Evo primera. Imamo permutaciju (3,1,2,4). Svaki broj u permutaciji oznacava na koje mesto treba premestiti odgovarajuci broj.
U prvom koraku ce (3,1,2,4) da predje u (1,2,3,4)
U drugom koracu ce (1,2,3,4) da predje u (2,3,1,4) (premestanje radimo u skladu sa pocetnom permutacijom (3,1,2,4))
U trecem koraku ce (2,3,1,4) preci u (3,1,2,4)

Znaci trebalo nam je 3 koraka. Znaci u prvom zadatku nadjite minimalni broj koraka menjanja permutacije da bi smo dobili pocetnu permutaciju.
To je lak zadatak, a sad malo tezi.

Treba napraviti algoritam koji za uneti broj n odstampa jednu permutaciju koja ce zahtevati maksimalni broj koraka da bismo dobili pocetnu permutaciju.
Prakticno trazimo maksimum svih minimuma svih mogucih permutacija.

^{02.02.2004. u 03:38}

noviKorisnik

Član broj: 13216
Poruke: 4516
*.bankmeridian.com

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{02.02.2004. u 06:59}

Ubih se da dešifrujem navedeni primer. Da ponovim šta predstavlja:

Imamo (3, 1, 2, 4). Premeštanje u skladu s permutacijom znači ovde da prvi član permutacije (trojka) ide na treću poziciju (baš zbog te trojke). Dalje, drugi član (jedinica) ide na prvu poziciju, pa treći član ide na drugu i četvrti ostaje na četvrtoj. Tako se dobija (1, 2, 3, 4).
Dalje opet po pravilu: prvi na treću, drugi na prvu i treći na drugu poziciju...

Da postavim smelu hipotezu: za svaku permutaciju od 1 do n se po ovoj igri nakon prvog koraka dobija (1, 2, ..., n).

^{02.02.2004. u 06:59}

sosa

Član broj: 19777
Poruke: 12
*.kotor.cg.yu

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{02.02.2004. u 08:57}

Sto se tice smelosti, bio si u pravu, jeste uvek pocetna permutacija.
Sto se tice ovog maksimuma, rekla bih da je to permutacija koja ima redni broj
1+(n!/2) gde pod rednim brojem podrazumevam leksikografski redosled permutacija, pa onda njenu poziciju u tom redosledu.

^{02.02.2004. u 08:57}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
..-chandran.sbs.auckland.ac.nz

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{02.02.2004. u 22:36}

Pa nije bas. Tih permutacija ima dosta a tvoj algoritam treba da ispise bilo koju od njih.
Probaj prvo da resis laksi deo zadatka. Znaci da nadjes posle koliko koraka se dobija pocetna permutacija. To ne bi trebalo da bude bruteforce jer to dosta traje za neke permutacije od npr. 100 brojeva. Probaj matematicki da vidis koliko koraka je potrebno. Ako permutaciju predstavis grafom mozda ce ti biti lakse da dodjes do resenja.

^{02.02.2004. u 22:36}

sosa

Član broj: 19777
Poruke: 12
*.kotor.cg.yu

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{03.02.2004. u 08:41}

Naravno da ima mnogo permutacija, pogotovo za veliko n...
Jos jednom da ponovimo, zadas n i trazis permutaciju koja ce imati najvise koraka da bi se premestanjem koje ona definise, vratili do pocetne permutacije. Da li je tako?
Pod pretpostavkom da je to tako, mislim da je trazena permutacija (jedna od onih koja zadovoljava zadati kriterijum) permutacija koja se nalazi na poziciji 1+(n!/2), a da se ona posle generise nije tesko.

^{03.02.2004. u 08:41}

noviKorisnik

Član broj: 13216
Poruke: 4516
*.bankmeridian.com

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{03.02.2004. u 10:23}

Svodi se na cikluse u grafu.

U primeru (3, 1, 2, 4) postoje 2 ciklusa: prvi ciklus su pozicije 1, 2 i 3, a drugi pozicija 4.
Dužina svakog ciklusa jednaka je broju pozicija u njemu, predstavlja broj koraka do povratka u početno stanje. U primeru je prvi ciklus dužine tri, a drugi dužine jedan.
Zbir dužina jednak je ukupnom broju pozicija - u primeru je to četiri.
Broj koraka do rešenja je najmanji zajednički sadržilac dužina svih ciklusa. U primeru su tri koraka (3 * 1 = 3).

Problem se preslikava na rastavljanje broja na sabirke tako da se dobije maksimum najmanjeg zajedničkog sadržioca sabiraka. U primeru:
4 = 4 => 4
4 = 3 + 1 => 3
4 = 2 + 2 => 2
4 = 2 + 1 + 1 => 2
4 = 1 + 1 + 1 + 1 => 1

A to je već neka druga matematika...

^{03.02.2004. u 10:23}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
..-chandran.sbs.auckland.ac.nz

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{03.02.2004. u 20:58}

Citat:

sosa:
Naravno da ima mnogo permutacija, pogotovo za veliko n...
Jos jednom da ponovimo, zadas n i trazis permutaciju koja ce imati najvise koraka da bi se premestanjem koje ona definise, vratili do pocetne permutacije. Da li je tako?

Tako je! I trazim broj koraka. U stvari i ne moras da das permutaciju, dovoljno je broj koraka jer ako znas da napravis algoritam za to onda je lako naci i permutaciju.

Citat:

Pod pretpostavkom da je to tako, mislim da je trazena permutacija (jedna od onih koja zadovoljava zadati kriterijum) permutacija koja se nalazi na poziciji 1+(n!/2), a da se ona posle generise nije tesko.

Nisi u pravu.
Evo za n=4 ti mislis da je trazena permutacija 3124 sto nije tacno jer nam to daje samo 3 koraka a maksimalno je 4 kako je to novikorisnik pokazao.

^{03.02.2004. u 20:58}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
..-chandran.sbs.auckland.ac.nz

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{03.02.2004. u 21:06}

Citat:

noviKorisnik:
Svodi se na cikluse u grafu.

Tako je! Mada nije trebalo da vam kazem da crtate graf, bilo bi zanimljivije da ste se sami setili toga :-)

Citat:

Broj koraka do rešenja je najmanji zajednički sadržilac dužina svih ciklusa.

Bravo! Resio si pola zadatka. To je laksi deo. Sada treba naci maksimum svih NZS-ova.

Recimo za n=5 najbolje je da imas dva ciklusa, jedan duzine 2 i jedan duzine 3 i to ce ti dati NZS=6
Posle kako izaberes te cikluse je manje bitno. Fora je naci duzine ciklusa koje daju najveci NZS.

^{03.02.2004. u 21:06}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
..-chandran.sbs.auckland.ac.nz

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{04.02.2004. u 03:35}

E da, maksimum NZS-ova mislim da ne moze da se nadje nekom formulom vec treba da smislis neki algoritam koji ce brzo da da resenje.

^{04.02.2004. u 03:35}

noviKorisnik

Član broj: 13216
Poruke: 4516
*.bankmeridian.com

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{04.02.2004. u 07:35}

Što već neko nije našao formulu?
Da, tek sam skontao da tema nije u forumu matematike. Nešto lepo da se isprogramira. Brute force?

Opet jedna hipoteza: traženi maksimum ima za sabirke samo proste brojeve i njihove stepene.

Odakle mi ovo? Ako su sabirci takvi, NZS će biti njihov prost proizvod...

... i kad dobijemo tražene sabirke (po algoritmu brute force ili onom koji tek treba da se pojavi), kako prikazati jednu od permutacija iz skupa rešenja?

Primer:
za n = 10 rešenje je iz tri ciklusa, po rastavljanju 10 = 2 + 3 + 5.
permutacija (2, 1, 5, 3, 4, 10, 6, 7, 8, 9) dobija se cikličnim šiftovanjem prva dva elementa (1, 2 -> 2, 1), zatim sledeća tri (3, 4, 5 -> 5, 4, 3) i poslednjih pet (? -> ?).

...

Zadatak za Art of Programming:
- odrediti funkciju koja za parametar ima prirodni broj i koja vraća niz sabiraka tog broja, takav da je najmanji zajednički sadržilac sabiraka maksimalan.

^{04.02.2004. u 07:35}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
*.dialup.xtra.co.nz

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{04.02.2004. u 13:23}

Citat:

noviKorisnik:
Što već neko nije našao formulu?

Ne znam. Ovaj zadatak je cini mi se bio na jednoj olimpijadi iz programiranja.

Citat:

Opet jedna hipoteza: traženi maksimum ima za sabirke samo proste brojeve i njihove stepene.

Tacna ti je hipoteza.

Citat:

... i kad dobijemo tražene sabirke (po algoritmu brute force ili onom koji tek treba da se pojavi)

Nemoj molim te brute force :-))
Zadatak je naci neki algoritam koji ce ti odmah napisati resenje. Ne treba ni sekunda da prodje.

Citat:

, kako prikazati jednu od permutacija iz skupa rešenja?

Bas na nacin kako si pokazao. Resio si sve matematicki sta je moglo matematicki a sada ostaje da se nadje neki lep algoritam koji ce da resi problem. Ja sam koristio dinamicko programiranje.

Citat:

Zadatak za Art of Programming:
- odrediti funkciju koja za parametar ima prirodni broj i koja vraća niz sabiraka tog broja, takav da je najmanji zajednički sadržilac sabiraka maksimalan.

Upravo na ovo se svodi pocetni zadatak. To je najvazniji i najtezi deo.

^{04.02.2004. u 13:23}

noviKorisnik

Član broj: 13216
Poruke: 4516
*.bankmeridian.com

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{04.02.2004. u 14:50}

Citat:

...a sada ostaje da se nadje neki lep algoritam koji ce da resi problem. Ja sam koristio dinamicko programiranje.

Voleo bih da vidim tvoje rešenje - recimo za dva dana - bez obzira da li se u međuvremenu postavi neka ispravna funkcija.

^{04.02.2004. u 14:50}

noviKorisnik

Član broj: 13216
Poruke: 4516
*.bankmeridian.com

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{05.02.2004. u 14:43}

Evo malo JS

Code:
function maxnzs (remain, index, product)
{
  if (remain <= 1) return product;
  var el = prim.get (index);
  if (remain < el) return 1;

  var newproduct = 1;
  var elval = 1;
  var newremain = remain;
  var mymax = 1;

  do
  {
    newproduct = maxnzs (newremain, index + 1, product * elval);
    if (newproduct > mymax) mymax = newproduct;
    elval *= el;
    newremain = remain - elval;
  } while (newremain >= 0);

  return mymax;
}

prim je jedan pametni niz prostih brojeva.
prim.get (index) vraća prosti broj odgovarajućeg indexa: 0 => 2, 1 => 3, 2 => 5, ...

funkcija vraća mahimalni nzs svih kombinacija sabiraka prirodnog broja (po hipotezi da se rešenje sastoji samo od prostih brojeva i njihovih stepena).

poziv funkcije nije proizvoljan, već oblika maxnzs (broj, 0, 1) - za kršenje ovog pravila ne snosim posledice.

i konačno, tu je zakačena kompletna aplikacija koja daje, recimo za pomenuti ulaz 10:

Citat:

number: 10

maxnzs: 30

elements: 2,3,5

one solution: (2,1,4,5,3,7,8,9,10,6)

stats: 28 calls of maxnzs ()
maxdepth: 4

Prikačeni fajlovi

srki.zip - 1.3k

^{05.02.2004. u 14:43}

StMilan

Član broj: 5061
Poruke: 144
*.ptt.yu

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{06.02.2004. u 07:02}

Poznat mi je ovaj zadatak, bavio sam se ja svojevremeno dosta tim takmicenjima iz programiranja.
Ono sto se secam, probacu da nadjem neki kontraprimer, je da dinamicko programiranje ne mora da da tacno resenje za ovaj problem. U vecini slucajeva hoce, ali generalno mislim da sam problem ne zadovoljava neke kriterijume za optimalnost resenja dinamickim programiranjem. (tu postoje neke matematicke strukture, matroidi, zaboravio sam vec sve to sad).
Cak nisam ni siguran da hipoteza o prostim brojevima stoji.

Naravno, ovo su samo moja secanja dok ne nadjem kontraprimer.

Mada sam i ja ovako resavao taj zadatak na jednom takmicenju, tamo je formulacija bila o nekoj deci koja prave neki krug i igraju ili tako nesto, nebitno.

^{06.02.2004. u 07:02}

noviKorisnik

Član broj: 13216
Poruke: 4516
*.bankmeridian.com

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{06.02.2004. u 12:50}

Šta mu dođe pojam dinamičkog programiranja? Ja ili pojma nemam ili sam zaboravan. Hajde, da znam o čemu se priča.

Interesuje me sada kakvu primenu može da ima ova tema (neka permutacija, je li). Neko kriptovanje?

I još jedno pitanje: koliko ima rešenja za dato n?

^{06.02.2004. u 12:50}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
*.dialup.xtra.co.nz

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{06.02.2004. u 17:26}

Citat:

StMilan:
Ono sto se secam, probacu da nadjem neki kontraprimer, je da dinamicko programiranje ne mora da da tacno resenje za ovaj problem.

Ovo mi nije jasno. Pa dinamicko programiranje ne menja resenje vec samo nacin dolazenja do resenja tako sto npr. pamtis u nekom nizu/matrici medju korake.

Citat:

Cak nisam ni siguran da hipoteza o prostim brojevima stoji.

Pa uvek mozes da imas neki ostatak ali fazon je da se prvo biraju prosti brojevi i njihovi stepeni ali moze da se desi da ti ostane neki ostatak koji ne mozes da iskoristis.

^{06.02.2004. u 17:26}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
*.dialup.xtra.co.nz

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{06.02.2004. u 17:36}

Citat:

noviKorisnik:
Šta mu dođe pojam dinamičkog programiranja? Ja ili pojma nemam ili sam zaboravan. Hajde, da znam o čemu se priča.

Pa to ti je ono kad pamtis medju korake pa ih iskoristis kada ponovo naletis na njih a ne da ides stalno u rekurziju. Tako bi ti mogao da unapredis tvoju funkciju mada ono radi dovoljno brzo i kada uneses broj 100. Cekas samo par sekundi, mada kada sam ja to resavao imao sam 25 Mhz pa bi tvoje resenje radilo malo duze dok je moje trenutno davalo rezultat. Probaj da napravis algoritam tako da ti ne ide uvek u rekurziju nego iskoristi to ako je vec prolazio kroz tu funkciju sa istim argumentima. Kao kada pravis program za nalazenje puta kroz lavirint pa umesto da svaki put ides na nove 4 strane ti pamtis u matrici da li si bio na tom novom polju i koliko ti je koraka trebalo pa ako je bilo potrebno manje koraka ti onda ne ulazis u rekurizju.

Inace ne radi ti program u svim slucajevima. Moj program za broj 100 daje sledece resenje:
100 *** Niz: 19 17 13 11 7 5 9 16 3 NZS: 232792560
a tvoj daje manji NZS.
Isto tako i za recimo 21
21 *** Niz: 7 5 3 4 2 NZS: 420
a tvoj daje NZS 330

Citat:

Interesuje me sada kakvu primenu može da ima ova tema (neka permutacija, je li). Neko kriptovanje?

Pa mozda, nisam se bavio time. Znam da PGP algoritam koristi velike proste brojeve pa isto ima permutaciju kojom kriptuje. Ti kada bi odredjen broj puta kriptovao informaciju sa istim kljucem dobio bi pocetnu informaciju. Ali problem je sto to zahteva puno vremena pa je zato prakticnije da probas nekim algoritmima da nadjes kontra-permutaciju kojom mozes da iz kodirane informacije dobijes originalnu.

^{06.02.2004. u 17:36}

noviKorisnik

Član broj: 13216
Poruke: 4516
*.041net.co.yu

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{07.02.2004. u 10:19}

U pravu si za ove primere. Umesto

Code:
if (remain <= 1) return product;
var el = prim.get (index);
if (remain < el) return 1;

bolje je

Code:
var el = prim.get (index);
if (remain < el) return product;

i još neke sitnije izmene u ostatku za ispravan ispis rešenja. To je opet u fajlu uz poruku.

Kako da budemo sigurni da je rešenje pravo, ako nigde ne stoji dokaz hipoteze o obliku rešenja?

Srki, stigao je red da objaviš svoje rešenje...

Prikačeni fajlovi

srki2.zip - 1.32k

^{07.02.2004. u 10:19}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
*.dialup.xtra.co.nz

Profil

Re: Zanimljiv zadatak za razmisljanje.

^{07.02.2004. u 13:40}

Citat:

noviKorisnik:
Kako da budemo sigurni da je rešenje pravo, ako nigde ne stoji dokaz hipoteze o obliku rešenja?

Pa to je izuzetno prosto dokazati. Pretpostavimo da je jedan od sabiraka (duzina jednog ciklusa) oblika

gde je p neki prost broj a s broj ciji faktori nemaju broj p. Bolje bi bilo to rastaviti na

i da dobijemo jos neki ostatak koji mozda mozemo nekako da iskoristimo u nekom drugom sabirku a NZS se pritome ne smanjuje.
To da se dobije jos neki ostatak se lako dokaze. Ako je npr.

onda
je bolje da to rastavimo u zbir jer je

Citat:

Srki, stigao je red da objaviš svoje rešenje...

Evo sada sam ga pola sata trazio po cd-ovima (bolje da sam ponovo napisao resenje). Ovaj program sam napisao pre 8 godina dok sam jos bio u srednjoj skoli jer mi je tada nastavnik iz assemblera dao taj zadatak da resim.
Resenje je zakacrno uz poruku (valjda radi, nisam probao sada).
Ako ne uspes da ga provalis vrlo rado cu ga objasniti.

Prikačeni fajlovi

Particij.pas - 1.56k

^{07.02.2004. u 13:40}