《算法设计编程实验：大学程序设计课程与竞赛训练教材》——2.1　直叙式模拟的实验范例

2.1　直叙式模拟的实验范例

顾名思义，直叙式模拟就是按照试题要求展开模拟过程。虽然不需要什么精妙算法，但编程者一定要忠实于原题，认真审题，千万不要疏漏任何条件，精心设计方便模拟的数据结构。“直叙式模拟”的难度取决于模拟对象所包含的动态变化的属性有多少，动态属性愈多，则难度愈大。直叙式模拟的形式一般有两种：
1）按指令行事，一般采用命令序列分析法。
2）按时间顺序模拟，一般采用时间序列分析法。
下面，我们举三个有趣的实例。
【2.1.1　The Hardest Problem Ever】
【问题描述】
凯撒大帝（Julius Caesar）生活在充满了危险和阴谋的年代，他要面临在最困难的情况下让自己生存下来的问题。为了能够生存，他创建了第一套密码。这个密码听起来是如此的令人难以置信，以至于没有人能弄清楚它是如何工作的。
你是凯撒军队中的一名下级军官。你的工作是破译凯撒发来的邮件，并报告给你的将军。凯撒加密的方法很简单。对于原文中的每一个字母，用这个字母之后的第五个字母来替换（即如果原文的字母是“A”，则要替换为密码字母“F”）。因为你要把凯撒的邮件翻译为原文文件，所以你要做相反的事情（将密码转换为原文）：
密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
在密码文件中只有字母才被替换，其他的非字母字符保持不变，所有的英文字母为大写。
输入：
本问题的输入由多达100个（非空的）测试用例组成。每个测试用例格式如下描述，在测试用例之间没有空行分开。所有的字符为大写。
一个测试用例由三部分组成：
1）起始行——一行，“START”。
2）密码消息——一行，由100～200个字符组成，包含100和200，表示由凯撒发送来的一条消息。
3）结束行——一行，“END”。
在最后一个测试用例后给出一行，“ENDOFINPUT”。
输出：
对每个测试用例，输出一行，给出凯撒的原始信息。

试题来源：ACM South Central USA 2002
在线测试地址：POJ 1298，ZOJ 1392，UVA 2540
试题解析
显然，这是一道按指令行事的简单直叙式模拟题。按照加密规则，26个大写英文字母依序围成一圈，密码字母逆时针方向上的第5个字母即为原文字母，即原文字母=‘A’+(密码字母-‘A’+21)%26按照上述规则，依次解密密码文件中的大写字母，即可得到原文。
程序清单

#include <iostream>
#include <string>
using namespace std;

int main()
{
string str;　　　　　　　　　　　　　　　　　　// 密码消息
int i;
while (cin >> str)// 输入密码消息
{
cin.ignore(INT_MAX, '＼n');// 忽略该行
if (str == "ENDOFINPUT") break;// 若输入终止标志，则结束程序
getline(cin, str, '＼n');// 将输入流存入str
for (i = 0; i < str.length(); i++)// 依次解密大写字母
if (isalpha(str［i］))
str［i］ = 'A' + (str［i］ - 'A' + 21) % 26;
cout << str << endl;// 输出原始信息
cin >> str;// 输入下一条密码
}
return 0;
}

【2.1.2　Rock-Paper-Scissors Tournament】
【问题描述】
“石头-剪子-布（Rock-Paper-Scissors）”是两个玩家A和B一起玩的游戏，每一方单独选择石头、剪子或布中的任意一项。选择了布的玩家赢选择了石头的玩家，选择了剪子的玩家赢选择了布的玩家，选择了石头的玩家赢选择了剪子的玩家，两个玩家选择相同的项则不分胜败。
有n位选手参加“石头-剪子-布”锦标赛，每位选手与其他每个选手要进行k场“石头-剪子-布”比赛，总共要进行kn(n-1)2场比赛。请计算每个选手的获胜平均数，获胜平均数被定义为ww+l，其中w是选手获胜的场次数，l是选手输掉的场次数。
输入：
输入包含若干测试用例，每个测试用例的第一行给出n,k（1≤n≤100，1≤k≤100），它们的定义如上。对每场比赛，在一行中给出p1,m1,p2,m2，p1和p2（1≤p1≤n且1≤p2≤n）是不同的整数，用于标识两个选手；m1和m2是他们各自的选择(“石头（rock）”、“剪子（scissors）”或“布（paper）”)。在最后一个测试用例之后给出包含0的一行。
输出：
对选手1，选手2，一直到选手n，每个选手输出一行，给出选手的获胜平均数，四舍五入到小数点后3位。如果获胜平均数无法定义，则输出"-"。在两个测试用例之间输出空行。

