I find an easier non-recursive solution to compute the rectangle
number (represented as RN) of an h x w rectangle (which has a height
of h units and a width of w units):
Situation 1. if (h and w are coprime) or (h = 1) or (w = 1), then RN =
h + w - 1
Situation 2. if h and w are not relatively prime, we can find the
greatest common divisor (represented as gcd) that makes
(1) h = h' x gcd, w = w' x gcd.
and
(2) (h' and w' are coprime) or (h' = 1) or (w' = 1).
then RN = (h' + w' - 1) x gcd
On Aug 23, 8:37 am, Nikhil Jindal <[email protected]> wrote:
> Here's my try:
>
> The following function returns the rectangle number given the dimensions of
> the rectangle.
>
> int FindRectangleNumber(int row, int colm)
> {
> if (row == colm)
> return row;
> if (row == 1)
> return colm;
> if (row%2 == 0 && colm%2 == 0)
> return 2*FindRectangleNumber(row/2, colm/2);
> if (row%2 == 1 && colm%2 == 0)
> return FindRectangleNumber(row - 1, colm) + 2;
> if (row%2 == 0 && colm%2 == 1)
> return FindRectangleNumber(row, colm - 1) + 2;
> if (row%2 == 1 && colm%2 == 1)
> return FindRectangleNumber(row - 1, colm-1) + 1;
>
> }
>
> This function can be used to solve the given problem.
>
> On Sun, Aug 22, 2010 at 3:29 PM, Saikat Debnath <[email protected]>wrote:
>
>
>
> > Can anyone help in finding number of rectangles having a given
> > recatngle number. A rectangle number is defined as the number of unit
> > sided square formed inside the given rectangle having a common point
> > with a diagonal of rectangle. The sides of rectangle have integer
> > length. E.g. number of rectangle with rectangle number 4 is 4, i.e.
> > 1X4, 2X4, 2X3 and 4X4.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%[email protected]>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> Please access the attached hyperlink for an important electronic
> communications
> disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
