Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Probleme cu puncte laticiale  (Citit de 6984 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« : Aprilie 11, 2009, 16:08:12 »

Comentarii la articolul Probleme cu puncte laticiale scris de Cosmin Negruşeri.

Îi mulţumim Alexandrei Diculescu pentru că s-a implicat în transcrierea lui.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #1 : 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?  Think
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #2 : 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.
Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #3 : 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;
si trebuia
Cod:
 num += (N - h + 2) * (M - w + 2) * laux;
pentru ca N si M sunt numarul de randuri respectiv coloane deci numarul de puncte pe verticala este N+1 iar pe orizontala M+1.
Pot sa modific?
« Ultima modificare: Iulie 27, 2010, 12:03:33 de către Dragos » Memorat
andrei202
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #4 : 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
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #5 : 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)).
Memorat

Am zis Mr. Green
rares96cheseli
Client obisnuit
**

Karma: 45
Deconectat Deconectat

Mesaje: 60



Vezi Profilul
« Răspunde #6 : 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++)
    {
        for (int w=2; w<=h; w++)
        {
            aux=(h-2)*(w-2) + h*w - gcd[h-1][w-1]-2;
            num+=(n-h+2)*(m-w+2)*aux;
        }
    }
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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