试题来源：Waterloo local 2005.09.17
在线测试地址：POJ 2654，UVA 10903
试题解析
这也是一道按指令行事的直叙式模拟题，指令即为“布”赢“石头”、“剪子”赢“布”、“石头”赢“剪子”的规则。有n个选手，每个选手需参加k场比赛，因此共有kn(n-1)2场比赛。我们依次输入每场“石头-剪子-布”比赛中一对选手的编号和各自的选择，根据输赢规则，统计每个玩家的输赢场次数（l和w的值）。最后计算每个选手的获胜平均数：
若出现选手输赢的场次数都为0（l+w=0）的情况，则无法定义获胜平均数；否则选手的获胜平均数为ww+l。
程序清单

#include <stdio.h>
#include <string.h>

int w［200］, l［200］;　　　　　　　　　　　　　　　　　// 选手i赢的场次数为w［i］，输的场次数为l［i］
int p1,p2,i,j,k,m,n;// 选手为n，每位选手的比赛场次数为k，测试用例
// 数为m，当前一场比赛的对手为p1和p2
char m1［10］, m2［10］;// 选手p1的当前选择为m1［］；选手p2的当前
// 选择为m2［］

main(){
for (m=0;1<=scanf("%d%d",&n,&k)&& n;m++) {// 输入选手和每位选手的比赛场次数，直至输入0为止
if (m) {
printf("＼n");
memset(w,0,sizeof(w));// 各选手输赢的场次数初始化为0
memset(l,0,sizeof(l));
}
for(i=0; i<k*n*(n-1)/2;i++){// 依次输入每场比赛的一对选手的编号和各自的选择
scanf("%d%s%d%s",&p1,m1,&p2,m2);
if (!strcmp(m1,"rock") && !strcmp(m2,"scissors") ||
!strcmp(m1,"scissors") && !strcmp(m2,"paper") ||
!strcmp(m1,"paper") && !strcmp(m2,"rock")) {
w［p1］++; l［p2］++;// p1赢，p2输，累计p1赢的场次数和p2输的场次数
}
if (!strcmp(m2,"rock") && !strcmp(m1,"scissors") ||
!strcmp(m2,"scissors") && !strcmp(m1,"paper") ||
!strcmp(m2,"paper") && !strcmp(m1,"rock")) {
w［p2］++; l［p1］++;// p2赢，p1输，累计p2赢的场次数和p1输的场次数

}
}
// 计算每位选手的获胜平均数。若出现选手输赢的场次数都为0，则获胜平均数无法定义
for (i=1;i<=n;i++) {
if (w［i］+l［i］) printf("%0.3lf＼n",(double)w［i］/(w［i］+l［i］));
else printf("-＼n");
}
}
if (n) printf("extraneous input! %d＼n",n);
}

【2.1.3　Robocode】
【问题描述】
Robocode是一个帮助你学习Java的教学游戏。玩家编写的程序，控制坦克在战场上互相攻击。这个游戏的思想看似简单，但编写一个获胜坦克的程序还需要很多的努力。本题不要求写一个智能坦克的程序，只要设计一个简化的Robocode游戏引擎。
本题设定整个战场是120*120（像素）。每辆坦克只能沿水平和垂直方向在固定的路径上移动（在战场中的水平和垂直方向路径每10个像素1格，总共有13条垂直路径和13条水平路径坦克可以行走，如图2.1-1所示）。本题忽略坦克的形状和大小，对于一辆坦克，用(x,y)(x,y∈［0,120］)表示它的坐标位置，用α(α∈{0,90,180,270})表示坦克面对的方向（α=0、90、180或270分别表示坦克面向右、上、左或下）。坦克以10像素/秒的恒定速度行驶，不能跑到边界之外（当坦克冲到战场的边界上的时候，就会停止移动，保持当前所面对的方向）。坦克可以向它所面对的方向射击，无论它是在行进还是停止。射击时炮弹以20像素/秒的恒定速度射出，炮弹的大小也被忽略。炮弹在路径上遇上一辆坦克时，就会发生爆炸。如果一发以上的炮弹几乎在同一时刻命中坦克，则可能在同一个地方发生爆炸。被击中的坦克将被销毁，并从战场上被立即移走。爆炸的炮弹或飞出边界的炮弹也将被移走。
当游戏开始的时候，所有的坦克停在垂直和水平路径的不同交叉路口。给出所有坦克的初始信息和若干指令，请找到赢家——在所有的指令被执行（或被忽略）并且在战场上已经没有炮弹的时候（也就是说，接下来没有坦克可能会被击毁），最后生存下来的坦克。
输入：
有若干个测试用例。对所有的测试用例，战场和路径都是一样的。每个测试用例首先给出用一个空格分开的整数N（1≤N≤10）和M（1≤M≤1000），N表示在战场上坦克的数量，M表示控制坦克移动的指令的条数。接下来的N行给出每辆坦克的初始信息（在时间为0时），格式如下：Name x y α一辆坦克的Name由不超过10个字母组成。x、y和α是整数，x，y∈{0,10,20,…,120}，α∈{0,90,180,270}，每个项之间用一个空格分开。
接下来的M行给出指令，格式如下：Time Name Content每个项之间用一个空格分开。按Time的升序给出所有的指令(0≤Time≤30)，Time是一个正整数，表示指令发出的时间戳；Name表示接收指令的坦克；Content的类型如下：

