|
Titlul: Problemă Scris de: FMI Razvan Birisan din Noiembrie 30, 2015, 19:52:57 Fie n și k două numere naturale. Definim m(k) = numărul minim de înmulțiri
pentru a obține nk. Spre exemplu, pentru k =15, avem m(15) = 5, întrucât: n * n = n^2 n^2 * n = n^3 n^3 * n^3 = n^6 n^6 * n^6 = n^12 n^12 * n^3 = n^15 Scrieți un program în C care calculează m(1) + m(2) + .... + m(200). Am nevoie doar de o idee de rezolvare ? De un hint, de orice m-ar putea ajuta să-mi dau seama cum aș putea rezolva problema... Titlul: Răspuns: Problemă Scris de: Mihai Calancea din Decembrie 01, 2015, 13:30:06 Din câte știu eu nu există soluție polinomială la problema asta. https://en.wikipedia.org/wiki/Addition-chain_exponentiation.
Unde ai găsit enunțul? Titlul: Răspuns: Problemă Scris de: George Marcus din Decembrie 01, 2015, 13:59:57 S-a dat o problema asemanatoare la nationala ACM din 2013: http://acm.tju.edu.cn/toj/vcontest/showp9268_C.html
Poate te ajuta acea solutie http://www.infoarena.ro/blog/acm-2013-etapa-nationala-partea-ii Titlul: Răspuns: Problemă Scris de: Mihai Calancea din Decembrie 01, 2015, 19:39:36 Cel puțin în cazul în care ai doar adunări, soluția aia e corectă doar fiindcă n e mic.. http://stackoverflow.com/a/15856054
Să tot vedem în concurs probleme deschise care ies banal (by pure chance) pe cazuri mici. Quality stuff. Titlul: Răspuns: Problemă Scris de: FMI Razvan Birisan din Decembrie 02, 2015, 19:35:29 Din câte știu eu nu există soluție polinomială la problema asta. https://en.wikipedia.org/wiki/Addition-chain_exponentiation. Unde ai găsit enunțul? E temă de laborator... și am încercat s-o rezolv cu programare dinamică, am căutat o formulă, apoi nu am mai avut idei. |