首页 >
> 详细

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

• 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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28