Problem solving using recursion There are two skeleton programs, flesh them out following the suggestions given. Recursive algorithm for calculating xn (n ≥0): if n = 0, return 1.0 else return x * xn-1 (slow technique) Alternate (faster) algorithm: if n = 0, return 1.0 else if n is odd return x * xn-1 else { y = xn/2; return y * y;} (fast technique). Run program with several input values and compare results from fast power, slow power, and Math.pow in this table: Show all digits displayed by your program. You could add a loop to your program and paste the screen shot for all input values mentioned here instead. Show all digits. Base Exponent slow power fast power Math.pow 3.5 64 5 15 1.25 31 2 17
Problem solving using recursion
There are two skeleton programs, flesh them out following the suggestions given.
Recursive
Alternate (faster) algorithm: if n = 0, return 1.0 else if n is odd return x * xn-1 else { y = xn/2; return y * y;} (fast technique).
Run program with several input values and compare results from fast power, slow power, and Math.pow in this table:
Show all digits displayed by your program.
You could add a loop to your program and paste the screen shot for all input values mentioned here instead. Show all digits.
Base Exponent slow power fast power Math.pow
3.5 64
5 15
1.25 31
2 17
String matching
Finding needle in a haystack:
If needle is longer than the haystack then failure
else if needle matches the initial portion of haystack (use .startsWith() method) then success
else {
create a shorter haystack (haystack.substring(1))
return result from recursive call on the shorter haystack
}
You are allowed to use only the following methods from the Java String class: .length(), .startsWith(), .subString().
You are not allowed to use any other method from the String class. [The String class already has a find method. We are trying to implement that using simpler tools].
Fill results from power calculation in this page, copy paste source code and screen shots from the two finished programs in the following pages. Save the file with name yourUserid_ICA06.docx and submit through Isidore Assignment.
You could add a loop to your programs so you can show results from several inputs in one screen shot. Be sure to cover all possible situations for String Matching.
Submit this Word document filled in with source codes and screen shots in appropriate pages through Isidore assignments.
final static Scanner cin = new Scanner(System.in); /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here out.print("CPS 151 ICA 04 Power calculation by YOUR NAME\n\n"); out.print("Enter base (double): "); double base = cin.nextDouble(); out.print("Enter the power to raise it to (positive int): "); int expo = cin.nextInt(); double result1 = slowPower(base, expo); double result2 = fastPower(base, expo); out.println("Result from slow power = " + result1); out.println("Result from fast power = " + result2); out.println("Result from math.pow = " + Math.pow(base, expo)); } // end main private static double slowPower(double base, int expo) { if (expo == 0) return 1.0; else return 1.0; // stub, replace with correct recursion pattern } // end method private static double fastPower(double base, int expo) { if (expo == 0) return 1.0; else return 1.0; // stub, replace with correct recursion pattern } // end method
Second code:
// define a scanner attached to keyboard available to all functions final static Scanner cin = new Scanner(System.in); /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here out.print("CPS 151 ICA 04 String matching by YOUR NAME\n\n"); out.print("Enter the text (one word): "); String hayStack = cin.next(); out.print("Enter the pattern (one word): "); String needle = cin.next(); if (find(needle, hayStack)) out.println(needle + " was found in " + hayStack); else out.println(needle + " was not found in " + hayStack); } // end main private static boolean find(String needle, String hayStack) { int patLen = needle.length(); int textLen = hayStack.length(); // base case 1 if (patLen > textLen) { // failure } else if (needle.startsWith(needle)) { // base case 2 MODIFY!! // SUCCESS } else { // recurse } return false; // dummy to keep NetBeans happy } // end method
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 5 images
