I have already done the first 2 partsfactorial and fibonacci

I have already done the first 2 parts(factorial and fibonacci) also finding the time elapsed, need to do the last 2 parts (palindromes and binary search) also finding the time elapsed on each version (need to add code for that).

Assignments:

1) Write the recursive and nonrecursive version of

a. Int factorial(int n), (use nFactorial as the name for non-recursive version) (where n >= 0)

b. Int fibonacci(int n), (and nFibonacci as the name for non-recursive version)

c. boolean isPalindrome(String s, int low, int high), (and nIsPalindrome for the non-recursive version)

d. int binarySearch(int[] v, int key, int low, int high), (and nBinarySearch for the non recursive version)

2) Develop testing schemes as following:

a. For a and b: use at least 20 different values of n (from small to sufficiently large) and the time function to find the time spent for different values of n.

b. For c, set up a string array of size 20 and initialize them with at least 10 palindromes. (already made an array in the method)

c. For d, do the following: (need to make a new method for both versions and all the calls for both )

i. Fill an integer array of 1000 multiples of 3 from 0 to 2997 (i.e., 0, 3, 6, 9,…,2997) and have them properly sorted.

ii. Test your function and see if it works.

iii. Set up a test array with 20 random integers between 0 and 3000 to test the program.

Main method code:

public class factorials {

