|
Titlul: problema permutari Scris de: Cristi din Decembrie 28, 2010, 17:49:57 Problema : sa se afle ordinul maxim al unei permutari din multimea Sn.
M-am gandit ca defapt trebuie sa aflu partitia numarului n astfel incat cmmc al numerelor a1 + a2 + ... ak = n sa fie maximal Dupa mai multe exemple am observat ca cmmc-ul acestor numere este maximal cand numerele sunt relativ prime ... am incercat sa fac un backtracking care tine cont de relatia intre numere ... Se poate mai eficient ? :-k Sa pornesc de la n = 1 si sa construiesc partitia ... ? Titlul: Răspuns: problema permutari Scris de: Paul-Dan Baltescu din Decembrie 28, 2010, 19:28:01 Se poate mai bine, folosind programare dinamica. Problema exista (http://infoarena.ro/problema/perm5) pe infoarena.
Titlul: Răspuns: problema permutari Scris de: Cristi din Decembrie 28, 2010, 21:52:35 o intrebare am ... rezolvarea cu PD se bazeaza tot pe faptul ca trebuie gasita partitia cu cmmc maximal nu ?
Titlul: Răspuns: problema permutari Scris de: Paul-Dan Baltescu din Decembrie 28, 2010, 22:40:31 Dap. :)
|