Ｉｎｓｔｒｕｃｔｉｏｎｓ问题算法分析.docVIP

Ｉｎｓｔｒｕｃｔｉｏｎｓ问题算法分析 　　摘要：ACM/ICPC（ACM International Collegiate Programming Contest）是ACM国际大学生程序设计竞赛的简称，这是世界计算机领域的一项权威赛事。该文就是针对ACM国际大学生程序设计中的一道题目的解法进行算法分析，道题目的名字叫做“Instructions”。通过对原问题进行理解，通过暴力方法，动态递推法，对原问题进行算法分析和实现，然后对算法进行测试和总结，从而满足题目的要求。 　　关键词：Instructions；算法； 暴力方法；动态递推法 　　中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)22-686-02 　　Algorithm Analysis of the Problem Instructions 　　MA Biao-biao 　　(College of Mathematical Sciences, Anhui University,Hefei 230601,China) 　　Abstract: ACM/ICPC is the abbreviation of ACM International Collegiate Programming Contest. This is authoritative match in the field of computer. This article aims to analyze the algorithm of a problem ofACM/ICPC. The name of this problem is Instructions. Through a detailed understanding, violent means and the method of dynamic recurrence, we analyze, realize and test the original algorithm such that our algorithm meet the requirement of the problem. 　　Key words: Instructions; algorithm; forcible method; the method of dynamical recurrence 　　1 问题提出 　　1.1 题意分析 　　题目的大意是这样的，一台老的探测机器人，它的任务是对一块土地进行探测，包括了四条指令，分别为“Forward”,“ Turn Left”,“ Turn Right”,“Scan”当输入指令为“Forward”时则机器人向它所面向的方向前进一格；当输入指令为“Turn Left”时，则机器人在原地向左转向；当输入指令为“Turn Right”时，则机器人在原地向右转向；当输入指令为“Scan”时，则机器人探测它所面向的方向的前一块区域。 　　现在有一台新的机器人代替老的机器人要完成相同的任务，但是它只有两条指令，为“Move”，“Scan”，移动指令可以让机器人朝它所在位置的任何一个方向移动任何的距离，探测指令则可以让机器人探测它四周的任何一块区域。问题是当新的机器人代替老机器人时，如何让转换它们之间的命令。 　　题目的输出要求是找出旧的指令转换成新的指令后，新指令最少有多少条。并且机器人要求站在同一起点，探测位置和顺序都不能变。 　　题意如图1所示： 　　■ 　　图1 　　图中，数字表示老的机器人走过的路线，红色的*表示探测的区域，红色的数字表示探测的顺序，可以看出，老的机器人如果要完成上面的命令，要执行8条指令，分别为ForwardForwardTurn LeftForwardScanTurnRight ScanForward，如果是新的机器人完成，则只关心起点位置和探测位置及探测顺序，要完成上面的任务有许多种走法，我们要做的就是找出使得新的指令最少的那种方法，根据图1，我们不难看出，当新机器人在图中#位置进行探测时，所需要的指令都是4条，分别为Move Forward 2 Move Left 1 Scan ForwardScan Right 。探测的区域最多有1000组，并且有10次输入。 　　1.2 问题模型 　　根据上面的问题分析，我们可以总结出该问题的问题模型：有最多1000组数据，按顺序记录了探测点的位置，我们假设则每个位置可以直接探测的站位为探测点的上、下、左、右。根据描述，我们可以记录各个站位的坐标，然后把每个站位到后一站位（包括探测过程）所需要的步骤相加，则最后得出到各个站位，探测完成所需要的总步数的所有可能。如图2所示。 　　2 算法分析 　　2.1