a question in a program written in c++

[1student]

hi,
sorry that I write it as a new topic, but it's urgent, and I must get help
Here (forums.anandtech.com/messageview.aspx?catid=33&threadid=1463864&enterthread=y) is the question. I'll write it again.

i'd a question - to write a program which gets a 2-dimension array (its size is some power of 2), in the array there are binary values: 0 or 1.
I had to write 2 function:
the first - counts the lit digits - the 1-cells
the second - gets an array and limits. it has to check if there are more than 1 lit digits, if so - it has to reduce the limits, till it gets limits that include just one lit digit - 1, and than prints out it limits.

example:

1) 0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0

=>> (0,0)(3,3)

2) 1 0 0 1
0 0 1 0
0 0 0 0
1 0 0 0

=>> (0,0)(1,1)
(3,0)(3,0)
(2,1)(2,1)
(0,2)(1,3)


etc..

It's hard to explain... hope u understood.

Here is the progam I wrote:

 

[1student]

the problem is... examples

when I enter numbers in the order below, I get:

Enter 4X4 pixels
1 1 0 0
0 1 0 0
1 0 0 1
1 1 1 1
square: (0,0),(0,0)
square: (0,1),(0,1)
square: (1,1),(1,1)
9

instead of getting:
square: (0,0),(0,0)
square: (0,1),(0,1)
square: (1,1),(1,1)
square: (0,2),(0,2)
square: (3,2),(3,2)
square: (0,3),(0,3)
square: (1,3),(1,3)
square: (2,3),(2,3)
square: (3,3),(3,3)
9

when I enter numbers in that order -
Enter 4X4 pixels
0 1 0 0
0 1 0 0
0 0 0 0
0 0 0 0
square: (0,1),(0,1)
square: (1,1),(1,1)
2
it's okay, but in that order:
Enter 4X4 pixels
0 1 0 0
1 0 0 0
0 0 0 0
0 0 0 0
square: (0,1),(0,1)
2
it isn't

Where is the problem?

 

[EagleKeeper]

Try to run a debugging mode.

That should clue you in where you are failing in your logic.

 

[njmodi]

Originally posted by: 1student
the problem is... examples

when I enter numbers in the order below, I get:

Enter 4X4 pixels
1 1 0 0
0 1 0 0
1 0 0 1
1 1 1 1
square: (0,0),(0,0)
square: (0,1),(0,1)
square: (1,1),(1,1)
9

instead of getting:
square: (0,0),(0,0)
square: (0,1),(0,1)
square: (1,1),(1,1)
square: (0,2),(0,2)
square: (3,2),(3,2)
square: (0,3),(0,3)
square: (1,3),(1,3)
square: (2,3),(2,3)
square: (3,3),(3,3)
9

Shouldn't you also get:
square: (1,1),(2,2) - that also only includes "1" lit square...
square: (1,2),(2,3) - that also only includes "1" lit square...

 

[1student]

Originally posted by: EagleKeeper
Try to run a debugging mode.

That should clue you in where you are failing in your logic.

I don't realy know how to do use it.

Originally posted by: njmodi
Shouldn't you also get:
square: (1,1),(2,2) - that also only includes "1" lit square...

u mean to the bold pixel and its area:
1 1 0 0
0 1 0 0
1 0 0 1
1 1 1 1

isn't it?

I'm not sure it is right, and i'll explain why:

normally the checking should be done in that order:

1) check if the array has more than 1 lit pixel.
if so-> print the natural linits, and the sum-1.

2) otherwise

divide the array (to 4 parts I think),
more or less like this:

1 1 | 0 0
0 1 | 0 0

1 0 | 0 1
1 1 | 1 1

and start checking each one of the "new arrays" from paragraph 1.

 

[njmodi]

What are the exact words of the assignment... I think you might be misunderstanding the goal here... I think the point is to use recursion (which is what your code does)... can you state the actual problem word-for-word from the textbook or handout....

 

[1student]

Originally posted by: njmodi
What are the exact words of the assignment... I think you might be misunderstanding the goal here... I think the point is to use recursion (which is what your code does)... can you state the actual problem word-for-word from the textbook or handout....

it's very long...:

It's possible to represent a screen as a 2-dimension array, in a size: nXn, which contains just the digits 0 & 1.
Each cell in the array represents a pixel int the screen. A cell which is equal to 1 - will represent a lit pixel, and the 0 will represent the opposite.
A square in the array will be defined with 4 variables, which contain the limits of it, they are the indexes of the the left extremity upper point, and the indexes of the right one,
ex:
the limits of the square which is represent by the points: (0,0),(n-1, n-1) =
left_top_x=0
left_top_y=0
right_bottom_x=n-1
left_bottom_y=n-1

