infoarena > infoarena - concursuri, probleme, evaluator, articole > Informatica > Subiect: Problema NP?
Pagini: [1]   În jos
« mesajul precedent următorul mesaj »
  Imprimă  
Ajutor Subiect: Problema NP?  (Citit de 1543 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« : Februarie 16, 2006, 21:22:09 »
Postez urmatoarea problema care mi-a venit in minte acum ceva timp si nu am reusit sa imi dau seama daca admite o rezolvare polinomiala. Voi ce credeti? Se poate rezolva polinomial sau e NP?

Citat
Se dau N numere naturale. Care este numarul maxim de numere din cele N care pot fi selectate astfel incat produsul lor sa fie patrat perfect? Numerele sunt naturale <= 10 000.
[/b][/color]

Eu am scos cel mai bine O(N * 2^D), unde D e numarul divizorilor primi din toate numerele.
Memorat
•greco
Nu mai tace
*****

Karma: 144
Deconectat Deconectat

Mesaje: 434



Vezi Profilul
« Răspunde #1 : Februarie 16, 2006, 22:27:33 »
Nu e NP, ti-am lasat un mesaj ca ma gandesc s-o punem pe infoarena la arhiva, asa ca nu mai dau alte sugestii aici pana nu vedem daca o punem sau nu.
Memorat
Jump in the cockpit and start up the engines
Remove all the wheelblocks there's no time to waste
Gathering speed as we head down the runway
Gotta get airborne before it's too late.
Pagini: [1]   În sus
  Imprimă  
infoarena > infoarena - concursuri, probleme, evaluator, articole > Informatica > Subiect: Problema NP?
 « mesajul precedent următorul mesaj »
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines