基础的C++入门练习题，完成五个函数的编写，以及一个迷宫寻路小程序。

Problem 1

Here are five functions, with descriptions of what they are supposed to do. They are incorrectly implemented. Replace the incorrect implementations of these functions with correct ones that use recursion in a useful way; your solution must not use the keywords while, for, or goto. You must not use global variables or variables declared with the keyword static, and you must not modify the function parameter lists. You must not use any references or pointers as parameters except for the parameters representing arrays.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// Returns the product of two positive integers, m and n,
// using only repeated addition.
int mult(unsigned int m, unsigned int n)
{
    return -1;  // This is incorrect.
}

// Returns the number of occurrences of digit in the decimal
// representation of num. digit is an int between 0 and 9
// inclusive.
//
// Pseudocode Example:
//    countDigit(18838, 8) => 3
//    countDigit(55555, 3) => 0
//    countDigit(0, 0)     => 0 or 1 (either if fine)
//
int countDigit(int num, int digit)
{
    return -1;  // This is incorrect.
}

// Returns a string where the same characters next each other in
// string n are separated by "++"
//
// Pseudocode Example:
//    pairPlus("goodbye") => "go++odbye"
//    pairPlus("yyuu")    => "y++yu++u"
//    pairPlus("aaaa")    => "a++a++a++a"
//
string pairPlus(string n)
{
    return "";  // This is not always correct.
}

// str contains a single pair of parenthesis, return a new string
// made of only the parenthesis and whatever those parensthesis
// contain.
//
//  Pseudocode Example:
//     subParen("abc(ghj)789") => "(ghj)"
//     subParen("(x)7")        => "(x)"
//     subParen("4agh(y)")     => "(y)"
//
string subParen(string str)
{
    return "*";  // This is incorrect.
}

// Return true if the sum of any combination of elements in the array
// a equals the value of the target.
//
//  Pseudocode Example:
//     sumCombination([2, 4, 8], 3, 10) => true
//     sumCombination([2, 4, 8], 3, 12) => true
//     sumCombination([2, 4, 8], 3, 11) => false
//     sumCombination([], 0, 0)         => true
//
bool sumCombination(const int a[], int size, int target)
{
    return false;  // This is not always correct.
}

Problem 2

Write a C++ function named pathExists that determines whether or not a theres a path from start to finish in a rectangular maze. Here is the prototype:

1
2
3

bool pathExists(string maze[], int nRows, int nCols, int sr, int sc, int er, int ec);
  // Return true if there is a path from (sr,sc) to (er,ec)
  // through the maze; return false otherwise

The parameters are

• A rectangular maze of Xs and dots that represents the maze. Each string of the array is a row of the maze.
• Each X represents a wall, each @ represents a bottomless trap hole, and each . represents a walkway.
• The number of rows in the maze.
• The number of columns in the maze. Each string in the maze parameter must be this length.
• The starting coordinates in the maze: sr, sc; the row number is in the range 0 through nRows-1, and the column number is in the range 0 through nCols-1.
• The ending coordinates in the maze: er, ec; the row number is in the range 0 through nRows-1, and the column number is in the range 0 through nCols-1.

Here is an example of a simple maze with 5 rows and 7 columns:

"XXXXXXX""X...X@X""XXX.X.X""[email protected]""XXXXXXX"

The function must return true if in the maze as it was when the function was called, there is a path from maze[sr][sc] to maze[er][ec] that includes only walkways, no walls or bottomless trap holes; otherwise it must return false. The path may turn north, east, south, and west, but not diagonally. When the function returns, it is allowable for the maze to have been modified by the function.

(Our convention is that (0,0) is the northwest (upper left) corner, with south (down) being the increasing r direction and east (right) being the increasing c direction.)

Here is pseudocode for your function:

If the start location is equal to the ending location, then we'vesolved the maze, so return true.Mark the start location as visted.For each of the four directions,If the location one step in that direction (from the startlocation) is unvisited,then call pathExists starting from that location (andending at the same ending location as in thecurrent call).If that returned true,then return true.Return false.

(If you wish, you can implement the pseudocode for loop with a series of four if statements instead of a loop.)

Here is how a client might use your function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int main()
{
  string maze[10] = {
    "XXXXXXXXXX",
    "X.......@X",
    "XX@X@@.XXX",
    "X..X.X...X",
    "[email protected]",
    "X....XXX.X",
    "[email protected]",
    "X..XX.XX.X",
    "X...X....X",
    "XXXXXXXXXX"
  };
        
  if (pathExists(maze, 10,10, 6,4, 1,1))
    cout << "Solvable!" << endl;
  else
    cout << "Out of luck!" << endl;
}

Because the focus of this homework is on practice with recursion, we wont demand that your function be as robust as we normally would. In particular, your function may make the following simplifying assumptions (i.e., you do not have to check for violations):

• the maze array contains nRows rows (you couldnt check for this anyway);
• each string in the maze is of length nCols;
• the maze contains only Xs, @s, and dots when passed in to the function;
• the top and bottom rows of the maze contain only Xs, as do the left and right columns;
• sr and er are between 0 and nRows-1, and sc and ec are between 0 and nCols-1;
• maze[sr][sc] and maze[er][ec] are . (i.e., not walls or bottomless trap holes)

(Of course, since your function is not checking for violations of these conditions, make sure you dont pass bad values to the function when you test it.)