Source code

001package algs11;
002
003import java.util.Arrays;
004import stdlib.*;
005
006/**
007 * This is a skeleton file for your homework. Edit the sections marked TODO. You
008 * may add new functions. You may also edit the function "main" to test your
009 * code.
010 *
011 * You must not add static variables. You MAY add static functions, just not
012 * static variables.
013 *
014 * It is okay to add functions, such as
015 *
016 * <pre>
017 *     public static double sumHelper (double[] list, int i, double sumSoFar) {
018 * </pre>
019 *
020 * but it is NOT okay to add static variables, such as
021 *
022 * <pre>
023 * public static int x;
024 * </pre>
025 *
026 * As for homework 1, you must not change the declaration of any method.
027 * 
028 * You can edit the main function all you want. I will not run your main
029 * function when grading.
030 */
031public class MySecondHomework {
032
033        /**
034         * As a model, here is a minValue function, both iteratively and recursively
035         */
036        /** iterative version */
037        public static double minValueI (double[] list) {
038                double result = list[0];
039                int i = 1;
040                while (i < list.length) {
041                        if (list[i] < result) result = list[i];
042                        i = i + 1;
043                }
044                return result;
045        }
046
047        /** recursive version */
048        public static double minValue (double[] list) {
049                return minValueHelper (list, 1, list[0]);
050        }
051        private static double minValueHelper (double[] list, int i, double result) {
052                if (i < list.length) {
053                        if (list[i] < result) result = list[i];
054                        result = minValueHelper (list, i + 1, result);
055                }
056                return result;
057        }
058
059        /**
060         * PROBLEM 1: Translate the following sum function from iterative to
061         * recursive.
062         *
063         * You should write a helper method. You may not use any "fields" to solve
064         * this problem (a field is a variable that is declared "outside" of the
065         * function declaration --- either before or after).
066         */
067        public static double sumI (double[] a) {
068                double result = 0.0;
069                int i = 0;
070                while (i < a.length) {
071                        result = result + a[i];
072                        i = i + 1;
073                }
074                return result;
075        }
076        public static double sum (double[] a) {
077                // TODO
078                return StdRandom.uniform ();
079        }
080
081        /**
082         * PROBLEM 2: Do the same translation for this in-place reverse function
083         *
084         * You should write a helper method. You may not use any "fields" to solve
085         * this problem (a field is a variable that is declared "outside" of the
086         * function declaration --- either before or after).
087         */
088        public static void reverseI (double[] a) {
089                int hi = a.length - 1;
090                int lo = 0;
091                while (lo < hi) {
092                        double loVal = a[lo];
093                        double hiVal = a[hi];
094                        a[hi] = loVal;
095                        a[lo] = hiVal;
096                        lo = lo + 1;
097                        hi = hi - 1;
098                }
099        }
100        public static void reverse (double[] a) {
101                // TODO
102        }
103
104        /**
105         * PROBLEM 3: The following function draws mickey mouse, if you call it like
106         * this from main:
107         *
108         * <pre>
109         * draw (.5, .5, .25);
110         * </pre>
111         *
112         * Change the code to draw mickey moose instead. Your solution should be
113         * recursive.
114         * 
115         * Before picture:
116         * http://fpl.cs.depaul.edu/jriely/ds1/images/MickeyMouse.png After picture:
117         * http://fpl.cs.depaul.edu/jriely/ds1/images/MickeyMoose.png
118         *
119         * You may not use any "fields" to solve this problem (a field is a variable
120         * that is declared "outside" of the function declaration --- either before
121         * or after).
122         */
123        public static void draw (double centerX, double centerY, double radius) {
124                // TODO 
125                if (radius < .0005) return;
126
127                StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
128                StdDraw.filledCircle (centerX, centerY, radius);
129                StdDraw.setPenColor (StdDraw.BLACK);
130                StdDraw.circle (centerX, centerY, radius);
131
132                double change = radius * 0.90;
133
134                StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
135                StdDraw.filledCircle (centerX + change, centerY + change, radius / 2);
136                StdDraw.setPenColor (StdDraw.BLACK);
137                StdDraw.circle (centerX + change, centerY + change, radius / 2);
138
139                StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
140                StdDraw.filledCircle (centerX - change, centerY + change, radius / 2);
141                StdDraw.setPenColor (StdDraw.BLACK);
142                StdDraw.circle (centerX - change, centerY + change, radius / 2);
143        }
144
145        /**
146         * PROBLEM 4: Run runTerribleLoop for one hour. You can stop the program
147         * using the red "stop" square in eclipse. Fill in the OUTPUT line below
148         * with the numbers you saw LAST --- edit the line, replacing the two ...
149         * with what you saw:
150         *
151         * OUTPUT: terribleFibonacci(...)=... // TODO
152         *
153         * Comment: the code uses "long" variables, which are like "int", but
154         * bigger. It's because fibonacci numbers get really big really fast.
155         */
156        public static void runTerribleLoop () {
157                for (int N = 0; N < 100; N++)
158                        StdOut.format ("terribleFibonacci(%2d)=%d\n", N, terribleFibonacci (N));
159        }
160        public static long terribleFibonacci (int n) {
161                if (n <= 1) return n;
162                return terribleFibonacci (n - 1) + terribleFibonacci (n - 2);
163        }
164
165        /**
166         * PROBLEM 5: The implementation of terribleFibonacci is TERRIBLE! Write a
167         * more efficient version of fibonacci. Do not change runFibonacciLoop or
168         * runFibonacciSomeValues.
169         *
170         * To make fibonacci run faster, you want it so that each call to
171         * fibonacci(n) computes the fibonacci numbers between 0 and n once, not
172         * over and over again.
173         *
174         * Comment: You will want to use a local variable of type "long" rather than
175         * type "int", for the reasons discussed above.
176         *
177         * Comment: At some point, your fibonacci numbers might become negative.
178         * This is normal and expected.
179         * http://en.wikipedia.org/wiki/Integer_overflow We discuss this at length
180         * in our systems classes.
181         *
182         * You may not use any "fields" to solve this problem (a field is a variable
183         * that is declared "outside" of the function declaration --- either before
184         * or after).
185         * 
186         * You may use a loop on this problem.
187         * You do not need to use recursion.
188         */
189        public static void runFibonacciLoop () {
190                for (int N = 0; N < 100; N++)
191                        StdOut.format ("fibonacci(%2d)=%d\n", N, fibonacci (N));
192        }
193        public static long fibonacci (int n) {
194                return 0; // TODO
195        }
196
197        /*
198         * A main function for debugging -- change the name to "main" to run it (and
199         * rename the existing main method to something else). Change the test as
200         * appropriate.
201         */
202        public static void main1 (String[] args) {
203                Trace.drawStepsOfMethod ("minValueI");
204                Trace.drawStepsOfMethod ("minValue");
205                Trace.drawStepsOfMethod ("minValueHelper");
206                Trace.run ();
207                testMinValue ("11 21 9 31 41");
208        }
209        
210        /**
211         * A test program, using private helper functions.  See below.
212         * To make typing tests a little easier, I've written a function to convert strings to arrays.  See below.
213         * You can modify this -- it is not graded.
214         */
215        public static void main (String[] args) {
216                testSum ("11 21 81 -41 51 61");
217                testSum ("11 21 81 -41 51");
218                testSum ("11 21 81 -41");
219                testSum ("11 21 81");
220                testSum ("11 21");
221                testSum ("11");
222                testSum ("");
223
224                testReverse ("11 21 81 -41 51 61");
225                testReverse ("11 21 81 -41 51");
226                testReverse ("11 21 81 -41");
227                testReverse ("11 21 81");
228                testReverse ("11 21");
229                testReverse ("11");
230                testReverse ("");
231
232                testFibonacci (0, 0);
233                testFibonacci (1, 1);
234                testFibonacci (1, 2);
235                testFibonacci (2, 3);
236                testFibonacci (21, 8);
237                testFibonacci (233, 13);
238                testFibonacci (75025, 25);
239                testFibonacci (             1_836_311_903L, 46);
240                testFibonacci (             2_971_215_073L, 47);
241                testFibonacci (       308_061_521_170_129L, 71); 
242                testFibonacci (       498_454_011_879_264L, 72);
243                testFibonacci ( 7_540_113_804_746_346_429L, 92);
244                //              9_223_372_036_854_775_807L == Long.MAX_VALUE
245                testFibonacci (-6_246_583_658_587_674_878L, 93);
246                testFibonacci (  -813_251_414_217_914_645L, 376);
247                StdOut.println ("Finished tests");
248
249                draw (.5, .5, .25);
250
251                // TODO: uncomment these temporarily when you want to see the output of your Fibonacci functions
252                //runTerribleLoop ();   
253                //runFibonacciLoop();           
254        }
255
256        /* Test functions --- lot's of similar code! */
257        private static void testSum (String list) {
258                double[] aList = doublesFromString (list);
259                double expected = sumI (aList);
260                double actual = sum (aList);
261                if (! Arrays.equals (aList, doublesFromString (list))) {
262                        StdOut.format ("Failed sum([%s]): Array modified\n", list);
263                }
264                if (expected != actual) {
265                        StdOut.format ("Failed sum([%s]): Expecting (%.1f) Actual (%.1f)\n", list, expected, actual);
266                }
267        }
268        private static void testMinValue (String list) {
269                double[] aList = doublesFromString (list);
270                double expected = minValueI (aList);
271                double actual = minValue (aList);
272                if (! Arrays.equals (aList, doublesFromString (list))) {
273                        StdOut.format ("Failed minValue([%s]): Array modified\n", list);
274                }
275                if (expected != actual) {
276                        StdOut.format ("Failed minValue([%s]): Expecting (%.1f) Actual (%.1f)\n", list, expected, actual);
277                }
278        }
279        private static void testReverse (String list) {
280                double[] expected = doublesFromString (list);
281                reverseI (expected);
282                double[] actual = doublesFromString (list);
283                reverse (actual);
284                // != does not do what we want on arrays
285                if (! Arrays.equals (expected, actual)) {
286                        StdOut.format ("Failed reverse([%s]): Expecting (%s) Actual (%s)\n", list, Arrays.toString (expected), Arrays.toString (actual));
287                }
288        }
289        private static void testFibonacci (long expected, int n) {
290                long actual = fibonacci (n);
291                if (expected != actual) {
292                        StdOut.format ("Failed fibonacci(%d): Expecting (%d) Actual (%d)\n", n, expected, actual);
293                }
294        }
295
296        /* A utility function to create an array of doubles from a string. */
297        // The string should include a list of numbers, separated by single spaces.
298        private static double[] doublesFromString (String s) {
299                if ("".equals (s)) return new double [0]; // empty array is a special case
300                String[] nums = s.split (" ");
301                double[] result = new double[nums.length];
302                for (int i = nums.length-1; i >= 0; i--) {
303                        try { 
304                                result[i] = Double.parseDouble (nums[i]); 
305                        } catch (NumberFormatException e) { 
306                                throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
307                        }
308                }
309                return result;
310        }
311}