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