C++ PLEASE HELP!!! Please implement the recursive functions (except #3 and 7) wi

Question

C++ PLEASE HELP!!!

Please implement the recursive functions (except #3 and 7) with the function prototypes:

//Function prototypes

int binarySearch(const int anArray[], int first, int last, int target);

int fact(int n);

int iterativeRabbit(int n);

int rabbit(int n);

void writeArrayBackward(const char anArray2[], int first, int last);

void writeBackward(string s);

void writeBackwardIterative(string s);

int sumUpTo(int n);

int binarySearch(const int anArray[], int first, int last, int target)

   /** Searches the array anArray[first] through anArray[last]

for a given value by using a binary search.

@pre 0 <= first, last <= SIZE - 1, where SIZE is the

maximum size of the array, and anArray[first] <=

anArray[first + 1] <= ... <= anArray[last].

@post anArray is unchanged and either anArray[index] contains

the given value or index == -1.

@param anArray The array to search.

@param first The low index to start searching from.

@param last The high index to stop searching at.

@param target The search key.

@return Either index, such that anArray[index] == target, or -1.

*/

int fact(int n)

/** Computes the factorial of the nonnegative integer n.

@pre n must be greater than or equal to 0.

@post None.

@return The factorial of n; n is unchanged. */

int iterativeRabbit(int n)

/** Iterative solution to the rabbit problem. */

int rabbit(int n)

/** Computes a term in the Fibonacci sequence.

@pre n is a positive integer.

@post None.

@param n The given integer.

@return The nth Fibonacci number. */

void writeArrayBackward(const char anArray2[], int first, int last)

/** Writes the characters in an array backward.

@pre The array anArray contains size characters, where size >= 0.

@post None.

@param anArray The array to write backward.

@param first The index of the first character in the array.

@param last The index of the last character in the array. */

void writeBackward(string s)

/** Writes a character string backward.

@pre The string s to write backward.

@post None.

@param s The string to write backward. */

void writeBackwardIterative(string s)

/** Iterative version. */

int sumUpTo(int n)

/** Computes the sum of the integers from 1 through n.

@pre n > 0.

@post None.

@param n A positive integer.

@return The sum 1 + 2 + . . . + n. */

Test your functions with followings:

      int anArray[SIZE] = {1, 5, 9, 12, 15, 21, 29, 31};

      char anArray2[3] ={'c','a','t'};

      char A, B, C;

      string s = "cat";

SAMPLE RUN

1. Binary search with anArray

Search for 9 return 2

Search for 6 returns - 1

2. fact(3) reutrns 6

3. iterativeRabbit(6) returns 8

4. rabbit(6) returns 8

5. writeArrayBackward(anArray2, 0, 2) returns tac

6. writeBackward(s) returns tac

7. writeBackwardIterative(s) returns tac

8. sumUpTo<10> returns 55

Explanation / Answer

#include <iostream>

using namespace std;

int binarySearch(const int anArray[], int first, int last, int target);

int fact(int n);

int iterativeRabbit(int n);

int rabbit(int n);

void writeArrayBackward(char anArray2[], int first, int last);

void writeBackward(string s);

void writeBackwardIterative(string s);

int sumUpTo(int n);

int main() {

int anArray[] = {1, 5, 9, 12, 15, 21, 29, 31};

char anArray2[3] ={'c','a','t'};

char A, B, C;

string s = "cat";

cout<<"Searching index of 9 in anArray: " << binarySearch(anArray,0,7,9) << endl;

cout<<"Searching index of 6 in anArray: " << binarySearch(anArray,0,7,6) << endl;

cout<<"fact(3): " << fact(3) << endl;

cout<<"iterativeRabbit(6): " << iterativeRabbit(6) << endl;

cout<<"rabbit(6): " << rabbit(6) << endl;

writeArrayBackward(anArray2, 0, 2);

cout<<"writeArrayBackward(anArray2, 0, 2): ";

for(int i=0;i<3;i++) {

cout<< anArray2[i];

}

cout<< endl << "writeBackward(s) : ";

writeBackward(s);

cout<< endl << "writeBackwardIterative(s) : ";

writeBackwardIterative(s);

cout<<"sumUpTo(10): " << sumUpTo(10) << endl;

}

int binarySearch(const int anArray[], int first, int last, int target)

{

if (last >= first)

{

int mid = first + (last - first)/2;

if (anArray[mid] == target)  

return mid;

// it can only be present in left subarray

if (anArray[mid] > target)

return binarySearch(anArray, first, mid-1, target);

return binarySearch(anArray, mid+1, last, target);

}

return -1;

}

int fact(int n) {

if (n<=0)

return 1;

else

return n*fact(n-1);

}

int iterativeRabbit(int n) {

int previous = 1;

int current = 1;

int next = 1;

for (int i = 3; i <= n; ++i)

{

next = current + previous;

previous = current;

current = next;

}

return next;

  

}

int rabbit(int n){

if (n <= 1)

return n;

return rabbit(n-1) + rabbit(n-2);

}

void writeArrayBackward(char anArray2[], int first, int last) {

if (first < last) {

char temp = anArray2[first];

anArray2[first] = anArray2[last];

anArray2[last] = temp;

++first;

--last;

writeArrayBackward(anArray2, first, last);

}

}

void writeBackward(string s){

if (s.length() >= 1) {

char temp = s[0];

writeBackward(s.substr(1));

cout << temp;

}

}

void writeBackwardIterative(string s) {

int n = s.length();

for (int i=0; i<n/2; i++) {

char temp = s[i];

s[i] = s[n-i-1];

s[n-i-1] = temp;

}

cout<< s << endl;

}

int sumUpTo(int n) {

return n * (n+1) / 2;

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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