Last post for this semester, I've finally gotten to the point where I write up my problem. I have decided to tackle the diagonals problem given in class, where you are given a rectangle broken into n squares by m squares. If you were to draw a diagonal line from one corner of the rectangle to the opposite corner, can you predict how many squares the line passes through.
To begin with, we understand that our inputs are n and m, two positive integers. Our output should also be a positive integer s, the number of squares. Knowing this, my plan was to search for patterns in the output using simple inputs.
As discussed in class, n = m + 1 is a good starting place, so
| rectangle dimensions | number of squares |
----------------------------------------------------
| 1 x 2 | 2 |
| 2 x 3 | 4 |
| 3 x 4 | 6 |
| 4 x 5 | 8 |
This is enough data to conclude that if the input is of the form n = m + 1, the output is s = n + m - 1
Another set of interesting data is when n and m are both even
| rectangle dimensions | number of squares |
----------------------------------------------------
| 2 x 2 | 2 |
| 2 x 4 | 4 |
| 2 x 6 | 6 |
| 4 x 4 | 4 |
| 4 x 6 | 8 |
Using this data, it seems slightly scattered. However, after some further consideration, another pattern emerges. If you divide both n and m by two until one or both are an odd number, the output of the smaller inputs can be multiplied by 2 to the exponent of the number of times the original inputs were halved:
| rectangle dimensions | number of squares |
----------------------------------------------------
| 4 x 4 | 4 |
| 2 x 2 | 2 | <-- 2 * 2 ^ 1 = 4
| 1 x 1 | 1 | <-- 2 * 2 ^ 2 = 4
This is unfortunately as far as my solution has gotten so far, but after my exams are over I will spend more time working on the derivation of a formula from this information.
Since this is my last post, good luck to everyone writing finals, and I hope you enjoyed this course, I found it quite interesting myself.
No comments:
Post a Comment