坦克一旦接收到指令，就采取相应的行动。例如，如果一辆坦克位置为（0，0），α=90，在time 1接收到指令MOVE，它就开始移动，在time 2到达位置（0，1）。要注意的是，坦克可以在一秒钟内接收多条指令，一条接一条地根据指令采取相应的行动。例如，如果坦克位置为（0，0），α=90，接收到的指令序列为“TURN 90;SHOOT;TURN-90”，它就转到方向α=180，发射一枚炮弹，然后再转回来。如果坦克接收到“MOVE;STOP”指令序列，它仍然待在原来的位置。
请注意一些要点：
如果一辆坦克被击中爆炸，在那一刻，它对所有收到的指令都不会采取任何行动。当然，所有发送到已经摧毁的坦克的指令也被略去。
虽然指令在确定的时间点发出，但是坦克和炮弹的运动和爆炸发生在连续时间段内。
输入数据保证不会有两辆坦克在路上相撞，因此你的程序不必考虑这种情况。
所有的输入内容是合法的。
以N=M=0的测试用例终止输入，程序不用处理这一情况。
输出：
对每个测试用例，在一行中输出赢家的名字。赢家是最后生存下来的坦克。如果在最后没有坦克了，或者有多于一辆坦克生存下来，则在一行中输出“NO WINNER!”。

试题来源：ACM Beijing 2005
在线测试地址：POJ 2729，UVA 3466
试题解析
很明显，本题是一道时序模拟题，因为指令发出的时间范围为30s。考虑到执行最后一条指令后可能还有变化，所以可以一直模拟到45s后。
如果位于(0,0)位置的坦克朝向(0,1)位置开炮，而位于(0,1)位置的坦克朝向(0,0)位置驶来，那么会在中间13的位置处被击中，同时也可能在12时间出现事故。于是我们将时间和地图都扩大6倍，即等价于原来的图每16秒考虑一次。
坦克和炮弹的属性有四个：位置、方向、行进（或停止）状态、移走（或未移走）状态。
我们从0时刻出发，依次处理每条指令。若当前指令的发出时间为t2，上条指令的发出时间为t1，则先依序模拟t1‥t2时刻的战况，然后根据指令设定受令坦克的状态：
若为MOVE指令，则受令坦克进入行进状态。
若为STOP指令，则受令坦克进入停止状态。
若为SHOOT指令且受令坦克未移走，则新增一发炮弹，除设行进状态外，其他属性与受令坦克相同。
若为TURN angle指令，则受令坦克的方向调整为“原方向数+angle90%4+4%4”。
注：方向数为角度90。
处理完所有指令后，再模拟15s的战况，以处理最后一条指令的后继影响。
最后，统计生存下来的坦克数：若所有坦克移走，或有一辆以上的坦克未移走，则无解；否则赢家为仅存的那辆未移走的坦克。
程序清单

#include <iostream>
#include <map>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <string>
using namespace std ;

const int DirX［4］ = { 10 , 0 , -10 , 0 } ; 　　　　　// 水平增量和垂直增量
const int DirY［4］ = { 0 , 10 , 0 , -10 } ;

#define mp make_pair

int　N , M , Shoot ;// 坦克数为N，指令数为M，N+1‥Shoot为炮弹
int　x［1050］ , y［1050］ , d［1050］ ;// 坦克或炮弹的位置为（x［］，y［］），方向为d［］
bool run［1050］,die［1050］ ;// 坦克的行进标志为run［］，坦克或炮弹的“移走”
// 标志为die［］
string symbol［1050］ ;// 第i辆坦克的名字为symbol［i］

map<string,int> Name ;// 名为s的坦克序号为Name［s］

