catanedelcu

RE:  :))

Cazimir

RE:  Dupa calculele mele, este o variatiune a Manhattan Distance
Cred ca esti mai familiar cu Manhattan Distance (MD) dacat sunt eu; pentru toata lumea, mai mult sau mai putin avizata, MD este distanta dintre 2 puncte p1=(x1, y1) p2=(x2, y2) calculata astfel: MD(p1, p2) = abs(x1-x2)+ abs(y1-y2). Deci pentru un dreptunghi cunoscut MxN, dimensiunile M si N sunt chiar abs(x1-x2), respectiv abs(y1-y2).
Aici vorbim de coordonate, dar in cazul problemei trebuie facut un artificiu, pentru ca fiecare patratel are o latime si o inaltime care trebuie luate in calcul.
Daca intr-un draptunghi MxN (M,N nr. nat.) atribuim coordonate fiecarui centru de patratel, MD al unei diagonale (din centru in centru, nu din colt in colt) este MD(M,N)=(M-1)+(N-1). La asta mai trebuie adaugat 1, pentru a lua 1/2 patrate la inceputul si 1/2 la sfarsitul diagonalei. Deci, nr de patratele taiate este: NP=MD(M,N)+1
Daca M si N nu sunt prime intre ele, atunci D=cmmdc(M,N) si M=DxA, N=DxB.In cazul asta, NP(M,N)=DxNP(A,B).
Pentru 3D, lucrurile stau aproape la fel, MD = (M-1)+(N-1)+(P-1) iar numarul de cuburi pentru MxNxP este NC=MD(M,N,P)+1.
Se face acelasi artificiu in cazul in care cmmdc(M,N,P) diferit de 1. In plus, chiar daca cmmdc =1, trebuie verificat daca oricare 2 dintre M, N, P sunt prime intre ele, caz in care se aplica formula din plan (vezi ex. nr. 2, N si P), plus a treia dimensiune (ex. 2, M), minus 1.
Aplicatii numerice:
1) M, N, P = 3, 4, 5
NC=(3-1)+(4-1)+(5-1)+1=10
2) M, N, P = 3, 4, 2
NC=NP(P,N)+(M-1)=NP(4,2)+(3-1)=2xNP(2,1)+2=2x[(2-1)+(1-1)+1]+2=2x[1+0+1]+2=6

P.S. Modelul l-am verificat pt foarte putine situatii concrete si a functionat pt fiecare. Daca gasesti vreun caz in care nu merge, mea culpa.