   public static void main (String args[])
   {
       System.out.println(\"Recursive Fibonacci Method: \ \");
       System.out.println(\" N\\t\\t\" + \"Fibonacci Sequence\\t\\t\" + \"Time Elapsed\");
       for(int n = 0; n < 25; n++)
       {
           long startTime = System.nanoTime();
           fibonacci(n);
           long stopTime = System.nanoTime();
           long elapsedTime = stopTime - startTime;

           System.out.println( \" \" + n + \"\\t\\t\\t \" + fibonacci(n) + \"\\t\\t\\t \" + elapsedTime);
           //System.out.println(/*\"Start Time: \" + startTime + \"\ Stop Time: \" + stopTime + */
                   //\"\ Elapsed Time: \" + elapsedTime);
       }

       System.out.println(\"\ \");

       System.out.println(\"Iterative Fibonacci Method: \ \");
       System.out.println(\" N\\t\\t\" + \"Fibonacci Sequence\\t\\t\" + \"Time Elapsed\");
       for ( int n = 0; n < 25; n++)
       {
           long startTime = System.nanoTime();


           nfactorial(n);
           long stopTime = System.nanoTime();
           long elapsedTime = stopTime - startTime;

           System.out.println( \" \" + n + \"\\t\\t\\t \" + nfibonacci(n) + \"\\t\\t\\t \" + elapsedTime);
           //System.out.println(/*\"Start Time: \" + startTime + \"\ Stop Time: \" + stopTime + */
               //   \"\ Elapsed Time: \" + elapsedTime);
       }

       System.out.println(\"\ \ \ \");

       System.out.println(\"Recursive Factorial Method: \ \");
       System.out.println(\" N\\t\\t\" + \"\\t   Factorial\\t\\t\" + \"\\tTime Elapsed\");
       for ( int n = 0; n < 25; n++)
       {
           long startTime = System.nanoTime();


           nfactorial(n);
           long stopTime = System.nanoTime();
           long elapsedTime = stopTime - startTime;

           System.out.println( \" \" + n + \"\\t\\t\\t \\t\" + factorial(n) + \"\\t\\t\\t\\t\\t\" + elapsedTime);
           //System.out.println(/*\"Start Time: \" + startTime + \"\ Stop Time: \" + stopTime + */
               //   \"\ Elapsed Time: \" + elapsedTime);
       }

       System.out.println(\"\ \");

       System.out.println(\"Iterative Factorial Method: \ \");
       System.out.println(\" N\\t\\t\" + \"\\tFactorial\\t\\t\" + \"\\tTime Elapsed\");
       for ( int n = 0; n < 25; n++)
       {
           long startTime = System.nanoTime();

           nfactorial(n);
           long stopTime = System.nanoTime();
           long elapsedTime = stopTime - startTime;

           System.out.println( \" \" + n + \"\\t\\t\\t \" + nfactorial(n) + \"\\t\\t\\t \" + elapsedTime);
           //System.out.println(/*\"Start Time: \" + startTime + \"\ Stop Time: \" + stopTime + */
               //   \"\ Elapsed Time: \" + elapsedTime);
       }

       System.out.println(\"\ \");

       //isPalindrome(null);

       for ( int n = 0; n < 19; n++)
       {
           long startTime = System.nanoTime();

           isPalindrome(array);
           System.out.println(\"Recursive Palindrome Method: \ \");
           System.out.println(\"Is \" + array[n] + \" Palindromic? \" + isPalindrome(array) + \"\\tTime Elapsed\");
           long stopTime = System.nanoTime();
           long elapsedTime = stopTime - startTime;

           System.out.println( \" \" + n + \"\\t\\t\\t \" + nfactorial(n) + \"\\t\\t\\t \" + elapsedTime);
           //System.out.println(/*\"Start Time: \" + startTime + \"\ Stop Time: \" + stopTime + */
               //   \"\ Elapsed Time: \" + elapsedTime);
       }
   }
   }



   static double factorial(int n)
{
double result;

if(n == 0 || n==1)
return 1;

result = factorial(n-1) * n;
return result;
}

   static double nfactorial(int n)
   {
       double result = 1;

       if(n==0 || n==1)
   return 1;

       for(int i = 1; i <= n ; i++)
       {
           result = result * i;
       }

       return result;
   }

   static int fibonacci(int n)
{
       if (n <= 1)
           return n;
       return fibonacci(n-1) + fibonacci(n-2);
}

   static int nfibonacci(int n)
   {
       if(n <= 1)
       {
       return n;
       }

       int result = 1;
       int fiboPrev = 1;
       for(int i = 2; i < n; ++i){
       int temp = result;
       result += fiboPrev;
       fiboPrev = temp;
       }
       return result;
       }

   static boolean isPalindrome(String s)
   {
       String[] array = {\"mom\", \"dad\", \"moon\", \"madam\", \"civic\", \"level\", \"wow\", \"rotor\", \"rotator\", \"stats\", \"racecar\",
               \"games\", \"cupcake\", \"math\", \"engineering\", \"science\", \"electricity\", \"recursion\", \"tacos\", \"gravity\"};

       int n = s.length();
       for (int i = 0; i < (n/2); ++i) {
       if (s.charAt(i) != s.charAt(n - i - 1)) {
       return false;
       }
       }

return true;
}
}

Example code for the palindrome and binary search (only for reference):

public class RecursivePalindrome {

public static boolean isPalindrome(String s) {

return isPalindrome(s, 0, s.length() - 1);

}

public static boolean isPalindrome(String s, int low, int high) {

if (high <= low) // Base case

return true;

else if (s.charAt(low) != s.charAt(high)) // Base case

return false;

else

return isPalindrome(s, low + 1, high - 1);

}

public static void main(String[] args) {

System.out.println(\"Is moon a palindrome? \" + isPalindrome(\"moon\"));

System.out.println(\"Is noon a palindrome? \" + isPalindrome(\"noon\"));

System.out.println(\"Is a a palindrome? \" + isPalindrome(\"a\"));

System.out.println(\"Is aba a palindrome? \" + isPalindrome(\"aba\"));

System.out.println(\"Is ab a palindrome? \" + isPalindrome(\"ab\"));

}

public class RecursiveBinarySearch {

public static int recursiveBinarySearch(int[] list, int key) {

int low = 0;

int high = list.length - 1;

return recursiveBinarySearch(list, key, low, high);

}

public static int recursiveBinarySearch(int[] list, int key, int low, int high) {

if (low > high) // The list has been exhausted without a match

return -low - 1;

int mid = (low + high) / 2;

if (key < list[mid])

return recursiveBinarySearch(list, key, low, mid - 1);

else if (key == list[mid])

return mid;

else

return recursiveBinarySearch(list, key, mid + 1, high);

}

return true;
}
}

I have already done the first 2 partsfactorial and fibonacci

Solution

Get Help Now

Submit a Take Down Notice