顾名思义，直叙式模拟就是按照试题要求展开模拟过程。虽然不需要什么精妙算法，但编程者一定要忠实于原题，认真审题，千万不要疏漏任何条件，精心设计方便模拟的数据结构。“直叙式模拟”的难度取决于模拟对象所包含的动态变化的属性有多少，动态属性愈多，则难度愈大。直叙式模拟的形式一般有两种：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)&按照上述规则，依次解密密码文件中的大写字母，即可得到原文。程序清单
#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() ;// 处理每条指令，输出游戏结果 } } 相关资源：算法第四版-PDF-网盘链接