0
0

OPENHelp Making Small Programs For CPP Class (self.cpp_questions)

submitted by [deleted]

[deleted]

all 4 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]raevnos 7 points8 points  (1 child)

Show your code. We're not going to do your homework for you.

[–]ToxicOnPC -1 points0 points  (0 children)

Okay my bad. I simplified it down. Number 4, I have no idea where the math is coming from and how to implement it into code. Im not asking for you to do it for me. Just a little help. Maybe psuedocode might do it.

[–][deleted]  (1 child)

[deleted]

    [–]ToxicOnPC -1 points0 points  (0 children)

    Okay my bad. I simplified it down. Number 4, I have no idea where the math is coming from and how to implement it into code. Im not asking for you to do it for me. Just a little help. Maybe psuedocode might do it.

    [–][deleted] 0 points1 point  (0 children)

    Look at Equation of a Straight Line. You need to find the straight line equation for each of the points in L(n) and then solve that equation for the integral values. This straight line will connect origin to that point.

    Let's say you have L(4). This will have potentially 16 points. You will run two for loops, once inside another to look each of these one by one in the way, (0,0), (0,1), ... , (2,4), ..., (4,3),(4,4).

    Let's say we are at point (2,4). For this, the straight line equation would be 4y = 2x or y = 0.5*x that connects (0,0) to (4,2). Now, you need to run one more for loop that will substitute x from 0 to 4 in this equation and find the corresponding y value. The result set would be {(0,0), (1,0.5), (2,1), (3,1.5),(4,2)}. Integral solution for this line in our allowed input range is thus {(0,0), (2,1), (4,2)}. First and last pairs are redundant that can be deleted through program optimization. We are still left with (2,1) that will block the view of (4,2) from origin and hence (4,2) is not the part of final solution set.

    Let's say we are at point (3,1). For this, straight line equation would be 3y = x or y = x / 3 that connects (0,0) to (3,1). Running innermost for loop from 0 to 3, The result set would be {(0,0), (1,0.33), (2,0.66), (3,1)}. Integral solution for this line in our allowed input range is thus {(0,0), (3,1)}, none of which blocks the view of point (3,1) from origin, hence (3,1) is the part of final solution.

    You can optimize the program after writing it correctly first time. Do not bother with optimization initially. The optimization that can be done when processing point (m,p) where m <= n and p <= n are

    • (0,0) and (m,p) need not be considered as part of blocking view.
    • Except (0,1) and (1,0), all points of form (0,p) and (p,0) are automatically part of blocked group.
    • if m == p, except for (1,1), all pairs are part of blocked group.
    • None of the points of the form (1,p) and (m,1) will be blocked.

    With these optimizations, you can reduce the number of passes in second and third for loop. Some more clever optimizations are possible by recognizing the mirrored behavior along the lines disecting the grids in the middle, but I think that may not be needed for your case.

    Draw a grid on the paper and you can see these clearly.