import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; /* Corrected 1/31: the postcondition of printBackward implied that it * should print forward, not backward. The corrected postcondition appears * below. Sorry for any confusion - RM */ /* * 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. * * In each case, we describe how to solve your instance of the problem * by solving one or more smaller instances of the problem. The * smaller instances can be solved recursively. Your recursive * algorithm must use the strategy we suggest. * * You can't use loops anywhere in the program. */ public class Assign2 { // 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) { // 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. // Removing non-letters from the smaller string is a smaller // instance of your original problem. return ""; } // item 2 // precondition: none // postcondition: has returned true if S is a palindrome // and false otherwise. public static boolean isPalindrome(String S){ // 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. // Figuring out the latter point is a smaller instance of // your original problem. // // Refer to writeBackward in the reacings from Chapter 3 for // tips on manipulating Strings. 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) { // 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) // Finding log2(n/2) is a smaller instance of your original problem. return 0; } // item 4: CORRECTED: The postcondition I posted originally had // an error that implied the sequence should be printed forward - Ross M. // precondition: i <= j // postcondition: The sequence j j-1 j-2 ... i has been printed // out on one line, with each integer followed by a space character public static void printBackward(int i, int j) { // 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+1 // through j, where mid = (i+j)/2 (integer arithmetic). // Each of these is a smaller instance of your original problem. } // 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) { // 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. This breaks it into two smaller instances of your // original problem. return 0; } // item 6 // 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. public static long pentagonPark (int n) { // 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. return 0; } // 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. public static int parade2(int n) { // 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. return 0; } // 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. // 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. return 0; } // item 9 // 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. // // You can use the solution from the book; we won't grade this, but // you need it for the next problem. public static int C(int n, int i) { return 0; } // 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. // Count each of these with a recursive call. public static int M (int n, int i, int j) { return 0; } //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. } //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: // .... // ... // .. // . // .. // ... // .... // public static void hourglass(int n) { // 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. } // 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 down) 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 " + pentagonPark(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); } }