Koja je ideja za zadatak?
[Delioci]
Zar ti nije bolje da probas sam da ga resis, pa ako ne mozes, onda ce ti neko pomoci. Bar da napises sta si pokusao, pa ako se nekom jedan deo ideje poklapa sa tvojom, onda moze da ti objasni, a i ti vise tako da naucis...
Ako neces, ja cu ti objasniti svakako kako se resava, ali probaj prvo sam :), ako hoces...
Ako neces, ja cu ti objasniti svakako kako se resava, ali probaj prvo sam :), ako hoces...
Ne, slazhem se potpuno sa tobom, ali nisam uspeo da smislim ishta shto bi moglo da radi u nekom normalnom vremenu.
Jedna ideja, za koju znam da bi uspelo, je ova:
u tom skupu brojeva 1..2^31 ima samo nekoliko brojeva koji su mogutja reshenja. Kada bi ishao kroz sve brojeve od 1 do 2^31, svaki broj kod koga prvi put vidim max broj delioca vetji od proshlog m. b. d je potencijalno reshenje. Ako bi ja pustio rachunar da ide kroz sve te brojeve ovako:
max := 0;
stigaodo := 0;
for i := 1 to 2^32 do
if brojcif[i] > max then begin
max := brojcif [i];
inc (stigaodo);
writeln (t, 'a[', stigaodo, '] := ', i, ';');
end;
gde je t neki tekstualni fajl, ja bi u njemu imao potencijalna reshenja. Zatim uradim c/p u kod, i dalje je trivijalno. Ali to je kvarno, + potrebne su optimizacije kako bi on taj for uradio za najvishe 15 minuta recimo. Znam kako bi optimizovao, ali to nije pravo reshenje, kvarno je.
Druga ideja: broj delioca se lako mozhe dobiti kada broj rastavim na proste. Recimo, broj (2^3)*(3^2)*(5^1) ima sve delioce oblika (2^(0..3)) * (3^(0..2)) * (5^(0..1)), i samim tim ima 4 * 3 * 2 delioca.
Krenuo bi od broja 2.
Za svaki broj koji imam dosad, ja mogu da dobijem sledetji tako shto tju
1) pomnozhiti broj sa nekim njegovim prostim deliocem, i time ga umnozhiti za taj delioc a broj belioca pomozhiti sa ((na koji je stepen taj delioc bio + 1)/(na koji je stepen delioc bio). Ili mogu
2) dodati novi prost delioc, time udvostruchivshi broj delioca ali pomnozhivshi sam broj sa njim.
Tako bi ja trebalo da prosto uvetjavam broj dok on ne postaje najvetji mogutj, ali time sam isprobao sve mogutjnosti, poneke vishe puta (jer mogu uvetjati stepen dvojke, pa trojke ali i obratno). Ne vidim reshenje u tome, jer bi to na kraju ipak bilo gradjenje svih slozhenih brojeva. Za svaki bi odmah imao broj delioca, ne bi morao da ga rachunam shto je lepo. Ali opet mislim da je presporo.
A mogao bi i "dinamichki", da krenem for i := 2 to n i svaki broj gradim od proizvoda dva medjusobno prosta broja. Ali tu je problem shto bi svaki put trazhio dva medjusobno prosta broja chiji je proizvod i, shto je opet presporo.
Mozhda bi mogao neshto slichno, da generishem broj cifara za sve stepene dvoje, trojke, petice... gde je taj stepen <= n, i onda.. ma nemam pojma, i to bilo izrachunavanje zbira cifara svih brojvea 1..n, a to ne dolazi u obzir.
Imam ideje, ali ne vidim da je bilo koja tachno reshenje. Desilo mi se par puta da odbacim tachno reshenje, ali ovde ne verujem da je bilo koje izvodljivo.
Ajde dok sam ovde, pomozi mi oko zadatka Arhitekte. I za to sam imao vishe ideja, ali ni jednu za koju nisam nashto kontraprimer. Ako te zanima koje su, mogu i to da ispishem..
Jedna ideja, za koju znam da bi uspelo, je ova:
u tom skupu brojeva 1..2^31 ima samo nekoliko brojeva koji su mogutja reshenja. Kada bi ishao kroz sve brojeve od 1 do 2^31, svaki broj kod koga prvi put vidim max broj delioca vetji od proshlog m. b. d je potencijalno reshenje. Ako bi ja pustio rachunar da ide kroz sve te brojeve ovako:
max := 0;
stigaodo := 0;
for i := 1 to 2^32 do
if brojcif[i] > max then begin
max := brojcif [i];
inc (stigaodo);
writeln (t, 'a[', stigaodo, '] := ', i, ';');
end;
gde je t neki tekstualni fajl, ja bi u njemu imao potencijalna reshenja. Zatim uradim c/p u kod, i dalje je trivijalno. Ali to je kvarno, + potrebne su optimizacije kako bi on taj for uradio za najvishe 15 minuta recimo. Znam kako bi optimizovao, ali to nije pravo reshenje, kvarno je.
Druga ideja: broj delioca se lako mozhe dobiti kada broj rastavim na proste. Recimo, broj (2^3)*(3^2)*(5^1) ima sve delioce oblika (2^(0..3)) * (3^(0..2)) * (5^(0..1)), i samim tim ima 4 * 3 * 2 delioca.
Krenuo bi od broja 2.
Za svaki broj koji imam dosad, ja mogu da dobijem sledetji tako shto tju
1) pomnozhiti broj sa nekim njegovim prostim deliocem, i time ga umnozhiti za taj delioc a broj belioca pomozhiti sa ((na koji je stepen taj delioc bio + 1)/(na koji je stepen delioc bio). Ili mogu
2) dodati novi prost delioc, time udvostruchivshi broj delioca ali pomnozhivshi sam broj sa njim.
Tako bi ja trebalo da prosto uvetjavam broj dok on ne postaje najvetji mogutj, ali time sam isprobao sve mogutjnosti, poneke vishe puta (jer mogu uvetjati stepen dvojke, pa trojke ali i obratno). Ne vidim reshenje u tome, jer bi to na kraju ipak bilo gradjenje svih slozhenih brojeva. Za svaki bi odmah imao broj delioca, ne bi morao da ga rachunam shto je lepo. Ali opet mislim da je presporo.
A mogao bi i "dinamichki", da krenem for i := 2 to n i svaki broj gradim od proizvoda dva medjusobno prosta broja. Ali tu je problem shto bi svaki put trazhio dva medjusobno prosta broja chiji je proizvod i, shto je opet presporo.
Mozhda bi mogao neshto slichno, da generishem broj cifara za sve stepene dvoje, trojke, petice... gde je taj stepen <= n, i onda.. ma nemam pojma, i to bilo izrachunavanje zbira cifara svih brojvea 1..n, a to ne dolazi u obzir.
Imam ideje, ali ne vidim da je bilo koja tachno reshenje. Desilo mi se par puta da odbacim tachno reshenje, ali ovde ne verujem da je bilo koje izvodljivo.
Ajde dok sam ovde, pomozi mi oko zadatka Arhitekte. I za to sam imao vishe ideja, ali ni jednu za koju nisam nashto kontraprimer. Ako te zanima koje su, mogu i to da ispishem..
Sto se tice delioca...
Ona prva ti je dobra
Prvo ti nema potrebe da posmtaras za proste brojeve ciji proizvod sa manjim od tih daje broj preko 2^31, jer ces umesto tog broja moci da napises neki manji. Tih prostih ima 15-ak, proveri. Onda za svaki prost nadjes na koji stepen mozes da ga dignes a da na predje 2^31 (za 2 mozes 31 :)). Onda jednostavno probas da uparis redom kroz for petlju i to ide brzo jer imas malo stepena i malo prostih brojeva.
Jel' malo jasnije. Znaci nadjes za sve proste brojeve ciji proizvod ne prelazi 2^31, nadjes na koji stepen mozes da ih dignes i onda probas sve i to je to.
Za arhitektu cu malo kasnije :)
Ona prva ti je dobra
Prvo ti nema potrebe da posmtaras za proste brojeve ciji proizvod sa manjim od tih daje broj preko 2^31, jer ces umesto tog broja moci da napises neki manji. Tih prostih ima 15-ak, proveri. Onda za svaki prost nadjes na koji stepen mozes da ga dignes a da na predje 2^31 (za 2 mozes 31 :)). Onda jednostavno probas da uparis redom kroz for petlju i to ide brzo jer imas malo stepena i malo prostih brojeva.
Jel' malo jasnije. Znaci nadjes za sve proste brojeve ciji proizvod ne prelazi 2^31, nadjes na koji stepen mozes da ih dignes i onda probas sve i to je to.
Za arhitektu cu malo kasnije :)