I have already done the first 2 parts(factorial and fibonacci) also finding the

ID: 3796889 • Letter: I

Question

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 " + "Fibonacci Sequence " + "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 + " " + fibonacci(n) + " " + 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 " + "Fibonacci Sequence " + "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 + " " + nfibonacci(n) + " " + 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 " + "    Factorial " + " 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 + " " + factorial(n) + " " + 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 " + " Factorial " + " 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 + " " + nfactorial(n) + " " + 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) + " Time Elapsed");
           long stopTime = System.nanoTime();
           long elapsedTime = stopTime - startTime;

           System.out.println( " " + n + " " + nfactorial(n) + " " + 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);

}

Explanation / Answer

return true;
}
}

Navigate

I have already done parts ONE and TWO, all I need is part THREE (iii). Please sh

I have already done this program, and it works just fine. However, I need to add

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

I have already done the first 2 parts(factorial and fibonacci) also finding the

Question

Explanation / Answer

Related Questions

Navigate