import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; /* * Lessons: * Whenever solving a smaller instance of the problem can help * you solve your instance, recursion is a possibility (onlyLetters, * isPalindrome) * Practice at developing recurrences for counting problems (pentagonPark * log2, parade2, Spock variant) * Divide-and-conquer (printBackward, guess) * Preconditions/postconditions * Testing and debugging a recursive method by working from smaller to * larger instances (use the provided menu) * Getting a start at recognizing when a log comes up in the number of * steps of a recursive algorithm (log2) * * No calls to methods written by other people that implement pieces * of the algorithms we want you to express. * * You can't use loops anywhere in the program. */ public class Assign2Sol { // item 1 // precondition: none // postcondition: Has returned the result of purging // S of characters that are false for Character.isletter(char) public static String onlyLetters(String S) { // insight: The result consists of removing the last character, // removing non-letters from the resulting smaller string, // then appending the last character if it is a letter // YOU MUST USE THIS RECURSIVE STRATEGY. if (S.length() == 0) return S; else { char a = S.charAt(S.length()-1); String T = onlyLetters(S.substring(0,S.length() - 1)); if (Character.isLetter(a)) return T + a; else return T; } } // item 2 // precondition: none // postcondition: has returned true if S is a palindrome // and false otherwise. public static boolean isPalindrome(String S){ // insight: A string of length >= 2 is a palindrome if and only // if its first and last letter match, and the string that results // when these two letters are removed is also a palindrome // YOU MUST USE A RECURSIVE STRATEGY BASED ON THIS OBSERVATION. if (S.length()<=1) return true; else if (S.charAt(0)==S.charAt(S.length()-1)) return isPalindrome(S.substring(1,S.length()-1)); else return false; } // item 3 // precondition: n >= 1; // postcondition: The floor of the log base 2 of n has been returned public static int log2 (int n) { // insight: log2(n) is the number of times you can divide by 2, // using integer arithmetic, before you get to 1. Therefore, // if n is at least 2, it's one greater than log2(n/2) // YOU MUST USE A RECURSIVE STRATEGY BASED ON THIS OBSERVATION. if (n == 1) return 0; else return 1 + log2(n/2); } // item 4 // precondition: i <= j // postcondition: The sequence i i+1 i+2 ... j has been printed // out on one line, with each integer followed by a space character public static void printBackward(int i, int j) { // insight: if n = j-i+1 >= 2, you can print it backward by printing the // second half backward and then printing the first half backward. // The two subproblems should be from i through mid, and mid // through j, where mid = (i+j)/2 (integer arithmetic). if (i == j) System.out.print (i + " "); else { int mid = (i+j)/2; printBackward (mid+1, j); printBackward (i,mid); } } // item 5 // precondition: i <= j // postcondition: The sum i^2 + (i+1)^2 + (i+2)^2 + ... + j^2 // has been returned public static int sumSquares(int i, int j) { // insight: If n = j-i+1 >= 2, the sum of squares is the sum of squares // of the first half plus the sum of squares of the second // half // YOU MUST USE A RECURSIVE STRATEGY BASED ON THIS OBSERVATION. // Hint: Let mid = (i+j)/2. One call can be on i..mid and // the other on mid+1..j. if (i == j) return i*i; else { int mid = (i+j)/2; return sumSquares(i,mid) + sumSquares(mid+1,j); } } // item 6 public static long pentagonPark (int n) { // precondition: n >= 0 // postcondition: has returned the number of ways to park // Civics, Explorers, Tanks in a row of n parking spaces, where // a tank takes up three space, an Explorer 2, and a Civic one, // and no space can be left empty. Two vehicles of one type // are indistinguishable. // // You must make three recursive calls, one to count the // number of arrangements ending with a Civic, one to count // the number of arrangements ending with an Explorer, and one // to count the number of arrangements ending in with a tank. if (n == 0) return 1; else if (n == 1) return 1; else if (n == 2) return 2; else return pentagonPark(n-3) // A Tank in last position + pentagonPark(n-2) // An Explorer in last position + pentagonPark(n-1); // A Civic in last position } // item 7 // precondition: n >= 0 // postcondition: has returned the number of ways of assembing a parade // of floats and bands, where each band must be separated from the // previous band by two floats. The bands are indistinguishable, // and the floats are indistinguishable. // // You need two recursive calls, one to count the number of arrangements // ending with a float, and one to count the number of arrangements // ending with a band. public static int parade2(int n) { if (n == 0) return 1; else if (n == 1) return 2; else if (n == 2) return 3; else return parade2(n-1) // float in last position + parade2(n-3); // band in last position } // item 8 public static int guess(int i, int j, Scanner Input) { // precondition: i <= j and a number you are thinking of is in the // range [i,i+1, ..., j]. // Input should be initialized to a Scanner object. // inputs: Each of your answers should be a single character, 'y' or 'n', // followed by a newline. // postcondition: The number you were thinking of, assuming you // answered truthfully, has been returned. // Insight: Let mid = (i+j)/2 (integer arithmetic). Ask if // their number is greater than mid. If it is, then you know // that their number is between mid+1 and j. Finding it is a smaller // instance of the problem. If it isn't, then you know // that their number is between i and mid. Finding it in this // case is also a smaller instance of the problem. if (i == j) return i; else { int mid = (i+j)/2; System.out.println("Is your number greater than " + mid + "? "); String Response = Input.next(); System.out.println(Response); if (Response.charAt(0) == 'y') return guess(mid+1, j, Input); else return guess(i, mid, Input); } } // item 9 (provided) // precondition: 0 <= i <= n // postcondition: Has returned the number of ways of selecting k elements // from a set of size n, where the order doesn't matter. public static int C(int n, int i) { if (i == 0 || i == n) return 1; else return C(n-1,i) + C(n-1,i-1); } // item 10 // precondition: 0 <= i, 0 <= j, and 0 <= i+j <= n // postcondition: Has returned the number of ways of selecting // a set A of size i from a set of size n, and then selecting // a set B of size j from the remaining elements. // The strategy must be the following generalization of the // one for solving Spock's dilemma. If either i or j is 0, or i+j is n, // the answer can be computed with C(int, int), above. // (Why?) Otherwise, focus on a particular element x. // Add up the number of solutions that include x in A, the number that // include x in B, and the number that don't include x in either set. public static int M (int n, int i, int j) { if (i+j == n) return C(n,i); else if (i == 0) return C(n,j); else if (j == 0) return C(n,i); else return M(n-1,i,j) + M(n-1,i-1,j) + M(n-1,i,j-1); } //item 11 //precondition: 1 <= n //postconditon: n dots have been printed on one line without a newline // at the end. public static void dots(int n) { // Printing out n-1 dots is a smaller instance of the original // problem. If you can solve this problem, then all you need // to do is print another dot in order to meet your postcondition. if(n == 1) { System.out.print("."); } else { dots(n - 1); System.out.print("."); } } //item12 //precondition: 1 <= n //postconditon: hourglass of size n has been printed // An hourglass of size n consists of n dots on the first line, // n-1 doest on the next line, ..., 2 dots on the next line, // 1 dot on the next line, 2 dots on the next line, ..., // n-1 dots on the next line, n dots on the last line, followed // by a newline. // // Example, size 4: // .... // ... // .. // . // .. // ... // .... // // Strategy: An hourglass of size n consists of a first line of n dots, // then an hourglass of size n-1 (a smaller instance of your problem) // then a line of n dots, followed by a newline. public static void hourglass(int n) { if(n == 1) { dots(1); } else { dots(n); System.out.println(); hourglass(n - 1); System.out.println(); dots(n); } } // prints out the menu (provided) public static void printStrings(String[] Strings) { for (int i = 0; i < Strings.length; i++) System.out.println(Strings[i]); } public static void main(String[] args) { Scanner Input = new Scanner(System.in); String[] MenuChoices = { "0. Exit", "1. Remove non-letters from a String", "2. Test whether a string, with non-letters removed, is a palindrome", "3. log_2(n)", "4. Print integers from i to j, backward, using divide-and-conquer", "5. Sum squares of integers from i to j, using divide-and-conquer", "6. Pentagon Park", "7. Number of parades, where bands must be separated by two floats", "8. Guessing game, based on binary search", "9. Spock, one ship", "10. Spock, two ships", "11. Print n dots on a line", "12. Print hourglass-shaped pattern of dots", }; int choice = -1; // Records the option number the user selected // from the menu do { System.out.println("\n ---------------------------------------"); System.out.println(" MENU"); printStrings(MenuChoices); System.out.print("\n Which? "); choice = Input.nextInt(); System.out.println(choice); if (choice == 1) { if (Input.hasNextLine()) Input.nextLine(); System.out.println("Enter line of text that you want to purge of non-letters:"); String str = Input.nextLine(); System.out.println(onlyLetters(str)); } else if (choice == 2) { if (Input.hasNextLine()) Input.nextLine(); System.out.println("Enter line of text that you want test: "); String str = Input.nextLine(); str = onlyLetters(str); if (isPalindrome(str)) System.out.println("It's a palindrome."); else System.out.println("It's not a palindrome."); } else if (choice == 3) { System.out.println("Input n >= 1 whose log you want to know"); int n = Input.nextInt(); System.out.println("The log base 2 of "+n+" (rounded up) is " + log2(n)); } else if (choice == 4) { System.out.println("Enter i, j with i <= j: "); int i = Input.nextInt(); int j = Input.nextInt(); printBackward(i, j); System.out.println("\n\n"); } else if (choice == 5) { System.out.println("Enter i, j with i <= j: "); int i = Input.nextInt(); int j = Input.nextInt(); System.out.println("\n\nSum of squares from i to j: " + sumSquares(i,j)); } else if (choice == 6) { System.out.print("Enter number of parking spaces: "); int n = Input.nextInt(); System.out.println("There are " + n + " ways to park tanks, Explorers, civis in " + n + " spaces.\n"); } else if (choice == 7) { System.out.println("Enter length of parade: "); int n = Input.nextInt(); System.out.println("There are " + parade2(n) + " ways to organize the parade."); } else if (choice == 8) { System.out.println("Enter the guessing start and end range values: "); int i = Input.nextInt(); int j = Input.nextInt(); if (i <= j) { int guessedValue = guess(i,j, Input); System.out.println("****Your number is "+ guessedValue + "****"); } else System.out.println("The start value must be >= the end range."); } else if (choice == 9) { System.out.print("Enter number of planets, number you can visit: "); int n = Input.nextInt(); int k = Input.nextInt(); System.out.println("There are " + C(n,k) + " subsets of a set of size " + n + "\n\n"); } else if (choice == 10) { System.out.print("Enter number n of planets: "); int n = Input.nextInt(); System.out.print("Enter number i of planets that ship 1 can visit: "); int i = Input.nextInt(); System.out.print("Enter number j of planets that ship 2 can visit: "); int j = Input.nextInt(); System.out.println("\n\n"); if (i+j > n) System.out.println("i+j should be less than n"); else System.out.println("There are " + M(n,i,j) + " ways to choose the sets"); } else if(choice == 11) { System.out.print("Enter number of dots: "); int n = Input.nextInt(); dots(n); } else if(choice == 12) { System.out.print("Enter hourglass size (>= 1): "); int n = Input.nextInt(); hourglass(n); } } while (choice != 0); } }