Observation is very important here. Examples can make us more clear
about the issue.
For a given RN, we do count in two situations refered before
separately.
1. In the first situation the qualifying rectangles will have their
width w and height h being coprime. Thus the equation RN = h + w - 1
will be true here. And we need to find all the numerical combinations
of h and w, where h<=w, which accord with the above equation. We
denote the number of all the combinations as C0.
2. In the second situation, RN = (h' + w' - 1) * gcd, where h' and w'
are coprime. First, we find all the possible gcds which can divide RN,
including RN itself. We denote these gcds as an array gcd1, gcd2 ...
gcdk. For each i belonging to {1,2..k}, we count the number of
possible combinations of h' and w' which accords to the equation h' +
w' - 1 = RN / gcdi. We denote this number as Ci. Finally, we count up
C0, C1 ... Ck. Then we get the final answer C = C0 + C1 + ... + Ck.
On Aug 24, 5:43 am, Saikat Debnath <saikat....@gmail.com> wrote:
> Thank you Adam, but the thing is I don't only want the solution but
> also, how to go about such questions? How do you came to a solution to
> this question?
>
> On Aug 24, 8:43 am, Adam <wangyanadam1...@gmail.com> wrote:
>
>
>
> > Write here again:
> > 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 we finally get the result RN = (h' + w' - 1) x gcd.
>
> > This computation method will obviously help you find all the
> > rectangles with a given pair of height and width. It's pretty much
> > like a reverse problem.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