void　Init()
{
Name.clear() ;
for ( int i = 1 ; i <= N ; i ++ )// 输入每辆坦克的名字、初始位置和移动方向
{
cin >> symbol［i］ >> x［i］ >> y［i］ >> d［i］ ;
x［i］ *= 6 ; y［i］ *= 6 ;d［i］ /= 90 ;// 把地图扩大6倍并计算方向数
run［i］ = false ;die［i］ = false ;// 坦克处于停止和未“移走”状态
Name［symbol［i］］ = i ;// 记下该坦克的序号
}
Shoot = N ;// 开炮的坦克序号初始化
}

bool　In( int x , int y )// 返回（x，y）在界内的标志
{
if ( x >= 0 && x <= 6*120 && y >= 0 && y <= 6*120 ) return true ;
return false ;
}

void　RunAll()// 模拟当前1个时间单位的战况
{
for ( int i = 1 ; i <= N ; i ++ )　　// 搜索每辆行进且未“移走”的坦克。若沿指定方向移动一步
// 仍在界内，则记下移动位置，否则置该坦克“停止”状态
{
if ( run［i］ && !die［i］ )
{
if ( In( x［i］ + DirX［d［i］］ , y［i］ + DirY［d［i］］ ) )
{
x［i］ += DirX［d［i］］ ;y［i］ += DirY［d［i］］ ;
}
else run［i］ = false ;
}
}
for ( int i=N+1 ; i <= Shoot ; i ++ )// 搜索炮弹序列中未“移走”的炮弹i。若炮弹沿
// d［i］方向运行1个时间单位后仍在界内，则记下该位置；否则置炮弹i“移走”状态
{
if ( !die［i］ )
{
if ( In( x［i］ + DirX［d［i］］ *2 , y［i］ + DirY［d［i］］ *2 ) )
{
x［i］ += DirX［d［i］］ *2 ;y［i］ += DirY［d［i］］ *2 ;
}
else die［i］ = true ;
}
}
for ( int i = 1 ; i <= N ; i ++ )// 搜索“未移走”的坦克i
{
if ( die［i］ ) continue ;
for ( int j = N+1 ; j <= Shoot ; j ++ ) if ( !die［j］ )
// 搜索炮弹序列中“未移走”的炮弹j。若炮弹j击中坦克i，则置坦克i和炮弹j“移走”状态
{
if ( x［i］ == x［j］ && y［i］ == y［j］ )
{
die［j］ = true ; die［i］ = true ;
}
}
}
}

void　Solve()// 执行每条指令，输出游戏结果

{
int now = 0 ;// 从时间0开始
for ( int i = 1 ; i <= M ; i ++ )// 输入每条指令发出的时间、受令坦克和指令类别
{
int t ; string sym , s ; int th ;
cin >> t >> sym >> s ;
t *= 6 ;// 时间*6
while ( t > now ) { RunAll() ; now ++ ; }// 模拟now‥t秒的战况
int symId = Name［sym］ ;// 取出受令坦克的序号

if ( s == "MOVE" )// 受令坦克移动
run［symId］ = true ;
else if ( s == "STOP" )// 受令坦克停止
run［symId］ = false ;
else if ( s == "SHOOT" )// 受令坦克开炮
{
if ( !die［symId］ )// 若受令坦克“未移走”，则发出的炮弹进入炮弹序列
{
Shoot ++ ;
run［Shoot］ = true ;die［Shoot］ = false ;
d［Shoot］ = d［symId］ ; x［Shoot］ = x［symId］ ; y［Shoot］ = y［symId］ ;
}
}
Else// 处理改变方向命令
{
cin >> th ; th /= 90 ;// 读改变的角度，重新计算方向数
d［symId］ = (d［symId］ + (th % 4) + 4 ) % 4 ;
}
}
for ( int i = 1 ; i <= 15*6 ; i ++ ) RunAll() ;// 顺序模拟15个时间单位的战况

int cnt = 0 ;// 统计最后生存下来的坦克数cnt
for ( int i = 1 ; i <= N ; i ++ ) if ( !die［i］ ) cnt ++ ;
if ( cnt != 1 ) cout << "NO WINNER!＼n" ;// 若最后没有坦克了，或有多于一辆坦克生存下来，
// 则无解；否则计算赢家（最后生存下来的坦克）
else
{
for ( int i = 1 ; i <= N ; i ++ ) if ( !die［i］ ) cout << symbol［i］ << "＼n" ;
}
}

int　main()
{
while ( cin>>N>>M && ( N || M ) )// 反复输入坦克数和指令数，直至输入两个0为止
{
Init() ;
Solve() ;// 处理每条指令，输出游戏结果
}
}