辅导CSCI1120、讲解C++编程语言、辅导C++设计、program留学生讲解
- 首页 >> Java编程 CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering,
Assignment 2: Missionaries and cannibals problem
Due: 20:00, Thu 8 Oct 2020 File name: rowboat.cpp Full marks: 100
Introduction
The objective of this assignment is to let you practice the use of variables, operators, expressions,
standard input/output and control flow in C++. You are to write a program to simulate a game based
on a classic river-crossing puzzle known as the “missionaries and cannibals” (“M&C”) problem.
In a classical setting of the puzzle, three missionaries and three cannibals are on one bank of a river.
There is one boat available that can carry at most two people. They would use it to cross the river. If
the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will
get eaten! The boat cannot cross the river by itself with no people on board. Under these constraints,
how can the boat be used to safely carry all the missionaries and cannibals across the river?
This problem is commonly turned into a game. You may play this game online on this website
(Adobe Flash required) and watch a YouTube video showing the solution.
In this assignment, you are to write a similar game program which is played via the console instead
of a graphical user interface. As another difference, we would generalize the problem. That means
the program should let the user input the number of missionaries, cannibals and the boat capacity at
the beginning. The program then repeatedly prompts the user for how many missionaries and/or
cannibals to get on the boat. It will check if the input numbers are valid under the above constraint
and show the current game state. The aim of the program is not about implementing any solution
search algorithm to solve the puzzle (which is beyond our scope) but simply supporting the user to
play the game.
Assume that all people are on the left bank initially. The current game state can be represented by a
simple vector ⟨m, c, b⟩ where m and c denote the counts of missionaries and cannibals on the left
bank respectively, and b equals 1 or 0 represents whether the boat is on the left or on the right bank,
respectively. So, the game starts with the initial state vector ⟨3, 3, 1⟩. To win the game, we need to
take successive boat trips to advance the game state towards the goal state ⟨0, 0, 0⟩, which means
that all the people and the boat are not on the left bank. They have all crossed the river!
For convenience of discussion, let us also denote a specific M&C problem in a tuple format (M, C, B)
where M and C refer to the number of missionaries and cannibals respectively, and B represents the
boat capacity. Some M&C problems have no solutions. For example, (M, C, 1) for any non-zero M, C
has no solution since the man rowing the boat that can carry only one man is doomed to returning
to the left bank with the boat or else the others can never cross the river. So, B must not be < 2.
Unless M > C, for problems with B = 2, M and C must be <= 3; for problems with B = 3, M and C must
be <= 5 or else they have no solution. For problems with B >= 4, there is no known bound on M and
C for solution existence. Of course, M must always be >= C in a valid problem.
CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 2 of 5
The following table depicts a solution to the (3, 3, 2) M&C problem. Each row shows the number of
missionaries (m) and cannibals (c) on either bank and the state transition after each boat trip (the
letter v denotes the boat which is on the left bank whenever b = 1 in the state vector).
Trip/State No. Left Bank River Right Bank State
1 m m m c c c v ⟨3, 3, 1⟩
2 m m m c → v c c ⟨3, 1, 0⟩
3 m m m c c v ← c ⟨3, 2, 1⟩
4 m m m → v c c c ⟨3, 0, 0⟩
5 m m m c v ← c c ⟨3, 1, 1⟩
6 m c → v m m c c ⟨1, 1, 0⟩
7 m m c c v ← m c ⟨2, 2, 1⟩
8 c c → v m m m c ⟨0, 2, 0⟩
9 c c c v ← m m m ⟨0, 3, 1⟩
10 c → v m m m c c ⟨0, 1, 0⟩
11 c c v ← m m m c ⟨0, 2, 1⟩
12 → v m m m c c c ⟨0, 0, 0⟩
Recall that in the vector ⟨m, c, b⟩, m and c denote the number of missionaries and cannibals on the
left bank. In other words, M - m and C - c denote the number of missionaries and cannibals on the
right bank. You win the game upon reaching the state ⟨0, 0, 0⟩ whereas you lose the game whenever
the missionaries on either bank are outnumbered by the cannibals there, i.e. m < c or M - m < C – c
for non-zero m and M - m.
Program Specification
The program should obtain three numbers as user input which control the number of missionaries
(M), the number of cannibals (C) and the boat capacity (B) at the beginning. These numbers have to
be validated against the criteria stated on p.1 to ensure that the game will have a solution before the
game gets started. Also, M and C must be >= 1 to be meaningful.
Then it starts a loop to prompt the user to enter two numbers, namely mb and cb, which represent
the number of missionaries and cannibals to get on the boat. The sum of mb and cb is bounded by B
and is at least 1 (at least one is needed for rowing the boat). Also, mb must be >= cb for missionaries
aboard not to be eaten. Of course, mb and cb cannot exceed the number of available missionaries
and cannibals on the bank concerned. Your program must check against these to assure a valid boat
trip. If any condition stated here is violated, the program will show an error message and prompt the
user for input again until a valid pair of values is obtained.
Upon receiving a valid pair of mb and cb, the program computes the current game state ⟨m, c, b⟩ and
prints the number of missionaries and cannibals on both banks and the boat position to the console
in a specific format (see the Sample Runs section). It will repeat prompting the user for new boat trip
inputs and game state handling until the state becomes ⟨0, 0, 0⟩ or the game losing condition
stated above is met, i.e. some missionaries get eaten! A game winning or losing message should
be printed accordingly.
CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 3 of 5
Output Formatting Requirements
In the Sample Runs section, please note that there are some formatting requirements your program
must follow. To display the game statistics neatly, the state, missionary and cannibal counts on
either bank are all right aligned, each in a fixed width that is set in the following manner. Suppose
that M has x digits, and C has y digits. The field widths for the number of missionaries and cannibals
on both banks will be set to x and y respectively. The field width for the state counter will be set as
maximum(x, y) + 1. Padding is added to the left of those values with # digits < the field width. Also,
there is a single space after the word “State” and every comma. See the following examples.
For M = 3, C = 3, the initial state is displayed as:
State 1: [3m, 3c]v ~~~ [0m, 0c]
For M = 30, C = 9, the initial state is displayed as:
State 1: [30m, 9c]v ~~~ [ 0m, 0c]
For M = 1000, C = 999, the initial state is displayed as:
State 1: [1000m, 999c]v ~~~ [ 0m, 0c]
A pair of square brackets is used to enclose each of the two banks. The boat is denoted by a letter v.
The river is represented by 6 characters – two spaces, then three ~ symbols, and then two spaces,
but with the leftmost or rightmost space replaced by the boat symbol v, depending on which bank
the boat is located.
Assumptions and Hints
• You can assume the user inputs are always non-negative integers bounded by 1000. There is no
need to validate the inputs against values that go beyond this assumption, e.g. "abc", "@#&",
99.9, -1, 1001, 9,999,999, etc.
• To achieve the right alignment stated above, you can make use of a standard library’s function
setw(…). To use it, you have to add #include at your program’s beginning.
• Suppose the field width for the state counter is set to 2. In case the player keeps playing the
game for so many rounds such that the state counter exceeds 2 digits, the output of the rest is
simply shifted to the right accordingly. See the example below:
...
State 99: [3m, 3c]v ~~~ [0m, 0c]
Enter #m #c aboard boat: 1 1
State 100: [2m, 2c] ~~~ v[1m, 1c]
Enter #m #c aboard boat: 1 1
State 101: [3m, 3c]v ~~~ [0m, 0c]
...
2 digits 1 digit
3 digits 2 digits 2 digits
5 digits 4 digits 3 digits
1 digit 1 digit
4 digits 3 digits
Left bank River Right bank
CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 4 of 5
• To know the number of digits of a number, you may use any working method except for third
party API, e.g. counting with a loop, or converting into a string and get the string’s length.
Sample Runs
In the following sample runs, the blue text is user input and the other text is the program printout.
You can try the provided sample program for other input. Your program output should be exactly the
same as the sample program (same text, symbols, letter case, spacings, etc.). Note that there is a
space after the ‘:’ in the program printout.
Sample Run #1:
Enter boat capacity: 2↵
Enter #missionaries: 3↵
Enter #cannibals: 3↵
State 1: [3m, 3c]v ~~~ [0m, 0c]
Enter #m #c aboard boat: 1 1↵
State 2: [2m, 2c] ~~~ v[1m, 1c]
Enter #m #c aboard boat: 1 0↵
State 3: [3m, 2c]v ~~~ [0m, 1c]
Enter #m #c aboard boat: 0 2↵
State 4: [3m, 0c] ~~~ v[0m, 3c]
Enter #m #c aboard boat: 0 1↵
State 5: [3m, 1c]v ~~~ [0m, 2c]
Enter #m #c aboard boat: 2 0↵
State 6: [1m, 1c] ~~~ v[2m, 2c]
Enter #m #c aboard boat: 1 1↵
State 7: [2m, 2c]v ~~~ [1m, 1c]
Enter #m #c aboard boat: 2 0↵
State 8: [0m, 2c] ~~~ v[3m, 1c]
Enter #m #c aboard boat: 0 1↵
State 9: [0m, 3c]v ~~~ [3m, 0c]
Enter #m #c aboard boat: 0 2↵
State 10: [0m, 1c] ~~~ v[3m, 2c]
Enter #m #c aboard boat: 0 1↵
State 11: [0m, 2c]v ~~~ [3m, 1c]
Enter #m #c aboard boat: 0 2↵
State 12: [0m, 0c] ~~~ v[3m, 3c]
Congratulations! You win!
Sample Run #2:
Enter boat capacity: 1↵
Enter #missionaries: 2↵
Enter #cannibals: 2↵
Invalid input!
Enter boat capacity: 2↵
Enter #missionaries: 5↵
Enter #cannibals: 5↵
Invalid input!
CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 5 of 5
Enter boat capacity: 2↵
Enter #missionaries: 2↵
Enter #cannibals: 3↵
Invalid input!
Enter boat capacity: 3↵
Enter #missionaries: 6↵
Enter #cannibals: 6↵
Invalid input!
Enter boat capacity: 4↵
Enter #missionaries: 100↵
Enter #cannibals: 99↵
State 1: [100m, 99c]v ~~~ [ 0m, 0c]
Enter #m #c aboard boat: 3 2↵
Invalid input!
Enter #m #c aboard boat: 1 3↵
Invalid input!
Enter #m #c aboard boat: 0 4↵
State 2: [100m, 95c] ~~~ v[ 0m, 4c]
Enter #m #c aboard boat: 0 5↵
Invalid input!
Enter #m #c aboard boat: 1 0↵
Invalid input!
Enter #m #c aboard boat: 0 1↵
State 3: [100m, 96c]v ~~~ [ 0m, 3c]
Enter #m #c aboard boat: 4 0↵
State 4: [ 96m, 96c] ~~~ v[ 4m, 3c]
Enter #m #c aboard boat: 1 2↵
Invalid input!
Enter #m #c aboard boat: 0 2↵
State 5: [ 96m, 98c]v ~~~ [ 4m, 1c]
Game over! Missionaries eaten!
• There are many combinations of possible inputs. Please check your program correctness against
the results produced by our sample program executable posted on Blackboard.
Submission and Marking
• Your program source file name should be rowboat.cpp. Submit the file in Blackboard
(https://blackboard.cuhk.edu.hk/).
• Insert your name, student ID, and e-mail as comments at the beginning of your source file.
• You can submit your assignment multiple times. Only the latest submission counts.
• Your program should be free of compilation errors and warnings.
• Your program should include suitable comments as documentation.
• Do NOT plagiarize. Sending your work to others is subject to the same penalty for copying work.
Department of Computer Science and Engineering,
Assignment 2: Missionaries and cannibals problem
Due: 20:00, Thu 8 Oct 2020 File name: rowboat.cpp Full marks: 100
Introduction
The objective of this assignment is to let you practice the use of variables, operators, expressions,
standard input/output and control flow in C++. You are to write a program to simulate a game based
on a classic river-crossing puzzle known as the “missionaries and cannibals” (“M&C”) problem.
In a classical setting of the puzzle, three missionaries and three cannibals are on one bank of a river.
There is one boat available that can carry at most two people. They would use it to cross the river. If
the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will
get eaten! The boat cannot cross the river by itself with no people on board. Under these constraints,
how can the boat be used to safely carry all the missionaries and cannibals across the river?
This problem is commonly turned into a game. You may play this game online on this website
(Adobe Flash required) and watch a YouTube video showing the solution.
In this assignment, you are to write a similar game program which is played via the console instead
of a graphical user interface. As another difference, we would generalize the problem. That means
the program should let the user input the number of missionaries, cannibals and the boat capacity at
the beginning. The program then repeatedly prompts the user for how many missionaries and/or
cannibals to get on the boat. It will check if the input numbers are valid under the above constraint
and show the current game state. The aim of the program is not about implementing any solution
search algorithm to solve the puzzle (which is beyond our scope) but simply supporting the user to
play the game.
Assume that all people are on the left bank initially. The current game state can be represented by a
simple vector ⟨m, c, b⟩ where m and c denote the counts of missionaries and cannibals on the left
bank respectively, and b equals 1 or 0 represents whether the boat is on the left or on the right bank,
respectively. So, the game starts with the initial state vector ⟨3, 3, 1⟩. To win the game, we need to
take successive boat trips to advance the game state towards the goal state ⟨0, 0, 0⟩, which means
that all the people and the boat are not on the left bank. They have all crossed the river!
For convenience of discussion, let us also denote a specific M&C problem in a tuple format (M, C, B)
where M and C refer to the number of missionaries and cannibals respectively, and B represents the
boat capacity. Some M&C problems have no solutions. For example, (M, C, 1) for any non-zero M, C
has no solution since the man rowing the boat that can carry only one man is doomed to returning
to the left bank with the boat or else the others can never cross the river. So, B must not be < 2.
Unless M > C, for problems with B = 2, M and C must be <= 3; for problems with B = 3, M and C must
be <= 5 or else they have no solution. For problems with B >= 4, there is no known bound on M and
C for solution existence. Of course, M must always be >= C in a valid problem.
CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 2 of 5
The following table depicts a solution to the (3, 3, 2) M&C problem. Each row shows the number of
missionaries (m) and cannibals (c) on either bank and the state transition after each boat trip (the
letter v denotes the boat which is on the left bank whenever b = 1 in the state vector).
Trip/State No. Left Bank River Right Bank State
1 m m m c c c v ⟨3, 3, 1⟩
2 m m m c → v c c ⟨3, 1, 0⟩
3 m m m c c v ← c ⟨3, 2, 1⟩
4 m m m → v c c c ⟨3, 0, 0⟩
5 m m m c v ← c c ⟨3, 1, 1⟩
6 m c → v m m c c ⟨1, 1, 0⟩
7 m m c c v ← m c ⟨2, 2, 1⟩
8 c c → v m m m c ⟨0, 2, 0⟩
9 c c c v ← m m m ⟨0, 3, 1⟩
10 c → v m m m c c ⟨0, 1, 0⟩
11 c c v ← m m m c ⟨0, 2, 1⟩
12 → v m m m c c c ⟨0, 0, 0⟩
Recall that in the vector ⟨m, c, b⟩, m and c denote the number of missionaries and cannibals on the
left bank. In other words, M - m and C - c denote the number of missionaries and cannibals on the
right bank. You win the game upon reaching the state ⟨0, 0, 0⟩ whereas you lose the game whenever
the missionaries on either bank are outnumbered by the cannibals there, i.e. m < c or M - m < C – c
for non-zero m and M - m.
Program Specification
The program should obtain three numbers as user input which control the number of missionaries
(M), the number of cannibals (C) and the boat capacity (B) at the beginning. These numbers have to
be validated against the criteria stated on p.1 to ensure that the game will have a solution before the
game gets started. Also, M and C must be >= 1 to be meaningful.
Then it starts a loop to prompt the user to enter two numbers, namely mb and cb, which represent
the number of missionaries and cannibals to get on the boat. The sum of mb and cb is bounded by B
and is at least 1 (at least one is needed for rowing the boat). Also, mb must be >= cb for missionaries
aboard not to be eaten. Of course, mb and cb cannot exceed the number of available missionaries
and cannibals on the bank concerned. Your program must check against these to assure a valid boat
trip. If any condition stated here is violated, the program will show an error message and prompt the
user for input again until a valid pair of values is obtained.
Upon receiving a valid pair of mb and cb, the program computes the current game state ⟨m, c, b⟩ and
prints the number of missionaries and cannibals on both banks and the boat position to the console
in a specific format (see the Sample Runs section). It will repeat prompting the user for new boat trip
inputs and game state handling until the state becomes ⟨0, 0, 0⟩ or the game losing condition
stated above is met, i.e. some missionaries get eaten! A game winning or losing message should
be printed accordingly.
CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 3 of 5
Output Formatting Requirements
In the Sample Runs section, please note that there are some formatting requirements your program
must follow. To display the game statistics neatly, the state, missionary and cannibal counts on
either bank are all right aligned, each in a fixed width that is set in the following manner. Suppose
that M has x digits, and C has y digits. The field widths for the number of missionaries and cannibals
on both banks will be set to x and y respectively. The field width for the state counter will be set as
maximum(x, y) + 1. Padding is added to the left of those values with # digits < the field width. Also,
there is a single space after the word “State” and every comma. See the following examples.
For M = 3, C = 3, the initial state is displayed as:
State 1: [3m, 3c]v ~~~ [0m, 0c]
For M = 30, C = 9, the initial state is displayed as:
State 1: [30m, 9c]v ~~~ [ 0m, 0c]
For M = 1000, C = 999, the initial state is displayed as:
State 1: [1000m, 999c]v ~~~ [ 0m, 0c]
A pair of square brackets is used to enclose each of the two banks. The boat is denoted by a letter v.
The river is represented by 6 characters – two spaces, then three ~ symbols, and then two spaces,
but with the leftmost or rightmost space replaced by the boat symbol v, depending on which bank
the boat is located.
Assumptions and Hints
• You can assume the user inputs are always non-negative integers bounded by 1000. There is no
need to validate the inputs against values that go beyond this assumption, e.g. "abc", "@#&",
99.9, -1, 1001, 9,999,999, etc.
• To achieve the right alignment stated above, you can make use of a standard library’s function
setw(…). To use it, you have to add #include
• Suppose the field width for the state counter is set to 2. In case the player keeps playing the
game for so many rounds such that the state counter exceeds 2 digits, the output of the rest is
simply shifted to the right accordingly. See the example below:
...
State 99: [3m, 3c]v ~~~ [0m, 0c]
Enter #m #c aboard boat: 1 1
State 100: [2m, 2c] ~~~ v[1m, 1c]
Enter #m #c aboard boat: 1 1
State 101: [3m, 3c]v ~~~ [0m, 0c]
...
2 digits 1 digit
3 digits 2 digits 2 digits
5 digits 4 digits 3 digits
1 digit 1 digit
4 digits 3 digits
Left bank River Right bank
CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 4 of 5
• To know the number of digits of a number, you may use any working method except for third
party API, e.g. counting with a loop, or converting into a string and get the string’s length.
Sample Runs
In the following sample runs, the blue text is user input and the other text is the program printout.
You can try the provided sample program for other input. Your program output should be exactly the
same as the sample program (same text, symbols, letter case, spacings, etc.). Note that there is a
space after the ‘:’ in the program printout.
Sample Run #1:
Enter boat capacity: 2↵
Enter #missionaries: 3↵
Enter #cannibals: 3↵
State 1: [3m, 3c]v ~~~ [0m, 0c]
Enter #m #c aboard boat: 1 1↵
State 2: [2m, 2c] ~~~ v[1m, 1c]
Enter #m #c aboard boat: 1 0↵
State 3: [3m, 2c]v ~~~ [0m, 1c]
Enter #m #c aboard boat: 0 2↵
State 4: [3m, 0c] ~~~ v[0m, 3c]
Enter #m #c aboard boat: 0 1↵
State 5: [3m, 1c]v ~~~ [0m, 2c]
Enter #m #c aboard boat: 2 0↵
State 6: [1m, 1c] ~~~ v[2m, 2c]
Enter #m #c aboard boat: 1 1↵
State 7: [2m, 2c]v ~~~ [1m, 1c]
Enter #m #c aboard boat: 2 0↵
State 8: [0m, 2c] ~~~ v[3m, 1c]
Enter #m #c aboard boat: 0 1↵
State 9: [0m, 3c]v ~~~ [3m, 0c]
Enter #m #c aboard boat: 0 2↵
State 10: [0m, 1c] ~~~ v[3m, 2c]
Enter #m #c aboard boat: 0 1↵
State 11: [0m, 2c]v ~~~ [3m, 1c]
Enter #m #c aboard boat: 0 2↵
State 12: [0m, 0c] ~~~ v[3m, 3c]
Congratulations! You win!
Sample Run #2:
Enter boat capacity: 1↵
Enter #missionaries: 2↵
Enter #cannibals: 2↵
Invalid input!
Enter boat capacity: 2↵
Enter #missionaries: 5↵
Enter #cannibals: 5↵
Invalid input!
CSCI1120 Introduction to Computing Using C++, Fall 2020/21
Department of Computer Science and Engineering, The Chinese University of Hong Kong
Copyright © 2020 CSE, CUHK Page 5 of 5
Enter boat capacity: 2↵
Enter #missionaries: 2↵
Enter #cannibals: 3↵
Invalid input!
Enter boat capacity: 3↵
Enter #missionaries: 6↵
Enter #cannibals: 6↵
Invalid input!
Enter boat capacity: 4↵
Enter #missionaries: 100↵
Enter #cannibals: 99↵
State 1: [100m, 99c]v ~~~ [ 0m, 0c]
Enter #m #c aboard boat: 3 2↵
Invalid input!
Enter #m #c aboard boat: 1 3↵
Invalid input!
Enter #m #c aboard boat: 0 4↵
State 2: [100m, 95c] ~~~ v[ 0m, 4c]
Enter #m #c aboard boat: 0 5↵
Invalid input!
Enter #m #c aboard boat: 1 0↵
Invalid input!
Enter #m #c aboard boat: 0 1↵
State 3: [100m, 96c]v ~~~ [ 0m, 3c]
Enter #m #c aboard boat: 4 0↵
State 4: [ 96m, 96c] ~~~ v[ 4m, 3c]
Enter #m #c aboard boat: 1 2↵
Invalid input!
Enter #m #c aboard boat: 0 2↵
State 5: [ 96m, 98c]v ~~~ [ 4m, 1c]
Game over! Missionaries eaten!
• There are many combinations of possible inputs. Please check your program correctness against
the results produced by our sample program executable posted on Blackboard.
Submission and Marking
• Your program source file name should be rowboat.cpp. Submit the file in Blackboard
(https://blackboard.cuhk.edu.hk/).
• Insert your name, student ID, and e-mail as comments at the beginning of your source file.
• You can submit your assignment multiple times. Only the latest submission counts.
• Your program should be free of compilation errors and warnings.
• Your program should include suitable comments as documentation.
• Do NOT plagiarize. Sending your work to others is subject to the same penalty for copying work.