首页 >
> 详细

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
- 微信：codinghelp

- 代写cmpt 214编程、代做programming语言、代写c/C++程序 2020-11-08
- 代写csci 2122课程、代做program编程实验、C++程序语言代写代 2020-11-08
- Fit5032语言编程代做、代写web程序实验、Web、Html程序语言代做 2020-11-08
- Com3503程序编程代做、Java，C++，Python留学生编程代写代写 2020-11-08
- 代写program程序课程、代写c++编程实验、C/C++编程语言代做 代做 2020-11-08
- Data留学生编程代做、代写python程序、Java，C++程序语言代写 2020-11-08
- 代写secj 1023实验编程、Programming程序代做、代写c++语 2020-11-08
- 代写cmpsc 465编程、代做java程序语言、Python，C++编程设 2020-11-07
- 代做mf 703语言编程、代写programming程序、Sql编程语言调试 2020-11-07
- 954246编程设计调试、代做programming程序、C++编程语言代写 2020-11-07
- Pstat 115程序实验代写、R编程语言调试、Data留学生程序代做 代写 2020-11-07
- Com1005课程编程代做、代写python程序、Java，C++程序语言调 2020-11-07
- Tcp留学生程序代写、Java程序设计调试、Java编程语言代写 帮做r语言 2020-11-07
- 代写program语言编程、代做data留学生程序、Python，Java编 2020-11-07
- 代做cosc2666编程、代写programming程序、C/C++程序语言 2020-11-07
- Digital编程设计代写、代做r程序实验、代写r留学生程序 调试matla 2020-11-07
- 代写programming程序实验、R程序语言调试、Data课程编程代做 代 2020-11-07
- Comp104-17B程序代写、代做c++编程实验、C++程序语言调试 帮做 2020-11-07
- Csc8501课程程序代做、C++编程语言调试、代写program编程课程 2020-11-07
- 代写css3留学生程序、代做html、Css编程语言、Data课程程序代做 2020-11-07