Cerinţa
Se dau n numere naturale. Determinaţi o aranjare a acestor numere pe un cerc, astfel încât suma produselor de câte două numere vecine să fie maximă.
Date de intrare
Fişierul de intrare cerc.in conţine pe prima linie numărul n, iar pe a doua linie cele n numere naturale, separate prin spaţii.
Date de ieşire
Fişierul de ieşire cerc.out va conţine pe prima linie cele n numere, în ordinea determinată, separate prin exact un spaţiu.
Restricţii şi precizări
1 ≤ n ≤ 10
cele n numere vor avea cel mult 2 cifre
dacă există mai multe modalităţi de aranjare a numerelor astfel încât să se obţină aceeaşi sumă maximă, se va determina cea lexicografic minimă
nu inteleg ce e gresit
Anexe:
Răspunsuri la întrebare
Răspuns de
3
Cel mai simplu mod de a aborda problema e asa:
1. Sortezi vectorul de numere. Si acum ai conficuratia lexicografic cea mai mica.
2. Folosind backtracking, sau ce vrei tu, iei la rand toate permutarile posibile ale lui v, si cu doua variabile memorezi, atunci cand gasesti, scorul maxim(strict mai mare decat precedentul scor maxim) si permutarea vectorului care da acel scor(scorul fiind acea suma de produse).
Initial variabila cu scor maxim va fi scorul permutarii initiale a vectorului si vectorul cu aranjamentul maxim e doar o copie a vectorului initial.
Gata!
Iti las si o implementare ceva mai avansata dar care urmeaza chiar metoda asta, dar e mai avansata, in caz ca vrei sa te bati cu ea:
1. Sortezi vectorul de numere. Si acum ai conficuratia lexicografic cea mai mica.
2. Folosind backtracking, sau ce vrei tu, iei la rand toate permutarile posibile ale lui v, si cu doua variabile memorezi, atunci cand gasesti, scorul maxim(strict mai mare decat precedentul scor maxim) si permutarea vectorului care da acel scor(scorul fiind acea suma de produse).
Initial variabila cu scor maxim va fi scorul permutarii initiale a vectorului si vectorul cu aranjamentul maxim e doar o copie a vectorului initial.
Gata!
Iti las si o implementare ceva mai avansata dar care urmeaza chiar metoda asta, dar e mai avansata, in caz ca vrei sa te bati cu ea:
Anexe:

Alte întrebări interesante
Ed. muzicală,
8 ani în urmă
Ed. tehnologică,
8 ani în urmă
Matematică,
9 ani în urmă
Limba română,
9 ani în urmă
Limba română,
9 ani în urmă
Matematică,
9 ani în urmă
Limba română,
9 ani în urmă