+/EE312
software design
git clone https://git.julia.blue/+/EE312
1c126f3
master
1/* 2* Project6.c 3* Recursion 4* Fall 2017 5* Joseph Ryan 6* jbr2558 7*/ 8 9 10#include <stdio.h> 11#include <stdint.h> 12#include <limits.h> 13#include <float.h> 14#include "MazeParams.h" 15#include "Recursion.h" 16 17#define MIN (X ,Y ) (X<Y?X:Y) 18 19/* return the smallest of the elements in array x[] 20* there are n elements in x[] (x[0].. x[n-1]) 21*/ 22int minIt (int x [],int n ) { 23int min = INT_MAX ; 24for (int i = 0 ;i < n ;++ i ) { 25min = MIN (x [i ],min ); 26 } 27return min ; 28} 29 30/* return the smallest of the elements in array x[] 31* there are n elements in x[] (x[0].. x[n-1]) 32* solve the problem recursively and 33* use an "n-1" type of decomposition 34*/ 35int minRec1 (int x [],int n ) { 36if (n == 0 ) { 37return x [0 ]; 38 } 39return MIN (x [n - 1 ],minRec1 (x ,n - 1 )); 40} 41 42/* 43* return the smallest of the elements in array x[] 44* there are n elements in x[] (x[0].. x[n-1]) 45* n may be either odd or even 46* solve the problem recursively and 47* use an "n / 2" type of decomposition 48*/ 49int minRec2 (int x [],int n ) { 50if (n <=1 ) { 51return x [0 ]; 52 } 53int half = n /2 ; 54int first = minRec2 (x ,half ); 55int last = minRec2 (x + half ,half + n %2 ); 56return MIN (first ,last ); 57} 58 59 60/* 61* calculate and return the square root of x. 62* The other two parameters are estimates of the square root. 63* low_guess is smaller than the actual square root, and high_guess 64* is larger than the actual square root. 65* Searching for the square root can be done much like searching 66* for a name in a phone book. 67* 68* Since you can't calculate a square root exactly, for this problem 69* you're required to calculate the answer to 15 decimal digits of 70* accuracy. 71*/ 72double sqrtIt (double x ,double low_guess ,double high_guess ) { 73double half = 1 ; 74while (high_guess - low_guess > 1e-15 ) { 75half = (low_guess + high_guess ) /2 ; 76if (half * half > x ) { 77high_guess = half ; 78 }else { 79low_guess = half ; 80 } 81 } 82return half ; 83} 84 85/* 86* calculate and return the square root of x. 87* The other two parameters are estimates of the square root. 88* low_guess is smaller than the actual square root, and high_guess 89* is larger than the actual square root. 90* Searching for the square root can be done much like searching 91* for a name in a phone book. 92* 93* Since you can't calculate a square root exactly, for this problem 94* you're required to calculate the answer to 15 decimal digits of 95* accuracy. 96*/ 97double sqrtRec (double x ,double low_guess ,double high_guess ) { 98if (high_guess < 0 ){ 99return 0 ; 100 } 101double half = (low_guess + high_guess ) /2 ; 102if (high_guess - low_guess > 1e-15 ) { 103if (half * half > x ) { 104high_guess = half ; 105 }else { 106low_guess = half ; 107 } 108return sqrtRec (x ,low_guess ,high_guess ); 109 } 110return half ; 111} 112 113 114/* 115* using only recursion, write a string comparison function 116* return -1 if str1 is less than str2 117* return 0 if the two strings are equal 118* return +1 if str1 is greater than str2 119* when comparing strings, use the ASCII value to compare each character 120* (i.e., that means 'A' is less than 'a' since it's ASCII value is smaller) 121* The string str1 is less than str2 if either 122* str1[0] < str2[0] 123* or there exists a k such that str1[k] < str2[k] and 124* for all j < k str1[j] == str2[j] 125* and k is less than the length of str1 and str2 126*/ 127 128int strCompare (char * str1 ,char * str2 ) { 129char a = str1 [0 ],b = str2 [0 ]; 130if (!a && !b ) { 131return 0 ; 132 } 133if (!b || a > b ) { 134return 1 ; 135 } 136if (!a || b > a ) { 137return -1 ; 138 } 139return strCompare (++ str1 ,++ str2 ); 140} 141 142/* 143* if c is not a letter return -1 144* if c is a letter, return the position of c in the alphabet 145* where 'A' (and 'a') are position 1 and 'Z' (and 'z') are position 26 146* 147* This code is rather ugly as I'm exploiting some detailed knowledge of the ASCII table 148*/ 149int whatLetter (char c ) { 150if (c < 'A' ) { 151return -1 ; 152 } 153if (c > 'z' ) { 154return -1 ; 155 } 156if (c > 'Z' && c < 'a' ) { 157return -1 ; 158 } 159return c & ~32 - 64 ; 160} 161 162/* 163* same as before, only this time 164* ignore anything that is not a letter 165* ignore the case (upper case, lower case) 166* So, strCompare2("Hello", "hello") should return 0 (they're the same) 167* strCompare2("The plane!", "theater") should return 1 since "theplane" is larger than "theater" 168* once again, you can only use recursion, no loops 169*/ 170int strCompare2 (char * str1 ,char * str2 ) { 171char a = whatLetter (* str1 ),b = whatLetter (* str2 ); 172if (!* str1 && !* str2 ) { 173return 0 ; 174 } 175if (a == -1 ) { 176return strCompare2 (++ str1 ,str2 ); 177 } 178if (b == -1 ) { 179return strCompare2 (str1 ,++ str2 ); 180 } 181if (a > b ) { 182return 1 ; 183 } 184if (b > a ) { 185return -1 ; 186 } 187return strCompare2 (++ str1 ,++ str2 ); 188} 189 190 191 192/* 193* the two dimensional array maze[MATRIX_SIZE][MATRIX_SIZE] contains a maze 194* Each square is (initially) either a 1 or a zero. Each 1 represents a wall 195* (you cannot walk through walls, so you can't go into any square where the 196* value is 1). Each 0 represents an open space. 197* 198* Write an recursive solution to find your way out of the maze 199* Your starting point is at row and col. (params to this function) 200* Your exit point is somewhere in the last row (which is: MATRIX_SIZE - 1) 201* 202* There is a relatively easy recursive solution to this problem, the trick is 203* to think of the solution in the following terms: 204* "In which direction(s) can I go and find a way out of this maze?" 205* In some cases, you may find yourself in a spot in the maze that there's 206* no way out (at least, not without backtracking). In that case, you'd return "false" 207* since the maze has no solution. In most cases, there's one or more ways out 208* from where you are now. Your key question is simply, "what is the first step I need to take" 209* 210* If you considered going "north", and you had a function that could tell you whether 211* it was possible to get out of the maze starting at the square to the north of your 212* current position, then you could use this function to determine if you can get out by 213* going north first. Similarly, you could consider going south, east or west, and (recursively) 214* determine if the maze can be solved from any of those locations. 215* 216* With that hint, the base case should be pretty obvious. In fact, 217* I'd suggest you consider the possibility that the base case is "Yup, I'm already at 218* the exit!" 219* 220* There is one tricky part to this decomposition. You need to make certain 221* that the problem is getting smaller. The "bigness" or "smallness" of this 222* problem is the number of squares that have not yet been tested. Each time 223* you test an adjacent square (making a recursive call to decide if there is a 224* path to the exit through that square), you'll be reducing the number of squares 225* that have not yet been tested. Eventually, you must have tested all the 226* squares and so you'll have to have found a way to the exit. 227* 228* The easy way to deal with the tricky part is to leave "bread crumbs" behind. 229* Before you recursively check any (or all) of your neighbors to see if you 230* can find the exit from there -- drop a bread crumb in your current square. 231* Then, don't ever check to see if you can find the exit using a square 232* with a breadcrumb in it (backtracking into that square would be silly). 233* 234* If you're trying to see if you can find an exit from some square, and all 235* the adjacent squares are either walls, or have bread crumbs in them, then 236* you already know the answer -- "you can't get to the exit from here". 237* Pick up your bread crumb and return false. 238* 239* You can set the value of the current square to "2" to indicate that a bread 240* crumb has been dropped. Set the square back to 0 when you want to pick 241* the bread crumb back up. 242* be sure not to change any of the squares that are 1 (the walls). 243* 244* for partial credit, you can leave all your bread crumbs on the floor. 245* for full credit, you must pick up all the bread crumbs EXCEPT those 246* along a path to the exit. 247*/ 248 249int solveMazeRec (int row ,int col ) { 250if (row >=MATRIX_SIZE || row < 0 || col >=MATRIX_SIZE || col < 0 ) { 251return 0 ; 252 } 253if (maze [row ][col ]) { 254return 0 ; 255 } 256maze [row ][col ]= 2 ; 257if (row == MATRIX_SIZE - 1 ) { 258return 1 ; 259 } 260if (solveMazeRec (row + 1 ,col )|| solveMazeRec (row ,col + 1 ) 261|| solveMazeRec (row - 1 ,col )|| solveMazeRec (row ,col - 1 )) { 262return 1 ; 263 } 264maze [row ][col ]= 0 ; 265return 0 ; 266} 267 268 269/********************** 270* adjacentCell and isOK are functions provided to help you write 271* solveMazeIt() 272*/ 273 274/* 275* OK, we're currently at maze[row][col] and we're considering moving 276* in direction dir. 277* Set trow and tcol (local variables inside the calling function) 278* to the row and column that we would move to IF we moved in 279* that direction 280* 281* For example, there are two good ways to use this function. 282* 1. to actually move one step in a direction use: 283* adjacentCell(row, col, dir, &row, &col); 284* That will set row and col to new values. The new values will 285* be one square away from the old values. 286* 287* 2. to set trow and tcol to a square that is adjacent to row and col use: 288* adjacentCell(row, col, dir, &trow, &tcol); 289* That will not change row and col, but will change trow and tcol. 290* This is useful if you aren't sure if you can actually move in this 291* direction yet (e.g., maze[trow][tcol] may be a wall!). So, you set 292* trow and tcol, and then check to see if it's OK to move there 293*/ 294void adjacentCell (int row ,int col ,int dir ,int * trow ,int * tcol ) { 295* trow = row ; 296* tcol = col ; 297switch (dir ) { 298case 0 :// UP 299* trow = * trow - 1 ; 300break ; 301case 1 :// RIGHT 302* tcol = * tcol + 1 ; 303break ; 304case 2 :// DOWN 305* trow = * trow + 1 ; 306break ; 307case 3 :// LEFT 308* tcol = * tcol - 1 ; 309break ; 310 } 311} 312 313 314/* 315* return false if there is a wall in the square for row and col 316* return true if it's not a wall. 317*/ 318int isOK (int row ,int col ) { 319return (row > 0 && row < MATRIX_SIZE 320&& col > 0 && col < MATRIX_SIZE 321&& maze [row ][col ]!= 1 ); 322} 323 324/* 325* return the value of the direction that is one turn to the right 326*/ 327int turnRight (int dir ) { 328return (dir + 1 ) %4 ; 329} 330 331/* 332* return the value of the direction that is one turn to the left 333*/ 334int turnLeft (int dir ) { 335return (dir + 3 ) %4 ; 336} 337 338/* 339* the two dimensional array maze[MATRIX_SIZE][MATRIX_SIZE] contains a maze 340* Each square is (initially) either a 1 or a zero. Each 1 represents a wall 341* (you cannot walk through walls, so you can't go into any square where the value 342* is 1). Each 0 represents an open space. 343* 344* write an iterative solution to find your way out of the maze 345* Your starting point is at row and col. (params to this function) 346* Your exit point is somewhere in the last row (which is: MATRIX_SIZE - 1) 347* The maze can be solved by following the right hand wall. In fact, there 348* is exactly one path between any two points in the maze (well, between any two 349* points that are not walls). 350* 351* The algorithm is not too bad, although it is certainly not trivial 352* Initially, you'll be headed DOWN (direction 2) 353* Each iteration do one of the following. Note that only one of two cases 354* can possibly apply (the properties of the maze guarantee that). 355* case 1: you can move in the current direction 356* In this case, you should take one step in the current direction 357* and then turn right. 358* case 2: you cannot move in the current direction 359* If there's a wall directly in front of you, then to follow the right 360* hand wall, you'd need to turn left (placing your hand on the wall that 361* used to be directly in front of you). So, if you discover this case 362* then turn left. Don't move, just turn left. 363* If you were walking down a straight corridor (with walls on both sides) 364* then you'd alternate case 1 and case 2. On the first iteration, you'd 365* take a step, and then turn right (case 1). This causes you to walk 366* one position down the hallway but then turn to face the wall. 367* On the next iteration, you'll be facing the wall, so you can't walk 368* forward and therefore (case 2) you'll turn left. On the third iteration 369* you'll be able to walk down the hallway again. 370* 371* If you follow those two cases, then you'll eventually find your way out 372* of the maze. To confirm that you're making it out, leave a "bread crumb" 373* behind each square along the path to the exit. 374* For partial credit, place a bread crumb in every square you visit. 375* For full credit, pick up all the breadcrumbs when you backtrack. 376* Backtracking is when you go back to a square you've already been before. 377* If the square you're about to step into has a breadcrumb, then pick up 378* the bread crumb in the square you're at now. 379* You indicate "bread crumbs" by setting the square equal to "2" 380*/ 381void solveMazeIt (int row ,int col ) { 382int dir = 2 ;// 0 is up, 1 is right, 2 is down, 3 is left. 383int trow ,tcol ; 384maze [row ][col ]= 2 ;// drop a bread crumb in the starting square 385while (row < MATRIX_SIZE - 1 ) { 386maze [row ][col ]= 2 ; 387adjacentCell (row ,col ,dir ,& trow ,& tcol ); 388if (isOK (trow ,tcol )) { 389if (maze [trow ][tcol ]== 2 ) { 390maze [row ][col ]= 0 ; 391 } 392adjacentCell (row ,col ,dir ,& row ,& col ); 393dir = turnRight (dir ); 394 }else { 395dir = turnLeft (dir ); 396 } 397 } 398} 399 400int countCoins (Martian m ) { 401return m .pennies + m .nicks + m .dodeks ; 402} 403 404Martian minMartian (Martian a ,Martian b ) { 405if (countCoins (a )> countCoins (b )) { 406return b ; 407 } 408return a ; 409} 410 411/* 412* using recursion, with no loops or globals, write a function that calculates the optimal 413* (fewest total coins) change for a given amount of money. Return a Martian struct that indicates 414* this optimal collection of coins. 415*/ 416Martian change (int cents ) { 417return change (cents ,5 ,12 ); 418} 419 420/* 421* Same as before, except the more general version where the coins have values 422* a cents and b cents, with a and b being algebraic. For the original problem, 423* a is the constant 5 (nick_value = 5 cents) and b is the constant 12 424* (dodek_value = 12 cents). 425* If you've really mastered thinking recursively, then this version of the 426* martian change problem is just as easy as the concrete version 427*/ 428Martian change (int cents ,int nick_val ,int dodek_val ) { 429if (!cents ) { 430struct Martian m ; 431m .pennies = 0 ; 432m .nicks = 0 ; 433m .dodeks = 0 ; 434return m ; 435 } 436struct Martian temp ; 437struct Martian m ; 438temp .dodeks = INT_MAX ; 439temp .nicks = INT_MAX ; 440temp .pennies = INT_MAX ; 441m .dodeks = INT_MAX ; 442m .nicks = INT_MAX ; 443m .pennies = INT_MAX ; 444if (cents >=dodek_val && dodek_val ) { 445m = change (cents - dodek_val ,nick_val ,dodek_val ); 446++ m .dodeks ; 447 } 448temp = minMartian (m ,temp ); 449if (cents >=nick_val && nick_val ) { 450m = change (cents - nick_val ,nick_val ,dodek_val ); 451++ m .nicks ; 452 } 453temp = minMartian (m ,temp ); 454if (cents >=1 ) { 455m = change (cents - 1 ,nick_val ,dodek_val ); 456++ m .pennies ; 457 } 458return minMartian (m ,temp ); 459} 460 461/* 462* without using recursion, solve the Martian change problem described above. 463* it's not too bad for the specific case of nick_value = 5 and dodek_value = 12 464*/ 465Martian changeIt (int cents ) { 466return changeIt (cents ,5 ,12 ); 467} 468 469int ternaryInc (int arr []) { 470int i = 0 ; 471while (arr [i ]== 2 ) { 472++ i ; 473 } 474int num = i ; 475++ arr [i ]; 476while (i > 0 ) { 477arr [-- i ]= 0 ; 478 } 479return num + 1 ; 480} 481 482/* 483* However, I don't have a solution for the general case. In fact, I consider 484* the general problem to "challenging" (i.e, an exercise in futility). 485* But, if you like banging your head against the wall for zero credit 486* this is the problem for you! 487*/ 488Martian changeIt (int cents ,int nick_value ,int dodek_value ) { 489int num = 1 ; 490int arr [10 ]; 491for (int i = 0 ;i < 10 ;++ i ) { 492arr [i ]= 0 ; 493 } 494while (cents ) { 495// for(int i = 0; i < num; ++i) { 496// printf("%d ", arr[i]); 497// } 498// printf("\n"); 499int temp = ternaryInc (arr ); 500num = temp > num ?temp :num ; 501int sum = 0 ; 502for (int j = 0 ;j < num ;++ j ) { 503if (arr [j ]== 0 ) { 504++ sum ; 505 }else if (arr [j ]== 1 ) { 506sum += nick_value ; 507 }else if (arr [j ]== 2 ) { 508sum += dodek_value ; 509 } 510 } 511 512if (sum == cents ) { 513break ; 514 } 515if (num == 9 ) { 516break ; 517 } 518 } 519Martian m ; 520m .pennies = 0 ; 521m .nicks = 0 ; 522m .dodeks = 0 ; 523for (int i = 0 ;i < num ;++ i ) { 524if (arr [i ]== 0 ) { 525++ m .pennies ; 526 } 527if (arr [i ]== 1 ) { 528++ m .nicks ; 529 } 530if (arr [i ]== 2 ) { 531++ m .dodeks ; 532 } 533 } 534return m ; 535}