You have to write a function which will get a 2dim array.... and wil return the sum of the setted on pixels in the array. (This function doesn't have to b recursuve)

A one pixel square is a square wich contains just 1 lit pixel.

we want to divide the screen to squares like this, and print the imiits of them.
We will use the next alghorithm:
when an array in size n*n is given with 4 other variables-which will define the limits of the tested square (at first the limits'll be the limits of the array itself).
The alghorithm will check the next cases:
a) if the array doesn't contain lit pixels at all (just 0's) the alghorithm will stop.
b) if the square is 1-pixel - the alghorithm'll print out the limits & stop.
c) otherwise - we wil devide the given array in a recurscion to 1-pixel squares in the next method:
we will devide the square to 4 different squares, which will b equal in their size, each one in the suze: (n/2) X (n/2), and we will activate on each one the recursive function, till the whole array is devided to 1-pixels squares, or setted-of squares.

This function should obtain an array and limits of the square.
It will print all the limits if the 1-pixel squares in the array according to the alghorithm that I described.
The array's size is some power of 2...

 

[njmodi]

Ok - I understand the problem statement... let me take a peek at the code again... I'll get back to you in a few.

 

[njmodi]

The way I read the problem - you have to keep recursing until you get to an individual array element that is set, rather than stopping when the "current" limits only contain one set pixel... still look at the code.

 

[1student]

Originally posted by: njmodi
The way I read the problem - you have to keep recursing until you get to an individual array element that is set, rather than stopping when the "current" limits only contain one set pixel... still look at the code.

I think I'll wait to your final opinion (I'm so confused from that question...)
lots of thanks!!! you just don't know how much u help me...

 

[njmodi]

Two main problems in the code:

1. You only need to keep recursing even if the total sum in the current "square" is 1 until you end up with a single array element, i.e.numBitsSettedOn() may return 1, but your square might include more than 1 pixel - so you need to keep recursing until you are at one square.

2. Your limit calulations need to be based on the difference of the endpoints, so lets use (x1,y1) - (x2,y2) to define the current limit. If the num. pixels set is > 1, then you need to divide that square into 4 equal squares... I would do that as follows:

Square 1: (x1,y1, (x1+ (x2-x1)/2), y1+ (y2-y1)/2)),

i.e. instead of your code: printsBitsSettedOn (x1, y1, x2/2, y2/2);
I would code that as: printsBitsSettedOn (x1, y1, (x1+ (x2-x1)/2), y1+ (y2-y1)/2));

I won't do all your work for you - just use similar logic to figure out the other 3 sub-squares and you should be all set...

Cheers.

 

[njmodi]

Did you get this working?

 

[1student]

Originally posted by: njmodi
I won't do all your work for you

For sure, I must learn it.

Originally posted by: njmodi
1. You only need to keep recursing even if the total sum in the current "square" is 1 until you end up with a single array element, i.e.numBitsSettedOn() may return 1, but your square might include more than 1 pixel - so you need to keep recursing until you are at one square.

sorry, but I don't think I understood it.

I'll take the ex. I wrote before to explain why not:
1 1 0 0
0 1 0 0
1 0 0 1
1 1 1 1
first of all, from the main, I arrive to the printsBitsSettedOn().
that function sends ths datas to numBitsSettedOn(), which count the 1's and tells me that sum=9
->(sum>1).

I enter to implement the statements in the if, and arrive to the printsBitsSettedOn (x1, y1, (x1+ (x2-x1)/2), y1+ (y2-y1)/2)). now I start all the story again: sends to check how much setted on pixels I have, 3 int the 1st case, than enter to the if statements etc.. till I arrive to sum=1 in the 1st pixel in that case, than I print the limits (0,0),(0,0), and return, to implement the other statements in if - check if it has lit pixel - it has, so I print its limits and return to imlemers the others...

when I finish with the first case, I turn to the next statement....
according to what u said in the first clause, maybe it has to be: printsBitsSettedOn (x1+(x2-x1+1)/2, y1+(y2-y1+1)/2),(x2,y2)) (<-is that right?)

etc...

till I arrive to the last array in the 4th case, than, when I arrive to return, I return to the main...

I didn't see the problem in it.
where do I have the mistake?

 

[njmodi]

Originally posted by: 1student

Originally posted by: njmodi
1. You only need to keep recursing even if the total sum in the current "square" is 1 until you end up with a single array element, i.e.numBitsSettedOn() may return 1, but your square might include more than 1 pixel - so you need to keep recursing until you are at one square.

sorry, but I don't think I understood it.

I'll take the ex. I wrote before to explain why not:
1 1 0 0
0 1 0 0
1 0 0 1
1 1 1 1

Think about this example:
1 1 0 1
0 0 0 0
0 0 0 0
0 0 0 0

