import java.util.Arrays;

import stdlib.*;

/**

* This is a skeleton file for your homework. Edit the sections marked TODO. You

* may add new functions. You may also edit the function "main" to test your

* code.

*

* You must not add static variables. You MAY add static functions, just not

* static variables.

*

* It is okay to add functions, such as

*

*

 
 * public static double sumHelper (double[] list, int i, double sumSoFar) {
 
 * 

*

* but it is NOT okay to add static variables, such as

*

*

 
 * public static int x;
 
 * 

*

* As in homework 1,2 you must not change the declaration of any method.

*

* You can edit the main function all you want. I will not run your main

* function when grading.

*/

public class CSC300Program3 {

/**

* As a model, here is a minValue function, both iteratively and recursively

*/

/** iterative version */

public static double minValueI (double[] list) {

double result = list[0];

int i = 1;

while (i < list.length) {

if (list[i] < result) result = list[i];

i = i + 1;

}

return result;

}

/** recursive version */

public static double minValue (double[] list) {

return minValueHelper (list, 1, list[0]);

}

private static double minValueHelper (double[] list, int i, double result) {

if (i < list.length) {

if (list[i] < result) result = list[i];

result = minValueHelper (list, i + 1, result);

}

return result;

}

/**

* PROBLEM 1: Translate the following sum function from iterative to

* recursive.

*

* You should write a helper method. You may not use any "fields" to solve

* this problem (a field is a variable that is declared "outside" of the

* function declaration --- either before or after).

*/

public static double sumI (double[] a) {

double result = 0.0;

int i = 0;

while (i < a.length) {

result = result + a[i];

i = i + 1;

}

return result;

}

public static double sum (double[] a) {

return 0; // TODO

}

/**

* PROBLEM 2: Do the same recursive translation for this in-place reverse function

*

* You should write a helper method. You may not use any "fields" to solve

* this problem (a field is a variable that is declared "outside" of the

* function declaration --- either before or after).

*/

public static void reverseI (double[] a) {

int hi = a.length - 1;

int lo = 0;

while (lo < hi) {

double loVal = a[lo];

double hiVal = a[hi];

a[hi] = loVal;

a[lo] = hiVal;

lo = lo + 1;

hi = hi - 1;

}

}

public static void reverse (double[] a) {

// TODO

}

/**

* PROBLEM 3: The following function draws mickey mouse, if you call it like

* this from main:

*

*

 
 * draw (.5, .5, .25);
 
 * 

*

* Change the code to draw mickey moose instead. Your solution should be

* recursive.

*

* Before picture: http://fpl.cs.depaul.edu/jriely/ds1/images/MickeyMouse.png

* After picture: http://fpl.cs.depaul.edu/jriely/ds1/images/MickeyMoose.png

*

* You may not use any "fields" to solve this problem (a field is a variable

* that is declared "outside" of the function declaration --- either before

* or after).

*/

public static void draw (double centerX, double centerY, double radius) {

if (radius < .0005) return;

StdDraw.setPenColor (StdDraw.LIGHT_GRAY);

StdDraw.filledCircle (centerX, centerY, radius);

StdDraw.setPenColor (StdDraw.BLACK);

StdDraw.circle (centerX, centerY, radius);

double change = radius * 0.90;

StdDraw.setPenColor (StdDraw.LIGHT_GRAY);

StdDraw.filledCircle (centerX+change, centerY+change, radius/2);

StdDraw.setPenColor (StdDraw.BLACK);

StdDraw.circle (centerX+change, centerY+change, radius/2);

StdDraw.setPenColor (StdDraw.LIGHT_GRAY);

StdDraw.filledCircle (centerX-change, centerY+change, radius/2);

StdDraw.setPenColor (StdDraw.BLACK);

StdDraw.circle (centerX-change, centerY+change, radius/2);

}

/**

* PROBLEM 4: Run runTerribleLoop for one hour. You can stop the program using

* the red "stop" square in eclipse. Fill in the OUTPUT line below with the

* numbers you saw LAST --- edit the line, replacing the two ... with what

* you saw:

*

* OUTPUT: terribleFibonacci(...)=... // TODO

*

* Comment: the code uses "long" variables, which are like "int", but

* bigger. It's because fibonacci numbers get really big really fast.

*/

public static void runTerribleLoop () {

for (int N = 0; N < 100; N++)

StdOut.format ("terribleFibonacci(%2d)=%d ", N, terribleFibonacci (N));

}

public static void runTerribleSomeValues () {

StdOut.format ("terribleFibonacci(%2d)=%d ", 13, terribleFibonacci (13));

StdOut.format ("terribleFibonacci(%2d)=%d ", 7, terribleFibonacci (7));

StdOut.format ("terribleFibonacci(%2d)=%d ", 21, terribleFibonacci (21));

}

public static long terribleFibonacci (int n) {

if (n <= 1) return n;

return terribleFibonacci (n - 1) + terribleFibonacci (n - 2);

}

/**

* PROBLEM 5: The implementation of terribleFibonacci is TERRIBLE! Write a

* more efficient version of fibonacci. Do not change runFibonacciLoop or

* runFibonacciSomeValues.

*

* To make fibonacci run faster, you want it so that each call to

* fibonacci(n) computes the fibonacci numbers between 0 and n once, not

* over and over again.

*

* Comment: You will want to use a local variable of type "long" rather than

* type "int", for the reasons discussed above.

*

* Comment: At some point, your fibonacci numbers might become negative.

* This is normal and expected.

* http://en.wikipedia.org/wiki/Integer_overflow We discuss this at length

* in our systems classes.

*

* You may not use any "fields" to solve this problem (a field is a variable

* that is declared "outside" of the function declaration --- either before

* or after).

*/

public static void runFibonacciLoop () {

for (int N = 0; N < 100; N++)

StdOut.format ("fibonacci(%2d)=%d ", N, fibonacci (N));

}

public static void runFibonacciSomeValues () {

StdOut.format ("fibonacci(%2d)=%d ", 13, fibonacci (13));

StdOut.format ("fibonacci(%2d)=%d ", 7, fibonacci (7));

StdOut.format ("fibonacci(%2d)=%d ", 21, fibonacci (21));

}

public static long fibonacci (int n) {

return 0; // TODO

}

public static void main (String[] args) {

double[] list0 = new double[] {};

double[] list1 = new double[] { 5 };

double[] list2 = new double[] { -3, 5 };

double[] list3 = new double[] { 2, -3, 5 };

double[] list4 = new double[] { -1, 2, -3, 5 };

double[] list5 = new double[] { 0, -1, 2, -3, 5 };

testSum(0, list0);

testSum(5, list1);

testSum(2, list2);

testSum(4, list3);

testSum(3, list4);

testSum(3, list5);

testReverse(new double[] {}, list0);

testReverse(new double[] { 5 }, list1);

testReverse(new double[] { 5, -3 }, list2);

testReverse(new double[] { 5, -3, 2 }, list3);

testReverse(new double[] { 5, -3, 2, -1 }, list4);

testReverse(new double[] { 5, -3, 2, -1, 0 }, list5);

draw (.5, .5, .25);

runTerribleSomeValues ();

runTerribleLoop ();

runFibonacciSomeValues ();

runFibonacciLoop();

}

public static void testSum (double expected, double[] list) {

double actual = sum(list);

if (expected != actual)

{

StdOut.format ("Failed: Expecting [%1.1f] Actual [%1.1f] with argument %s ", expected, actual, Arrays.toString(list));

}

else

{

StdOut.println ("Correct sum: " + actual);

}

}

public static void testReverse (double[] expected, double[] list) {

reverse(list);

boolean failed = false;

if ( expected.length != list.length )

{

failed = true;

}

else

{

int len = list.length;

for ( int i = 0; i < len; i++ )

{

if ( expected[i] != list[i] )

{

failed = true;

}

}

}

if ( failed )

{

StdOut.format ("Failed: Expecting %s Actual %s ", Arrays.toString(expected), Arrays.toString(list));

}

else

{

StdOut.format ("Correct: reverse: %s ", Arrays.toString(list));

}

}

}