C++代写：CSCI1113 Strings and Recursion

发表于   |   分类于

代写关于String和Recursion的两个练习作业。

Recursion

Recursion is an abstraction that is defined in terms of itself. Examples include mathematical abstractions such as Fibonacci series, Factorials, and Exponentials, and other abstractions such as the Towers of Hanoi puzzle, the Eight Queens problem and Fractal Geometry. Recursion is actually an alternate form of repetition. So far, we’ve employed repetition using loops (while, do-while, and for), but many interesting and challenging computational problems are difficult to solve in an iterative fashion. Often these problems have very simple and elegant recursive solutions.

After working though the following exercises using the methods discussed in class, you should begin to get a feel for “thinking recursively” as a problem solving technique.

Strings

Representing textual information using sequences of characters is common throughout computing. Names, sentences, text, prompts, etc. all need a proper representation. We’ve been using string literals since the first week of the course when we discovered how to write “Hello World” to the computer display.

In addition to representing non-numeric and qualitative information, string objects are frequently used in engineering and scientific applications to input and process large text files containing measurements, experimental test data, and so forth.

Comma Separated Value files (CSV)

One common format for representing large data files is the “comma separated value” (CSV) format. For example, if you have data in an Excel spreadsheet, it is a simple matter to output it to a file in CSV format.

The CSV format is simplicity itself: each data element is stored as a text string separated from the succeeding value by a single comma (‘ , ‘). If the file data is tabular (rows and columns), the rows are separated using a single newline character (‘\n’). This makes it possible to use a standard text-editor to view the contents of any CSV formatted file in order to determine its organization.

Getline()

Processing the data in a CSV formatted file requires that you identify and separate the individual values in each row. Individual rows are read using the getline(stream, string) function which returns the entire comma-separated row as a C++ string object. The row string must then be parsed by your program, separating values from the comma separators. This requires some fluency with manipulating strings which we will explore in this Lab Exercise.

Converting Strings to Values

The “values” that are obtained from each CSV string (row) are character strings. Before they can be used in a computation, they must be converted to numeric values (floating-point or integer). There are many clever ways to do this in C++, but the simplest method is to use the functions atof and/or atoi, found in the standard C++ library: <cstdlib>. These functions both take a c_string as an argument and return a double or int respectively. Recall that c_strings and C++ string objects are not the same thing! If the character string you wish to convert to a value is stored in a C++ string object, you first need to convert it to a c_string using the string class method c_str:

1
double foo = atof(somestring.c_str())

Mystery-Box Challenge

Here is your next mystery-box challenge. Determine what the following function does and explain it to one of your TAs.

1
2
3
4
5
6
7
bool mystery(string fstr)
{
  string rstr;
  for (int i=fstr.length()-1; i>=0 ;i--)
    rstr += fstr[i];
  return rstr == fstr;
}

Warm-up

Recursive max

Consider a recursive function to find the maximum value in an array of integers. The function declaration is:

1
int maxValue(int vals[], int size, int start);

For this function, we need to know the size of the array and the starting index of the array (because both will change when a recursive call is made). You may assume that there is at least one value in the array:

  1. Describe the base case
    Hint: in what size array would it be easiest to find the maximum value?
  2. Describe the reduction step.
    Hint: describe the original problem using the base case in combination with some reduced form of the problem.
  3. Describe why the reduction step will (i) solve the problem and (ii) move closer to the base case.
  4. Write the complete function definition for maxValue.

Stretch

Binomial Coefficients

In probability and statistics applications, you often need to know the total possible number of certain outcome combinations. For example, you may want to know how many ways a 2-card BlackJack hand can be dealt from a 52 card deck, or you may need to know the number of possible committees of 3 people that can be formed from a 12-person department, etc. The binomial coefficient (often referred to as “n choose k”) will provide the number of combinations of k things that can be formed from a set of n things.

Returning Individual CSV Values

Write a function named nextString that will return a single ‘value’ (i.e. substring) from a Comma Separated Value” string. Your function will take two arguments: a string variable containing a comma separated list of values, and an integer containing the starting index; your function should return a single string object with the value that starts at that index and ends right before the next comma ‘,’ (do not include the comma in the returned string!) :

1
string nextString(string str, int start_index);

If, however, the start index is after the last comma in the string, then the function should return the value starting at that index and continuing to the end of the string.
For example,

1
cout << nextString("my,cat,ate,my,homework",3);

will print

cat

and

1
cout << nextString("my,cat,ate,my,homework",8);

will print

te

and

1
cout << nextString("my,cat,ate,my,homework",18);

will print

work

When you have written your function, then write a short test program that will take in a simple comma separated string using getline:

1
getline(cin,somestring)

and output values in the string using the nextString function.

Split

Now, extend your test program by adding a second function named split that will identify all the individual values in a comma separated value string and return them in an array of string objects:

1
int split(string str, string a[], int max_size);

Your function will take three arguments: a comma separated value string str, an array a of string objects, and the maximum size of the array. You must use the nextString function from Stretch Problem (1) to obtain each value in the string and store it in the array starting, with the first element. Return the total number of values stored in the array.

For example:

1
2
3
4
string varray[VALUES];
int cnt = split("my,cat,ate,my,homework",varray,VALUES);
for (int i=0; i<cnt; i++)
  cout << varray[i] << endl;

Should produce:

my
cat
ate
my
homework