When you get to the second block:
0 1
0 0
Your sum is going to be 1, but you are still covering 4 pixels - so what will your limits be in that case?
What I'm saying is that even if the sum is 1, you need to keep recursing until you are only covering one pixel in your limits... so your logic needs to be sum >1 OR limits > 1 pixel... then keep recursing.
You only want to stop recursing if (sum == 0) or (sum = 1 &amp;&amp; limits cover 1 pixel).

Originally posted by: 1student
first of all, from the main, I arrive to the printsBitsSettedOn().
that function sends ths datas to numBitsSettedOn(), which count the 1's and tells me that sum=9
->(sum>1).

I enter to implement the statements in the if, and arrive to the printsBitsSettedOn (x1, y1, (x1+ (x2-x1)/2), y1+ (y2-y1)/2)). now I start all the story again: sends to check how much setted on pixels I have, 3 int the 1st case, than enter to the if statements etc.. till I arrive to sum=1 in the 1st pixel in that case, than I print the limits (0,0),(0,0), and return, to implement the other statements in if - check if it has lit pixel - it has, so I print its limits and return to imlemers the others...

when I finish with the first case, I turn to the next statement....

Yes your understanding above is correct.

Originally posted by: 1student
according to what u said in the first clause, maybe it has to be: printsBitsSettedOn (x1+(x2-x1+1)/2, y1+(y2-y1+1)/2),(x2,y2)) (<-is that right?)

I think you want:
printsBitsSettedOn (x1+(x2-x1)/2)+1, (y1+(y2-y1)/2)+1,(x2,y2))
i.e. add the 1 after dividing by 2

Originally posted by: 1student


etc...

till I arrive to the last array in the 4th case, than, when I arrive to return, I return to the main...

I didn't see the problem in it.
where do I have the mistake?

See my comments regarding the recursion and the example I provided.

Use some debugging cout statements to make sure that your recursions are calculating the currect limits for each smaller portion of your array... you know ahead of time exactly how you expect that 4x4 array to be subdivided over and over - so you can use the couts to make sure that the correct limits are being calculated each time you recurse.

 

[1student]

First, lots of thanks for your pation!!!

Originally posted by: njmodi
Think about this example:
1 1 0 1
0 0 0 0
0 0 0 0
0 0 0 0

When you get to the second block:
0 1
0 0
Your sum is going to be 1, but you are still covering 4 pixels - so what will your limits be in that case?
What I'm saying is that even if the sum is 1, you need to keep recursing until you are only covering one pixel in your limits... so your logic needs to be sum >1 OR limits > 1 pixel... then keep recursing.
You only want to stop recursing if (sum == 0) or (sum = 1 &amp;&amp; limits cover 1 pixel).

I think it's my fault... that I didn't give enough examples.
One of the examples is a similar case to that second block, in that case, I don't have to go through the statements in if, it's enough that I print the limits and say that I have 1 lit pixel.
I can have a block with more then one pixel (usually 2,4, 16,...), that just if in it there's 1 lit pixel and the others are 0's, or just 0's ( -> in that case-the limits will not be printed).

Originally posted by: njmodi

Originally posted by: 1student
first of all, from the main, I arrive to the printsBitsSettedOn().
that function sends ths datas to numBitsSettedOn(), which count the 1's and tells me that sum=9
->(sum>1).

I enter to implement the statements in the if, and arrive to the printsBitsSettedOn (x1, y1, (x1+ (x2-x1)/2), y1+ (y2-y1)/2)). now I start all the story again: sends to check how much setted on pixels I have, 3 int the 1st case, than enter to the if statements etc.. till I arrive to sum=1 in the 1st pixel in that case, than I print the limits (0,0),(0,0), and return, to implement the other statements in if - check if it has lit pixel - it has, so I print its limits and return to imlemers the others...

when I finish with the first case, I turn to the next statement....

Yes your understanding above is correct.

and it is done like this in the program?

Originally posted by: njmodi
See my comments regarding the recursion and the example I provided.

Use some debugging cout statements to make sure that your recursions are calculating the currect limits for each smaller portion of your array... you know ahead of time exactly how you expect that 4x4 array to be subdivided over and over - so you can use the couts to make sure that the correct limits are being calculated each time you recurse.

I'll do that and write here the program, after I finish.
I just wanna see what u say about what I wrote.

 

[njmodi]

Originally posted by: 1student
First, lots of thanks for your pation!!!

I think it's my fault... that I didn't give enough examples.
One of the examples is a similar case to that second block, in that case, I don't have to go through the statements in if, it's enough that I print the limits and say that I have 1 lit pixel.
I can have a block with more then one pixel (usually 2,4, 16,...), that just if in it there's 1 lit pixel and the others are 0's, or just 0's ( -> in that case-the limits will not be printed).

