shilpi84
asked on
count squares of different dimensions in a matrix
I have a question. It isn't homework I just want to know the logic that must be applied in this program.
Suppose u r given a 4*3 rectangle like (take these values from user)
__________________________
| | | |
| | | |
|________|_________|______ __|
| | | |
| | | |
|________|_________|______ __|
| | | |
| | | |
|________|_________|______ __|
| | | |
| | | |
|________|_________|______ __|
Now calculate the no. of squares in this rectangle like:
No. of squares of dimension 1 is 12
No. of squares of dimension 2 is 6
No. of squares of dimension 3 is 2
No. of squares of dimension 4 is 0
Total no. of squares are 20.
So, can anyone please help me with the logic?
Thanks.
Suppose u r given a 4*3 rectangle like (take these values from user)
__________________________
| | | |
| | | |
|________|_________|______
| | | |
| | | |
|________|_________|______
| | | |
| | | |
|________|_________|______
| | | |
| | | |
|________|_________|______
Now calculate the no. of squares in this rectangle like:
No. of squares of dimension 1 is 12
No. of squares of dimension 2 is 6
No. of squares of dimension 3 is 2
No. of squares of dimension 4 is 0
Total no. of squares are 20.
So, can anyone please help me with the logic?
Thanks.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Well, the number of squres of the dimension 1*1 in a m*n-sized rectangle will always be m*n*...
A few typo corrections :
0 = (4 - 3) * (3 - 0)
should have been :
0 = (4 - 3) * (3 - 3)
And I should have shown :
12 = 3 * 4
as :
12 = (4 - 0) * (3 - 0)
0 = (4 - 3) * (3 - 0)
should have been :
0 = (4 - 3) * (3 - 3)
And I should have shown :
12 = 3 * 4
as :
12 = (4 - 0) * (3 - 0)
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Hi NovaDenizen,
I don't believe that it's that complicated. :)
Counting all possible squares of size S in a rectangle size MxN is the expression that I posted.
( Length(Rectangle) - Side(Square) + 1 ) * ( Width(Rectangle) - Side(Square) + 1 )
that is,
(M - S + 1) * ( N - S + 1)
Kent
I don't believe that it's that complicated. :)
Counting all possible squares of size S in a rectangle size MxN is the expression that I posted.
( Length(Rectangle) - Side(Square) + 1 ) * ( Width(Rectangle) - Side(Square) + 1 )
that is,
(M - S + 1) * ( N - S + 1)
Kent
If your expression is correct (and mine is too. :) ), then my expression is equivalent to the sum of (M-S+1)(N-S+1) for all S between 1 and min(N,M). My expressions solves for the whole sum, where yours is only for a particular square size.
A non-formulaic approach...
You first multiply width times height of the entire rectatngle (or height times width, it doesn't matter) (e.g. 4 x 3 = 12)
Then, reduce each number by 1 and multiply again (e.g. 3 x 2 = 6)
Reduce each number by 1 again, and multiply again (e.g. 2 x 1 =2).
Keep reducing and multiplying, until one of the numbers hits 0. Then, add all the products: in the example above, 12 + 6 + 2 = 20.
You first multiply width times height of the entire rectatngle (or height times width, it doesn't matter) (e.g. 4 x 3 = 12)
Then, reduce each number by 1 and multiply again (e.g. 3 x 2 = 6)
Reduce each number by 1 again, and multiply again (e.g. 2 x 1 =2).
Keep reducing and multiplying, until one of the numbers hits 0. Then, add all the products: in the example above, 12 + 6 + 2 = 20.
Take a look at the first post, Galisteo8 ...
Oops. Thanks, infinity. I'm late to the party. :)
Infinity has pretty well pegged it for you...
As the size of your "squares" increase, the size of the matrix you are "dealing with" effectively decreases...
If you were writing it as a program, a for loop to reduce the variables, and since the variables are not necessarily equal, an if to exit the for loop when either of the resulting reductions reachs zero...
In the meantime, multiply the variables and total the results.
As the size of your "squares" increase, the size of the matrix you are "dealing with" effectively decreases...
If you were writing it as a program, a for loop to reduce the variables, and since the variables are not necessarily equal, an if to exit the for loop when either of the resulting reductions reachs zero...
In the meantime, multiply the variables and total the results.
> No. of squares of dimension 2 is 6
Question is more like rectangles than squares, still that is incorrect. Taking
__________________________
| | | |
| | | |
|________|_________|______ __|
| | | |
| | | |
|________|_________|______ __|
| | | |
| | | |
|________|_________|______ __|
| | | |
| | | |
|________|_________|______ __|
I think you are missing these:
__________________________
| | | |
| | | |
|________|_________|______ __|
| | | |
| 2 | | 2 |
|________|_________|______ __|
| | | |
| 2 | | 2 |
|________|_________|______ __|
| | | |
| | | |
|________|_________|______ __|
etc
Question is more like rectangles than squares, still that is incorrect. Taking
__________________________
| | | |
| | | |
|________|_________|______
| | | |
| | | |
|________|_________|______
| | | |
| | | |
|________|_________|______
| | | |
| | | |
|________|_________|______
I think you are missing these:
__________________________
| | | |
| | | |
|________|_________|______
| | | |
| 2 | | 2 |
|________|_________|______
| | | |
| 2 | | 2 |
|________|_________|______
| | | |
| | | |
|________|_________|______
etc
Hi Sunbow,
6 is correct.
__________________________
| | | |
| A | B | C |
|________|_________|______
| | | |
| D | E | F |
|________|_________|______
| | | |
| G | H | I |
|________|_________|______
| | | |
| J | K | L |
|________|_________|______
2x2 squares can only be inserted (defined) such that their upper left small square is coincidental with A, B, D, E, G, and H.
Kent
Mybe it is design or image, and seeing what is rectangle or not while open to "these values from user"
I pretty much stopped review where AD is square, and imagine that you presume that. So I bow out Thanks This is then a math question, not puzzle.
I pretty much stopped review where AD is square, and imagine that you presume that. So I bow out Thanks This is then a math question, not puzzle.