C++代写 | CSCI-311 Assignment Recursive Functions Strings

本次C++代写要求使用C++中的vector实现各种字符串转换处理及递归函数处理。

Problem 1. Given a vector A of integers, write a recursive function that finds the minimum number in A. Your function must have two recursive calls and must return an integer (there is no output).

You need to write the following function with the exact header as shown:

int recMin(const vector<int> &A, int start, int fin);

Example: A = {32, 17, 5, 28, 44, 19, 3, 63}, your function will return 3.

 

Problem 2. Given a vector A of integers of size n, write a recursive function that calculates the sums of all subarrays A[0…i], 0 ≤ i ≤ n-1. Your function must have one recursive call.

You need to write the following function with the exact header as shown:

void subarraySums(const vector<int> &A, vector<int> &B, int fin);

Example: A = {3, 2, 4, 1, 5}. Initially vector B has the same size as A and initialized to 0. At the end of your function, B = {3, 5, 9, 10, 15}. At entry B[i], the sum A[0]+A[1]+…+A[i] is stored. For example, B[2] = 9 = 3 + 2 + 4.

 

Problem 3. Given a vector A of integers, write a recursive function that returns true if A is a palindrome; and false, otherwise. Your function must have one recursive call.

You need to write the following function with the exact header as shown:

bool recPal(const vector<int> &A, int first, int last);

Example: A = {3, 2, 1, 2, 3} is a palindrome; A = {3, 2, 2, 3} is also a palindrome; but A = {3, 4, 5, 2, 6, 4, 3} is not.

 

Problem 4. Given a vector A of distinct integers in increasing order and an integer k. Write a recursive function that returns true if k occurs in A. Your function must have one recursive call.

You need to write the following function with the exact header as shown:

bool recFindSorted(const vector<int> &A, int k, int start, int fin);

Example: A = {12, 15, 17, 21, 34, 59, 67, 82} and k = 67, then your function will return true. If A is the same, but k = 13, then your function will return false.

 

Problem 5. Given a vector A with distinct integers in increasing order. Write a recursive function that returns an integer index such that index = A[index]. If no such index exists, your function will return -1. Your function must have one recursive call.

You need to write the following function with the exact header as shown:

int findIndex(const vector<int> &A, int start, int fin);

Example: A = {-11, -5, 2, 14, 25, 49, 52}, then your function will return index 2 because 2 = A[2]. If A is A = {-20, 0, 5, 12, 34}, then your function will return -1.

 

Problem 6. Given a vector A of integers (in any order) and an integer k. Write a recursive function that returns true if k is in A. Your function must have two recursive calls.

You need to write the following function with the exact header as shown:

bool recFind(const vector<int> &A, int k, int start, int fin);

This problem is solved similarly to Problem 1.

 

Problem 7. Power Set. Given a set of integers (i.e. a vector of distinct integers – sets do not have repeats). Find and print the Power Set of the given set (except for an empty subset). There is one recursive call.

Definition: The Power Set of a given set of integers A is the set of all subsets of A including an empty subset {} and the entire A itself.

Example: A = {2, 5, 4}, PowerSet(A) = { {}, {2}, {5}, {2, 5}, {4}, {2, 4}, {5, 4}, {2, 5, 4} }.

You need to write the following function with the exact header as shown: void powerSet(const vector<int> &A, vector< vector<int> > &P, int last);

Initially, vector P (power set of A) is empty, and by the end of execution, it will contain the power set of A (except for the empty subset).

 

Problem 8. Print All Permutations. Given a string s of size n. Write a function that prints all permutations of s. Your function must have one recursive call.

Definition: Given a string s of n characters, a permutation of s is a re-ordering of characters in s.

Example: s = “abc”, then all permutations of s are: abc, bac, bca, acb, cab, cba.

You need to write the following function with the exact header as shown:

void findPerms(const string &s, queue<string> &p, int first);

Initially queue p (permutations) is empty, and by the end of execution, it will contain all permutations of s.

Function Name_______________

Test Files__________________

recMin

T01

subarraySums

T02

recPal

T03

recFindSorted

T04

findIndex

T05

recFind

T06

powerSet

T07

findPerms

T08

findInMatrix

T09