|
Titlul: Probleme cu puncte laticiale Scris de: Marius Stroe din Aprilie 11, 2009, 16:08:12 Comentarii la articolul Probleme cu puncte laticiale (http://infoarena.ro/probleme-cu-puncte-laticiale) scris de Cosmin Negruşeri (http://infoarena.ro/utilizator/cosmin).
Îi mulţumim Alexandrei Diculescu (http://infoarena.ro/utilizator/portocala) pentru că s-a implicat în transcrierea lui. Titlul: Răspuns: Probleme cu puncte laticiale Scris de: Florian Marcu din Aprilie 30, 2009, 18:27:19 Legat de problema #7 ( paralelograme ): Spre sfarsitul explicatiei de la rezolvare, se da urmatoarea idee de optimizare:
Citat Mai putem optimiza factorii constanţi ai soluţiei observând că într-un triunghi de dimensiuni H * W poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un triunghi W * H. Acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri. La ce triunghiuri se refera? :-kTitlul: Răspuns: Probleme cu puncte laticiale Scris de: Cosmin Negruseri din Aprilie 30, 2009, 21:55:46 Am corectat la dreptunghi.
Cand vezi ceva gresit poti sa corectezi chiar tu. Siteul este wiki si va incurajam sa fiti activi nu pasivi. Titlul: Răspuns: Probleme cu puncte laticiale Scris de: Dragos din Iulie 24, 2010, 16:47:28 La problema 5 avem formula 4 * ((H - 1)(W - 1) + H - 1 + W - 1).
Factorul 4 reprezinta cele 4 pozitii ale primului punct. Produsul (H - 1)(W - 1) toate perechile care se pot forma intre ultimele H-1 puncte de pe verticala si primele W-1 puncte de pe orizontala? H-1 repezinta numarul de puncte de pe verticala pe care le putem imperechea cu al W-lea de pe orizontala? Iar W-1 reprezinta numarul de puncte de pe orizontala pe care le putem imperechea cu primul de pe verticala? Later edit: Iar la problema 7 avem h * w - cmmdc(h - 1, w - 1) - 2 posibilităţi Pentru diagonala avem cmmdc(h - 1, w - 1) +1 posibilitati si mai eliminam un 1 deoarece putem obtine un patrat de 2 ori? (Scuzati-ma daca nu se intelege bine ce am scris). Later later edit: Si tot la problema 7 la seventa de cod este o mica greseala. Este scris: Cod: num += (N - h + 1) * (M - w + 1) * laux; Cod: num += (N - h + 2) * (M - w + 2) * laux; Pot sa modific? Titlul: Răspuns: Probleme cu puncte laticiale Scris de: Tulus Andrei din Aprilie 22, 2011, 10:05:40 in legatura cu problema 6 nu am inteles de unde il iau pe H si W pt ca in enunt mi se da doar N si M
Titlul: Răspuns: Probleme cu puncte laticiale Scris de: Paul-Dan Baltescu din Aprilie 22, 2011, 12:16:43 Citat Astfel, în O(H) vom şti numărul de dreptunghiuri înscrise într-un dreptunghi de dimensiuni H * W. Acest dreptunghi poate fi pus în (N - H + 1) * (M - W + 1) locaţii pe o grilă de dimensiune N * M. Deci, soluţia are complexitate O(N*M^2), pentru fiecare dreptunghi de dimensiuni 1 ≤ H ≤ N şi 1 ≤ W ≤ M calculându-se numărul de dreptunghiuri înscrise. Cum e precizat mai sus, ideea e sa alegi toate perechile (H,W) cu 1 <= H <= N si 1 <= W <= M, iar pentru fiecare pereche in parte sa calculezi in O(H) numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H si W, folosind indicatiile din primele paragrafe. Acest numar va trebui inmultit cu numarul de amplasari posibile ale unui astfel de dreptunghi (adica (N - H + 1) * (M - W + 1)). Titlul: Răspuns: Probleme cu puncte laticiale Scris de: Rares Cheseli din Mai 28, 2013, 21:38:10 La problema 7 cum pot folosi faptul ca într-un dreptunghi de dimensiuni H * W poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un dreptunghi W * H?
am incercat sa fac asa dar nu da rezultat bun : Cod: for (int h=2; h<=max(m, n)+1; h++) |