jako-ongelma?

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Moneenko yhtäsuureen osaan positiivinen luku a on jaettava, jotta osien tulo olisi mahdollisimman suuri?

Kommentit (8)

Vierailija

Öhh.. luulisin että mahd. moneen että tulee kakkosia. Jos a = 10, niin 2^5 taitaa olla suurin mihin päästään? En tiedä sitten jos vaikka a = 17.. luulisin että suurin on 2^8*1.. eipäs olekaan. 3^5*2 on isompi.

Vierailija
Päivystävä dosentti
Suunnilleen a/e osaan, missä e on Neperin luku. Esimerkiksi 1000 kannattaa jakaa 368 osaan ja 1000/e = 367,879...

..heti paljastui ongelman ratkaisu.
mutta todistuskin olisi mukava nähdä.
Onhan se todistettava, että tehtävässä kasvun raja liittyy neperin lukuun..

Vierailija

public class max
{
static int max = 0, maar = 0, pit_min = -1;
static String tulot;
public static void main(String[] args)
{
int a = 30; // luku

int raja = (int) (a / 2.718281828459) + 1;
int alku = raja - 3;
if (alku < 1)
alku = 1;

for (int pal = alku; pal <= raja; pal++)
osiin(a, pal, "", 1, 0);
System.out.println(tulot + " = " + max);
System.out.println(maar + " rekursiota");
}
public static void osiin(int a, int m, String k, int t, int p)
{
maar++;
if (m == 1 || a < 4)
{
k += a;
t *= a;
if (t > max || (t == max && (pit_min == -1 || p < pit_min)))
{
pit_min = p;
max = t;
tulot = k;
}
}
else for (int i = 2; i < a-1; i++)
osiin(a - i, m - 1, k + i + "*", t * i, p+1);
}
}[/code:3ri8sjqo]

Tuossa tuommoinen javapätkä.. on vähän hidas kun a > 30... kai sitä voisi jotenkin vielä optimoida. En ole ihan varma että toimiiko tuo "alku" muuttuja oikein.. ts. löytääkö aina oikean ratkaisun. Löytää ainkin jos alku on aina 1. Vähän kiireessä tein loppuun kun kaverit soittelee

======
edit: tämmöisen likiarvokaavan katsoin:
max = 0,92031991698683*1,445433800631^a

kun a = 1, 2, 3, ... , 29, 30 se heittää keskimäärin 4,1%. Taitaa tulla tarkemmaksi kun a kasvaa... esim. kun a=35 se heittää 3,4% ja kun a=36, se heittää enää 0,36%

Vierailija
msdos464
Tuossa tuommoinen javapätkä.. on vähän hidas kun a > 30... kai sitä voisi jotenkin vielä optimoida.

Niin, Javallahan ei tosiaankaan kannata tehdä numeerista laskentaa, vaan esim. C tai Fortran ovat huomattavasti tehokkaampia.

Alkuperäiseen kysymykseen saatiinkin jo vastaus, mutta sen osoitusta kyseltiin. No, kirjoitetaanpa se nyt auki (tuskin kyseessä mikään läksytehtäväkään oli kun on kesä):
Jos a jaetaan x:ään samankokoiseen osaan, näiden tulo on f(x) = (a/x)^x. Tämän funktion maksimi on sen derivaatan f'(x) = (a/x)^x * (ln(a/x)-1) nollakohdassa x = a/e. Kun x:n haluttiin olevan kokonaisluku, valitaan tästä joko suurempi tai pienempi, kumpi antaakaan suuremman tulon.
Ei siinä tuon ihmeempiä temppuja tarvita.

Vierailija

Oho se tosiaan oli yhtäsuureen osaan... ajattelin että jos vaikka 12 jaetaan 3 osaan niin yksi mahdollisuus on 3*4*5. Ilmankos tuo ohjelma on vähän hidas Se kun alunperin kävi kaikki jakovaihtoehdot läpi.

Vierailija
murikka
Kun x:n haluttiin olevan kokonaisluku, valitaan tästä joko suurempi tai pienempi, kumpi antaakaan suuremman tulon.

Melkein aina suuremman tulon antava kokonaisluku saadaan yksinkertaisesti pyöristämällä a/e.

Jatkokysymys: Joillekin reaaliluvuille a yksinkertainen pyöristys ei toimi (esimerkiksi a=9,5). Onko tällaisia kokonaislukuja?

Uusimmat

Suosituimmat