回复：（野比）[全民编程]76道高难度C++练习题.含NOI竞...
/*---------------------------------------------------------------------------
File name: C76-33.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com)
Created on: 7/3/2007 17:18:43
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762
Modification history:
===========================================================================
Problem statement:
---------------------------------------------------------------------------
经典 76 道编程题 之 33:
33. ( 野人与传教士 ) 设有三个传教士和三个野人来到河边，打算乘一只船从右
岸渡到左岸去。该船最大负载能力为两人，在任何时候，如果野人人数超过传教士
人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过
河去呢？
Analysis:
---------------------------------------------------------------------------
c --- 传教士
y --- 野人
r --- right bank
l --- left bank
b --- boat
The first time we have 1 c and 1 y on the boat and drop the y, let the c come
back to pick up another y;
from 2nd time, 1 y is always on the boat (i.e., either 1y 1c on the boat or 2y
on the boat) and let y do the transfer job.
...
Repeat until all is done. (the last few steps are a little bit different.)
Totally times to use the boat is 4*n-3.
Sample output:
---------------------------------------------------------------------------
Please input number of barbarians n (n>0): 7
# right bank boat left bank
-------------------------------------------------
0 c (7), y (7)
1 c (6), y (6) cy-->
2 c (6), y (6) <--c* y (1)
3 c (6), y (5) cy--> y (1)
4 c (6), y (5) <--y* c (1), y (1)
5 c (5), y (5) cy--> c (1), y (1)
6 c (5), y (5) <--y* c (2), y (1)
7 c (5), y (4) cy--> c (1), y (2)
8 c (5), y (4) <--y* c (2), y (2)
9 c (4), y (4) cy--> c (2), y (2)
10 c (4), y (4) <--y* c (3), y (2)
11 c (4), y (3) cy--> c (2), y (3)
12 c (4), y (3) <--y* c (3), y (3)
13 c (3), y (3) cy--> c (3), y (3)
14 c (3), y (3) <--y* c (4), y (3)
15 c (3), y (2) cy--> c (3), y (4)
16 c (3), y (2) <--y* c (4), y (4)
17 c (2), y (2) cy--> c (4), y (4)
18 c (2), y (2) <--y* c (5), y (4)
19 c (2), y (1) cy--> c (4), y (5)
20 c (2), y (1) <--y* c (5), y (5)
21 c (1), y (1) cy--> c (5), y (5)
22 c (1), y (1) <--y* c (6), y (5)
23 y (1) yc--> c (6), y (5)
24 y (1) <--y* c (7), y (5)
25 yy--> c (7), y (5)
26 c (7), y (7)
Press any key to continue . . .
Reference:
---------------------------------------------------------------------------
1. 野比, [全民编程]76道高难度C++练习题
http://bbs.bc-cn.net/viewthread.php?tid=147967
*/
#include <iostream>
#include <string>
#include <iomanip>
#include <sstream>
using namespace std;
/**
The travel plan.
-->yc going from right bank to left bank
(1 y and 1 c are on the boat)
<--y* going from right bank to left bank
(1 y is on the boat, another seat on the boat is empty.
* --- represents an empty seat.)
@param n --- number of 野人
Totally, we need to use the boat 4*n-3 times, n>=1.
*/
int travel(int n);
/**
Print the status of right bank, boat, and the left left bank.
@param rc --- number of 传教士 on right bank
@param ry --- number of 野人 on right bank
@param b --- tells you who is on the boat
@param lc --- number of 传教士 on left bank
@param ly --- number of 野人 on left bank
*/
void print(int rc, int ry, string b, int lc, int ly, int counter);
int main()
{
int n;
cout<<"Please input number of barbarians n (n>0): ";
cin>>n;
travel(n);
return 0;
}
int travel(int n)
{
int rc = n;
int ry = n;
string b;
int lc = 0;
int ly = 0;
int i;
int counter = 0;
string rightBank;
string leftBank;
stringstream oss;
cout<<"# right bank boat left bank\n";
cout<<"-------------------------------------------------\n";
print(rc, ry, " ", lc, ly, counter);
if(n==1) // n = 1 is a special case
{
++counter;
print(0, 0, "cy-->", 0, 0, counter);
++counter;
print(n-1, n-1, " ", 1, 1, counter);
return 1;
}
// first few steps
++counter;
print(n-1, n-1, "cy-->", 0, 0, counter);
++counter;
print(n-1, n-1, "<--c*", 0, 1, counter);
// middle steps
for(i=1; i<=n-2; ++i)
{
++counter;
print(n-i, n-i-1, "cy-->", i-1, i, counter);
++counter;
print(n-i, n-i-1, "<--y*", i, i, counter);
++counter;
print(n-i-1, n-i-1, "cy-->", i, i, counter);
++counter;
print(n-i-1, n-i-1, "<--y*", i+1, i, counter);
}
// final steps
++counter;
print(0, 1, "yc-->", n-1, n-2, counter);
++counter;
print(0, 1, "<--y*", n, n-2, counter);
++counter;
print(0, 0, "yy-->", n, n-2, counter);
++counter;
print(0, 0, " ", n, n, counter);
return counter-1;
}
void print(int rc, int ry, string b, int lc, int ly, int counter)
{
ostringstream oss;
string rightBank;
string leftBank;
cout<<std::left<<setw(4)<<counter<<setw(20);
if(rc >0)
{
oss<<"c (";
oss<<rc;
oss<<"), ";
}
if(ry > 0)
{
oss<<"y (";
oss<<ry;
oss<<")";
rightBank = oss.str();
cout<<rightBank;
}
if(ry + rc == 0)
{
cout<<" ";
}
cout<<setw(7)<<b;
oss.str("");
if(lc >0)
{
oss<<"c (";
oss<<lc;
oss<<"), ";
}
if(ly > 0)
{
oss<<"y (";
oss<<ly;
oss<<")";
leftBank = oss.str();
cout<<leftBank;
}
cout<<endl;
}
程序代码：