Each week, you’ll meet for about an hour in a small discussion section. Your section leader will help review the material, explore some topics in more depth, and generally answer questions as appropriate.
每周，你们将在一个小讨论组中进行大约一个小时的讨论。讨论小组组长将帮助你们复习教材，深入探讨某些主题，并回答适当的问题。
These section problems are designed to give you some extra practice with the course material. You’re not expected to complete these problems before attending section and we won’t be grading them for credit.
这些章节问题旨在为您提供一些有关课程材料的额外练习。我们不要求您在参加课程之前完成这些问题，也不会对这些问题进行学分评分。
Instead, think of them as a resource you can use to practice with the material as you see fit. You’re not expected to cover all these problems in section, so feel free to look over the solutions to the problems you didn’t complete.
相反，请将它们视为一种资源，您可以根据自己的需要利用它们来练习教材。我们并不要求您在章节中完成所有这些问题，因此，您可以随时查看未完成问题的解答。
📦 Starter code
📦 启动代码
1) Returning and Printing
1) 返回和打印
Topics: Function call and return, return types
主题函数调用和返回、返回类型
Below is a series of four printLyrics_v# functions, each of which has a blank where the return type should be. For each function, determine
下面是一系列四个 printLyrics_v# 函数，每个函数的返回类型处都有空白。请为每个函数确定
- what the return type of the function should be,
函数的返回类型、 - what value, if any, is returned, and
返回值（如果有），以及 - what output, if any, will be produced if that function is called.
如果调用该函数，会产生什么输出（如果有的话）。
Is it appropriate for each of these functions to be named printLyrics? Why or why not?
将这些函数分别命名为 printLyrics 是否合适？为什么或为什么不合适？
_____ printLyrics_v1() {
cout << "Havana ooh na na" << endl;
}
_____ printLyrics_v2() {
return "Havana ooh na na";
}
_____ printLyrics_v3() {
return "H";
}
_____ printLyrics_v4() {
return 'H';
}
void printLyrics_v1() {
cout << "Havana ooh na na" << endl;
}
string printLyrics_v2() {
return "Havana ooh na na";
}
string printLyrics_v3() {
return "H";
}
char printLyrics_v4() {
return 'H';
}
Of these four functions, only printLyrics_v1 will print anything. Specifically, it prints out the string "Havana ooh na na.". The name “printLyrics” is inappropriate for the other functions, as those functions don’t actually print anything. 😃
The function printLyrics_v1 doesn’t return anything – it just sends information to the console. As a result, its return type should be void. The functions printLyrics_v2 and printLyrics_v3 each return strings, since C++ treats anything in double-quotes as a string. Finally, printLyrics_v4 returns a char, since C++ treats anything in single-quotes as a character.
2) Recursion Tracing
2) 递归跟踪
Topics: Recursion, strings, recursion tracing
主题：递归、字符串、递归跟踪
In lecture, we wrote the following recursive function to reverse a string:
在讲座中，我们编写了以下递归函数来反转字符串：
string reverseOf(string s) {
if (s == "") {
return "";
} else {
return reverseOf(s.substr(1)) + s[0];
}
}
Trace through the execution of reverseOf("stop") along the lines of what we did in Wednesday’s lecture, showing stack frames for each call that’s made and how the final value gets computed.
按照我们在周三讲座中的做法，跟踪 reverseOf("stop") 的执行过程，显示每次调用的堆栈框架以及如何计算最终值。
Our initial call to reverseOf("stop") looks like this:
This call then fires off a call to reverseOf("top"), which looks like this:
This call fires off a call to reverseOf("op"):
This in turn calls reverseOf("p"):
This in turn calls reverseOf(""):
This triggers the base case and returns the empty string. (Notice that the reverse of the empty string "" is indeed the empty string ""):
We now append p to return "p":
We now append o to return "po":
We append t to return "pot":
And finally we append s to return "pots" back to whoever called us. Yay!
3) Testing and Debugging
3) 测试和调试
Topics: Testing, loops, types, function call and return
主题测试、循环、类型、函数调用和返回
Consider the following piece of code:
请看下面这段代码：
/* Watch out! This code contains many bugs! */
bool hasDoubledCharacter(string text) {
for (int i = 0; i < text.size(); i++) {
string current = text[i];
string previous = text[i - 1];
return current == previous;
}
}
This code attempts to check whether a string contains at least two consecutive copies of the same character. Unfortunately, it has some errors in it.
这段代码试图检查一个字符串是否至少包含两个连续的相同字符。不幸的是，它有一些错误。
- Identify and fix all the errors in this code.
找出并修复代码中的所有错误。
We can write test cases to check our work and ensure that the code indeed works as expected. Imagine you’re given the following provided test:
我们可以编写测试用例来检查我们的工作，并确保代码确实按预期运行。想象一下，你会得到以下测试：
PROVIDED_TEST("Detects doubled characters") {
EXPECT(hasDoubledCharacter("aa"));
EXPECT(hasDoubledCharacter("bb"));
}
This test checks some cases, but leaves others unchecked. As a result, even if these tests pass, it might still be the case that the function is incorrect.
该测试会检查某些情况，但不会检查其他情况。因此，即使这些测试通过了，函数仍可能是不正确的。
- Identify three types of strings not tested by the above test case. For each of those types of strings, write a
STUDENT_TESTthat covers that type of string.
确定上述测试用例未测试的三种字符串类型。针对每种类型的字符串，编写涵盖该类型字符串的STUDENT_TEST。
Here’s a list of the errors in the code:
-
It uses the
stringtype instead of thechartype when representing individual characters in the string. This will cause the code to not compile. -
On the first iteration of the loop, we will try to look at the -1 st character of the string, which will probably cause a crash and definitely is wrong.
-
The
returnstatement inside the for loop means that we’ll never look at more than one pair of characters; the function will exit as soon as the return statement is executed, so we can’t progress from one iteration to the next. -
If the string doesn’t contain any doubled characters, the function never returns a value.
We can fix all of these errors by rewriting the code like this:
bool hasDoubledCharacter(string text) {
for (int i = 1; i < text.size(); i++) {
char current = text[i];
char previous = text[i - 1];
if (current == previous) {
return true;
}
}
return false;
}
To make things cleaner, we could remove the current and previous variables:
bool hasDoubledCharacter(string text) {
for (int i = 1; i < text.size(); i++) {
if (text[i] == text[i - 1]) {
return true;
}
}
return false;
}
Although we hadn't talked about pass-by-const reference in the first week of class, we really should use the pass-by-const reference here because we are reading but not modifying the text parameter.
bool hasDoubledCharacter(const string& text) {
for (int i = 1; i < text.size(); i++) {
if (text[i] == text[i - 1]) {
return true;
}
}
return false;
}
Now, let’s talk testing. Notice that the test cases we have are purely for
-
strings that have doubled characters,
-
where the doubled letters are at the beginning,
-
where there are no undoubled characters,
-
where the doubled characters are lower-case letters, and
-
that have length exactly two.
To find some classes of strings that don’t have these properties, we can simply break all of the above rules and see what we find! So let’s write tests for each of the following types of strings:
-
strings that don’t have doubled letters;
-
strings that have doubled letters, but not at the beginning;
-
strings that have doubled letters, but also some non-doubled letters;
-
strings that have doubled non-letter characters; and
-
strings whose lengths aren’t two (maybe shorter strings or longer strings).
Here’s some sample tests we could write:
STUDENT_TEST("Strings without doubled characters") {
EXPECT(!hasDoubledCharacter("abcd")); // Nothing doubled
EXPECT(!hasDoubledCharacter("aba")); // a appears twice, but not consecutively
EXPECT(!hasDoubledCharacter("Aa")); // Not technically the same character
}
STUDENT_TEST("Strings with doubled characters not at the front") {
EXPECT(hasDoubledCharacter("abb")); // Back
EXPECT(hasDoubledCharacter("abcddabc")); // Middle
}
STUDENT_TEST("Strings with doubled non-letter characters") {
EXPECT(hasDoubledCharacter("**")); // Symbols
EXPECT(hasDoubledCharacter(" ")); // Spaces
EXPECT(hasDoubledCharacter("00")); // Numbers
EXPECT(hasDoubledCharacter("!!")); // Punctuation
}
STUDENT_TEST("Short strings") {
EXPECT(!hasDoubledCharacter("")); // Too short
EXPECT(!hasDoubledCharacter("a")); // Too short
}
4) Human Pyramids
4) 人类金字塔
Topics: Recursion
主题递归
A human pyramid is a triangular stack of a bunch of people where each person (except the person at the top) supports their weight on the two people below them. A sample human pyramid is shown below.
人体金字塔是由一群人组成的三角形堆叠，每个人（除了最上面的人）的重量都由下面的两个人支撑。下图是一个人字金字塔的示例。
Your task is to write a function
您的任务是编写一个函数
int peopleInPyramidOfHeight(int n);
that takes as input the height of the human pyramid (the number of layers; the pyramid to the right has height three) and returns the number of people in that pyramid. Your function should be completely recursive and should not involve any loops of any sort.
输入人类金字塔的高度（层数；右边的金字塔高度为 3），并返回该金字塔中的人数。您的函数应该是完全递归的，不应涉及任何循环。
As a hint, think about what happens if you take the bottom layer off of a human pyramid.
作为提示，想想如果把人类金字塔的底层去掉会发生什么。
Once you’ve written your solution, trace through the execution of peopleInPyramidOfHeight(3) similarly to how we traced through factorial(5) in class, showing each function call and how values get returned.
写完解决方案后，请跟踪 peopleInPyramidOfHeight(3) 的执行情况，就像我们在课堂上跟踪 factorial(5) 一样，显示每次函数调用和返回值的方式。
As a note, there’s a closed-form solution to this problem (you can directly compute how many people are in the pyramid just from the height through a simple formula). It’s described in the solutions.
需要注意的是，这个问题有一个封闭式的解决方案（通过一个简单的公式，你可以直接从高度计算出金字塔里有多少人）。解决方案中对此进行了描述。
The key recursive insight here is that a human pyramid of height 0 is a pyramid of no people, and that a human pyramid of height n is a group of n people supporting a human pyramid of n-1 people. Using that idea, we can write this function:
int peopleInPyramidOfHeight(int n) {
if (n == 0) {
return 0;
} else {
return n + peopleInPyramidOfHeight(n - 1);
}
}
As a note, you can directly evaluate peopleInPyramidOfHeight(n) by computing n(n + 1) / 2. We’ll see a really cool intuition for this later in the quarter!
5) Random Shuffling
5)随机洗牌
How might the computer shuffle a deck of cards?
电脑如何洗牌？
This problem is a bit more complex than it might seem, and while it's easy to come up with algorithms that randomize the order of the cards, only a few algorithms will do so in a way that ends up generating a uniformly-random reordering of the cards.
这个问题比想象的要复杂一些，虽然很容易想出随机化纸牌顺序的算法，但只有少数算法能做到最终产生统一随机的纸牌顺序。
One simple algorithm for shuffling a deck of cards is based on the following idea:
洗牌的一种简单算法基于以下想法：
- Choose a random card from the deck and remove it.
从牌组中随机抽取一张牌并移除。 - Shuffle the rest of the deck.
洗剩下的牌。 - Place the randomly-chosen card on top of the deck.
Assuming that we choose the card that we put on top uniformly at random from the deck, this ends up producing a random shuffle of the deck.
将随机选择的牌放在牌面上。假设我们从扑克牌中均匀随机地选择了放在上面的牌，那么最终就会产生随机洗牌的结果。
Write a function
编写函数
string randomShuffle(string input)
that accepts as input a string, then returns a random permutation of the elements of the string using the above algorithm. Your algorithm should be recursive and not use any loops (for, while, etc.).
接受一个字符串作为输入，然后使用上述算法返回字符串元素的随机排列。你的算法应该是递归的，不应该使用任何循环（ for , while 等）。
The header file "random.h" includes a function
头文件 "random.h" 包含一个函数
int randomInteger(int low, int high);
that takes as input a pair of integers low and high, then returns an integer greater than or equal to low and less than or equal to high. Feel free to use that here.
输入一对整数 low 和 high，然后返回一个大于或等于 low 和小于或等于 high 的整数。请在此随意使用。
Interesting note: This shuffling algorithm is a variant of the Fisher-Yates Shuffle. For more information on why it works correctly, take CS109!
有趣的是：这种洗牌算法是费舍尔-耶茨洗牌法的一种变体。如需了解其正确运作的更多信息，请参阅 CS109！
Here is one possible solution:
string randomShuffle(string input) {
/* Base case: There is only one possible permutation of a string
* with no characters in it.
*/
if (input.empty()) {
return input;
} else {
/* Choose a random index in the string. */
int i = randomInteger(0, input.length() - 1);
/* Pull that character to the front, then permute the rest of
* the string.
*/
return input[i] + randomShuffle(input.substr(0, i) + input.substr(i + 1));
}
}
This function is based on the recursive observation that there is only one possible random shuffle of the empty string (namely, itself), and then using the algorithm specified in the handout for the recursive step.
Here is another possible solution (using a modified function header) which shows how to implement this function using references and no return value. Shoutout to one of our awesome SLs, Rachel Gardner, for this alternate solution!
void randomShuffle(string &input) {
if (input == "") return;
int rand = randomInteger(0, input.length() - 1);
char chosen = input[rand];
input.erase(rand, 1);
randomShuffle(input);
input = chosen + input;
}
6) Computing Statistics
6) 计算统计
Topics: Structures, file reading, loops
主题结构、文件读取、循环
Imagine you have a file containing a list of real numbers, one per line (perhaps they’re exam scores, or blood pressure numbers, etc.) Your task is to write a function
想象一下，您有一个文件，其中包含一个实数列表，每行一个（可能是考试分数或血压数字等）。
Statistics documentStatisticsFor(istream& input);
that takes as input a reference to an input stream pointed at the contents of a file, then returns a Statistics object (described below) containing statistics about that document. You can assume that the file is properly formatted and contains at least one number.
该程序将指向文件内容的输入流引用作为输入，然后返回一个包含该文件统计信息的 Statistics 对象（如下所述）。可以假设文件格式正确，至少包含一个数字。
The Statistics type used here is a struct that’s defined as follows:
这里使用的 Statistics 类型是一个结构体，其定义如下：
struct Statistics {
double min; // Smallest value in the file
double max; // Largest value in the file
double average; // Average value in the file
}
As a reminder, you can read a single value from a file by writing
作为提醒，您可以通过写入
double val;
input >> val;
and read all the values left in a file by writing
并通过写入
for (double val; input >> val;) {
// Do something with val
}
There are many ways to write this function. Here's one:
Statistics documentStatisticsFor(istream& input) {
/* Read an initial value out of the file. We're going to use this to seed
* the minimum and maximum values.
*/
double val;
input >> val; // Should do error-checking, but we'll skip that here.
/* Create a Statistics object and initialize its min and max values. */
Statistics info;
info.min = val;
info.max = val;
/* Keep track of the sum of the values and the number of values so that we
* can report back the average value. Initially, the sum is whatever value
* we just read, and the number of values read is 1.
*/
double total = val;
int numValues = 1;
/* Read the rest of the file, updating the min/max as we go along with the
* sum and number of values.
*/
while (input >> val) {
numValues++;
total += val;
if (val > info.max) info.max = val;
if (val < info.min) info.min = val;
}
/* Compute the average. */
info.average = total / numValues;
return info;
}
7) Haiku Detection
7) 俳句检测
Topics: TokenScanner, procedural decomposition
主题： TokenScanner ，程序分解
A haiku is a three-line poem where the first line has five syllables, the second has seven syllables, and the final line has five syllables. For example, this poem is a haiku:
俳句是一首三行诗，第一行有五个音节，第二行有七个音节，最后一行有五个音节。例如，这首诗就是一首俳句：
An observation:
Haikus are concise, but they
Don't always say much.
This poem is not a haiku, because the last line has six syllables.
这首诗不是俳句，因为最后一行有六个音节。
One two three four five
Six seven eight nine ten, then
eleven, twelve, thirteen!
Your job is to write a program that reads three lines of text from the user, then checks whether those lines form a haiku. You can assume that you have access to a function
你的任务是编写一个程序，从用户处读取三行文本，然后检查这三行是否构成一首俳句。你可以假设你可以访问一个函数
int syllablesIn(string word);
which returns the total number of syllables in a word. You can assume that the input text consists solely of words, spaces, and punctuation marks (e.g. commas and exclamation points). You may want to use the TokenScanner type here. You can use TokenScanner to break a string apart into individual units as follows:
返回单词的音节总数。可以假设输入文本仅由单词、空格和标点符号（如逗号和感叹号）组成。您可能希望在此处使用 TokenScanner 类型。您可以使用 TokenScanner 将字符串拆分成以下单个单元：
#include "tokenscanner.h" // At the top of your program
TokenScanner scanner(str);
scanner.ignoreWhitespace();
while(scanner.hasMoreTokens()) {
string token = scanner.nextToken();
// Do something with token
}
Note: we are not providing a starter file for this one; we encourage you to think about how
you want to decompose it and discuss with your section leader and section-mates!
注意：我们没有为这一主题提供启动文件；我们鼓励你们思考如何分解这一主题，并与你们的组长和组员进行讨论！
/* We will assume that
* this function works. It's fun to
* implement. Try it!
*/
int syllablesIn(string word);
/* These are prototypes.
* They let us call these functions
* Before they're defined.
*/
bool isHaiku(string line1, string line2, string line3);
int syllablesInLine(string line);
int main() {
string line1 = getLine("Enter the first line: ");
string line2 = getLine("Now, enter the second line: ");
string line3 = getLine("Enter the third line: ");
/* Given these three lines,
* check whether they're a haiku,
* then show the result.
*/
if (isHaiku(line1, line2, line3)) {
cout << "The text you entered" << endl;
cout << "Goes 5 - 7 - 5, so it" << endl;
cout << "is a haiku. Yay!" << endl;
} else {
cout << "Though you have tried hard," << endl;
cout << "The three lines you entered are" << endl;
cout << "Not a haiku. Awww." << endl;
}
return 0;
}
/* Given a poem
* of three lines, returns whether
* it is a haiku.
*/
bool isHaiku(string line1, string line2, string line3) {
return syllablesInLine(line1) == 5 &&
syllablesInLine(line2) == 7 &&
syllablesInLine(line3) == 5;
}
/* Counts the number of
* syllables in a line of
* text, then returns it.
*/
int syllablesInLine(string text) {
/* To split apart the
* text, make a TokenScanner
* and configure it.
*/
TokenScanner scanner(text);
scanner.ignoreWhitespace();
int numSyllables = 0;
while (scanner.hasMoreTokens()) {
/* If this token is
* a word, count its syllables
* and update total.
*/
string token = scanner.nextToken();
if (scanner.getTokenType(token) == TokenScanner::TokenType::WORD) {
numSyllables += syllablesIn(token);
}
}
return numSyllables;
}
/* Did you notice that
* all the comments are haikus?
* Same with the output!
*/