* - addInOrder
* - getFortune
* - remove
Answer:
We do not draw a big triangle. Instead, we call the method 3 times (with different vertices as argument) to draw 3 segments of the snowflake.
Answer:
At the bottom level of recursion, we know what to draw, so draw. For this program, we do not start drawing anything until we get to the bottom. What's the point of backing up the "call ladder"? So we can draw other small segments that make up for other parts of the snowflake. Even though the upper (non-bottom) levels of recursion do not draw anything, they actually calculate the positions and make calls to the lower level.
Answer:
Again, there is no "cutting out" any lines here. It's unlike the spiral (or the Sierpinski Gasket) where we performs a draw at each level. For this lab, we only draw at the bottom level (base case of recursion).
Answer:If you have more questions, post them here (be sure to put your name) or email me.
Up to you. I have 2 suggestions for you. Choose either one or come up with your own. There is no right or wrong.Both options would give sufficient information to the SnowflakeSegment on what to draw. Which one should you pick? ... whatever. You will need to calculate the points of subdivision from the arguments. It's a little work on geometry. Both options give you enough information for the calculation.
- SnowflakeSegment(Point p1, Point p2);
- SnowflakeSegment(Point p1, double length, double angle);
mergeInOrder(array A, array B)Note that at this first step, your pseudocode sounds like English (or another human language of your choice -- in my case, I sometimes write in Thai). And you may have no idea (yet) how to do Step 2 exactly. This is fine, we will gradually refine it.
- Make a new array C to be the output.
- Put contents of A and B onto C, maintaining order.
- Return C
mergeInOrder(array A, array B)This looks more like a code now. So let's put more details on how we keep track of "current elements" in A, B, and C. We probably need some index variables. Let's call them i, j, k.
- Make an array C of size A.length + B.length.
- Loop until A or B run out of values
- IF current element in A is less than current element in B
THEN put current element of A in C, proceed A and C
ELSE put current element of B in C, proceed B and C- If A run out first, put the rest of B in C
- If B run out first, put the rest of A in C
- Return C
mergeInOrder(array A, array B)And, we are pretty much done. This piece of pseudocode is very valuable, as we can directly translate it into (almost) any high-level languages: Java, C, Perl, python. It is much easier (and safer) to arrive at a code this way than by just writing a Java code on a blank screen (also known as "Debugging a Blank Screen").
- Make an array C of size A.length + B.length.
- Let the integers i = 0, j = 0, k = 0. /* they will be indices of A, B, C, respectively */
- WHILE i < A.length AND j < B.length DO THIS
- IF current A[i] < B[j]
THEN C[k] = A[i]; increment k, i;
ELSE C[k] = B[j]; increment k, j;
- /* If A run out first, put the rest of B in C */
- WHILE (j < B.length) DO THIS
- C[k] = B[j]; increment k, j;
- /* If B run out first, put the rest of A in C */
- WHILE (i < A.length) DO THIS
- C[k] = A[i]; increment k, i;
- Return C
/**
* Prints the step-by-step instruction on how to solve the Tower of Hanoi problem.
* Specifically, tells the user how to move n disks from tower i to tower j, using tower k as a temporary tower.
*
* Assumes i, j, k are all different.
*/
private void solveHanoi(int n, int i, int j, int k);
1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3
/**
* Prints the step-by-step instruction on how to solve the
* Tower of Hanoi problem.
*
* Specifically, tells the user how to move n disks from tower i to tower j,
* using tower k as a temporary tower.
*
* Assumes i, j, k are all different.
*/
private void solveHanoi(int n, int i, int j, int k) {
if (n <= 0) return;
if (n == 1) {
System.out.println(i + " -> " + j);
return;
}
/** we may now assume n > 1 */
solveHanoi(n-1, i, k, j);
solveHanoi(1, i, j, k);
solveHanoi(n-1, k, j, i);
}
/**
* Draws a Sierpinski Gasket whose 3 corners are p1, p2, p3. Stops when p1 and p2 are "too close" -- having distance less than 3.
* Assumes we have this global variable:
* Graphics2D g2;
* Everything should be drawn onto g2.
*/
private void drawSierpinski(Point p1, p2, p3);
private void drawSierpinski(Point p1, p2, p3);Then, we refine it:
- Compute distance between p1 and p2.
- If distance < 3, return;
- Draw a boring triangle (p1, p2, p3).
- Compute the midpoints p12, p23, and p13
- Make recursive calls.
private void drawSierpinski(Point p1, p2, p3);and that's pretty much the code! (except for the blah blah part :P)
- double d = squareRootOf( (p1.x-p2.x)^2 + (p1.y-p2.y)^2 );
- IF d < 3 THEN return;
- /* Draw a boring triangle (p1, p2, p3). */
- Draw line p1 - p2
- Draw line p1 - p3
- Draw line p2 - p3
- /* Compute the midpoints p12, p23, and p13 */
- /* Compute p12 */
- p12.x = (p1.x + p2.x) / 2.0;
- p12.y = (p1.y + p2.y) / 2.0;
- blah... (for p23)
- blah blah... (for p13)
- /* Make recursive calls. */
- drawSierpinski(p1, p12, p13);
- drawSierpinski(p2, p12, p23);
- drawSierpinski(p3, p13, p23);
| Problem | Comments |
| 2b | The answer is "EMPTY STRING". Please note that there is a difference between null and empty strings. |
| 2c | The answer is "STATIC". Normally, when we have a non-static method inside a class C, we have to call it by _variableName.methodName(); where _variableName is a variable of type C. We cannot simply call: C.methodName(); unless the method is static. |
| 5a | javax.swing.JApplet is extended to create an applet. JFrame is not the correct answer. JFrame is used to create a window for a java application. |
| 5g | The answer can be: blueprints, guides, stamps, models, cookiecutters. |
| 9c | An algorithm is a set of steps leading to a result. Pseudocode can help develop an algorithm because it focuses on the steps, not the language. An algorithm is NOT a process of refining pseudocode. An algorithm is a process of solving a problem. Pseudocode is used to describe an algorithm. |
| 9e | To write a loop, one must not forget to set an initial value to the counter. |
| 10c | Many of you wrote that in a sentinel-controlled repetition, the number of times the code is repeated depends on user's input. This is not wrong, but not entirely true. It could depend on a lot of other things: e.g. result of a calculation, random number, state of the machine, network data. |
• Midterm 3
– Monday 2/26/07
– Topics:
• Chapters 7 & 8
• How it works: bouncing ball program
• Timer, Mover, MoveTimer
• BorderLayout, FlowLayout, Button
• Let’s review the bouncing ball app
– BouncingBallApp
– BouncingBallPanel
– BouncingBall
– Mover
– MoveTimer
– SmartEllipse
• BouncingBallApp
– Wrapper of the BouncingBallPanel
– Doesn’t do much
• BouncingBallPanel
– implements Mover
• So there must be a move() method
– Objects contained:
• a BouncingBall
• a MoveTimer
– Important methods:
• paintComponent
• move -- has to call repaint()
• BouncingBall
– extends SmartEllipse
– Method move() – override or overload?
• Mover
– A simple interface
• Why do we need this?
• What if we don’t have this, can we still do the job? What do we need to modify?
– Specifies one method
– Can we make this into an abstract class?
• What could be a problem?
• MoveTimer
– extends javax.swing.Timer
– Concepts of inner class
• SmartEllipse
– Same thing you had before.
• Layouts
– BorderLayout, FlowLayout
/**
* Merge the sorted array a and b together, putting the elements in correct order
*
* @param a a non-null ascendingly sorted array
* @param b another non-null ascendingly sorted array
* @return
* a new array of size a.length + b.length containing elements from
* a[] and b[] in ascendingly sorted order.
*/
private int[] mergeInOrder(int[] a, int[] b) {
int la = a.length;
int lb = b.length;
int[] c = new int[la+lb];
int i = 0, j = 0, k = 0;
while ((i < la) && (j < lb)) {
if (a[i] < b[j]) {
// a wins!
c[k] = a[i];
i++;
k++;
} else {
// b wins!
c[k] = b[j];
j++;
k++;
}
}
return c;
}
product. The name was a bit misleading so I am renaming it to productExcept. We solved this problem together and came up with this nested-loop solution:
/**
* Computes a new array where the i-th element is the product of all elements in array a
* except a[i]. For example, if a = {1, 2, 3, 4} then
* productExcept(a) = {24, 12, 8, 6}
*
* @param a a non-null array of integers
* @return
* an array b of the same size as a where,
* with n being the size of a,
* b[i] = a[0]*...*a[i-1]*a[i+1]*...*a[n-1]
* for every i from 0 to n-1
*/
private int[] productExcept(int[] a) {
int la = a.length;
int[] b = new int[la];
for (int i = 0; i < la; i++) {
b[i] = 1;
// we will compute the value of b[i]
for (int j = 0; j < la; j++) {
if (j != i) {
b[i] = b[i] * a[j];
}
}
}
return b;
}
private int[] myArray;
private void printAll(int[] a) {
for (int x : a) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String[] args) {
myArray = new int[10];
a[0] = 10;
a[1] = 9;
a[2] = 8;
...
a[9] = 1;
printAll(myArray);
}
/** returns index k such that a[k] == x
* but if x is not in a, then returns -1
*/
private int findInArray(int[] a, int x);
/** returns the maximum value of the elements in a
*/
private int findMaxValue(int[] a);
/** returns the minimum value of the elements in a
*/
private int findMinValue(int[] a);
/** Returns a new array whose elements are a reversal of array a
* For example, if a = [1 2 3 4 5]
* then reverseArray(a) = [5 4 3 2 1]
* Array a should not be modified.
*/
private int[] reverseArray(int[] a);
/** Merge a and b together, put a first, then b
*/
private int[] mergeArrays(int[] a, int[] b)
/** Assume a and b are sorted in ascending order
* Returns the merged array in sorted order.
*/
private int[] mergeInOrder(int[] a, int[] b)
/** Returns array b such that
* b[i] = products of all elements in a except a[i]
*/
private int[] product(int[] a)
public static double random()
double greater than or equal to 0.0 and less than 1.0.
private int f(int x) {
if (x==0) return 1;
else return x * f(x-1);
}
private int a(int m, int n) {
if (m==0) return n+1;
if (n==0) return a(m-1, 1);
return a(m-1, a(m, n-1));
}
public static void main(String[] args) {
System.out.println(f(5));
System.out.println(a(3, 1));
}
