infoarena

Elaborati un program care descompune numarul natural n in suma de numere naturale n=p1+p2+...+pk astfel incat produsul lor p=p1*p2*...*pk sa fie maxim. Programul va citi numarul n (n£ 50) si va afisa produsul p.

asa cam stiu cum s-ar putea face...dar implementarea nu prea stiu cum s-o fac.....deci io as zice asa ca termenii >=2 si sa fie cat mai multi pentru ca p-u sa fie mare

de ex :n=11 -->p=54             11=2+9(18)   =2+2+7(28)...si tot asa incerc sa caut un maxp...

daca ma poate ajuta careva cu indicatii....

Problema este aceasta (http://acm.timus.ru/problem.aspx?space=1&num=1222). Nu imparti in mai multe 2-uri. Pentru 6 cum faci ? Sper sa te prinzi. Spor :).

pai io asa m-am gandit.......deci scrii de ex: 6= 2+4(aici compar cu pmax)
                                                                   2+2(si aici....)             ===>ramane 24


io ma gandesc sa scriu n-u ca suma de 2+n-2(compar) ....cum ar fii la 11 de ex ii 2+9(compar)
                                                                                                                2+7(compar)
                                                                                                                    2+3(compar) si atat ca daca cresc 2 si scad 3 ii acelasi lucru atunci.....il scriu pe 7 ca 3+4 (compar)...si atat ca iara incalca conditia a>=a[i-1] apoi scriu pe 9 ca 3+6(compar)....si tot asa pana la sf.... nu-i buna ideea?:-/ io zic ca mere.....nu stiu la ce te-ai referit ca la 6 nu mere....:P..                                                                               

Pt 6 cred ca e mai buna descompunerea 3 + 3. E produsul 9 > 2 * 4.

pai da la 6 = 2+4(compar)
                     2+2(compar)
scriu pe 6=3+3........imi da niste indicatii de rezolvare...dari io zic ca metoda mea ii buna....:Pmi-o iesit si la 6 p=9
                     

Incearca sa te exprimi clar si sa scrii corect, respectand regulile de punctuatie. Am incercat sa iti citesc posturile insa mi-am pierdut rabdarea incercand sa inteleg ce vrei sa spui.

Problema a fost data si aici: http://infoarena.ro/blog/problema-saptamanii-produs (http://infoarena.ro/blog/problema-saptamanii-produs).
Solutia o gasesti tu, tot pe blog.

ok......o solutie ar mai fii sa sa generez toate partitiile numarului(cu backtr) in afara de alea cu 1+.... si ca sa evit chestii de genu 2+3.. si 3+2 le scriu crescator....si caut cel mai mare produs.......asta cred ca mere daca n=50 da la n<=3000 oare mai ii eficienta:-/

Ti-am zis, incearca sa te prinzi pentru 6, 7, 8, 9, 10, .. 15 si o sa observi o regula.

Cred ca ar merge si io dinamica de genul A[ i ] = max {A[ i-1 ] *1, A[ i-2] *2, ... A[ 1 ] * (i-1)}

Asa ai o complexitate de o(N^2). Rezolvarea este logaritmica, in loc de 3000 mergea si 1 miliard, doar ca aveai foarte multe cifre la rezultat.

ms :D