I thought the initial problem statement said you have to find each pixel that is lit, not the range of pixels in which only one is list... your program does the latter of those two things. As long as thats how the problem statement is supposed to be interpreted, then its fine.

Originally posted by: njmodi

Originally posted by: 1student
first of all, from the main, I arrive to the printsBitsSettedOn().
that function sends ths datas to numBitsSettedOn(), which count the 1's and tells me that sum=9
->(sum>1).

I enter to implement the statements in the if, and arrive to the printsBitsSettedOn (x1, y1, (x1+ (x2-x1)/2), y1+ (y2-y1)/2)). now I start all the story again: sends to check how much setted on pixels I have, 3 int the 1st case, than enter to the if statements etc.. till I arrive to sum=1 in the 1st pixel in that case, than I print the limits (0,0),(0,0), and return, to implement the other statements in if - check if it has lit pixel - it has, so I print its limits and return to imlemers the others...

when I finish with the first case, I turn to the next statement....

Yes your understanding above is correct.

Originally posted by: 1student
and it is done like this in the program?

Yes - your program does behave that way - just the calculations of the limits is incorrect.

 

[1student]

I think it worksssss!!

In fact, it doesn't seem perfect... it's not so good

see it:

 

[1student]

and here is what I get when I run the program:

Enter 4X4 pixels
1 1 0 0
0 1 0 0
1 0 0 1
1 1 1 1
square: (0,0),(0,0)
square: (1,0),(1,1)
square: (0,1),(0,1)
square: (1,1),(1,2)
square: (1,1),(1,1)
square: (2,0),(2,1)
square: (3,0),(3,0)
square: (3,2),(3,2)
square: (0,2),(2,3)
square: (3,2),(3,2)
square: (3,3),(3,3)
9

 

[njmodi]

You are very close... the middle two limit equations are incorrect:

printsBitsSettedOn (x1+(x2-x1)/2+1, y1, x2, y1+(y2-y1)/2+1 should be
printsBitsSettedOn (x1+(x2-x1)/2+1, y1, x2, y1+(y2-y1)/2 (no +1 in the second Y limit).

&amp;
printsBitsSettedOn (x1, y1+(y2-y1)/2+1, (x2-x1)/2+1, y2); is missing an x1 term, i.e. should be
printsBitsSettedOn (x1, y1+(y2-y1)/2+1, x1+(x2-x1)/2, y2);

Fix that and run your code- it will work. Try the array below and see if you notice that something *might* not be right... depending on how you interpret the original problem... post back the results from your program on this array:
1 1 1 0
0 1 0 0
1 0 0 1
1 1 1 1

Cheers.

 

[1student]

Here is what I got:

Enter 4X4 pixels
1 1 1 0
0 1 0 0
1 0 0 1
1 1 1 1
square: (0,0),(0,0)
square: (0,1),(0,1)
square: (1,1),(1,1)
square: (2,0),(2,0)
square: (3,0),(3,0)
square: (3,1),(3,1)
square: (0,2),(1,3)
square: (3,2),(3,2)
square: (2,3),(2,3)
square: (3,3),(3,3)
10

It workssss. I can believe it.

njmodi,
I don't know how to thank you.
You helped me soooo much!!!! in a way that not just the problem is correct, but I also understand the problem.
Lots (!!!!) of thanks!!

 

[njmodi]

Are you sure it works.. I think its close... but look at the line in bold.. does that make sense?

I think that line should really say:
square: (0,2),(0,2)

I think the problem statement is keep going until the limits only cover 1 pixel.... from your post about the exact problem you are coding


b) if the square is 1-pixel - the alghorithm'll print out the limits &amp; stop.
c) otherwise - we wil devide the given array in a recurscion to 1-pixel squares in the next method:
we will devide the square to 4 different squares, which will b equal in their size, each one in the suze: (n/2) X (n/2), and we will activate on each one the recursive function, till the whole array is devided to 1-pixels squares, or setted-of squares.


b) says if the square is 1 pixel - in the case of the line in bold, you are actually covering 4 pixels - even though only one is lit...

do you understand what I'm saying?

Originally posted by: 1student
Here is what I got:

Enter 4X4 pixels
1 1 1 0
0 1 0 0
1 0 0 1
1 1 1 1
square: (0,0),(0,0)
square: (0,1),(0,1)
square: (1,1),(1,1)
square: (2,0),(2,0)
square: (3,0),(3,0)
square: (3,1),(3,1)
square: (0,2),(1,3)
square: (3,2),(3,2)
square: (2,3),(2,3)
square: (3,3),(3,3)
10

It workssss. I can believe it.

njmodi,
I don't know how to thank you.
You helped me soooo much!!!! in a way that not just the problem is correct, but I also understand the problem.
Lots (!!!!) of thanks!!

You are welcome.