C++代写:CSCI1113StringsandRecursion


代写关于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 :
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.
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:
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!) :
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,
cout << nextString(“my,cat,ate,my,homework”,3);
—|—
will print
cat
and
cout << nextString(“my,cat,ate,my,homework”,8);
—|—
will print
te
and
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:
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:
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:
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


文章作者: SafePoker
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 SafePoker !
  目录