模拟算法

模拟算法山东省广饶一中杨庆礼火柴棍的世界简单聊聊经典例题什么是模拟官方定义形式浅谈方法模拟级数求和30secondslater采用模拟法，直接用循环模拟这个乘法式子初始sn=0，n=0，然后每次循环n:=n+1Sn:=sn+1/n，直到sn大于k，最后输出n已知sn=1+1/2+1/3+…+1/n。对于任意一个整数k，当n足够大的时候，sn大于k，现在给出一个整数k（1=k=15）计算出一个最小的n，使得snk桌子上放着60根火柴甲、乙二人轮流每次取走1～3根规定谁取走最后一根火柴谁获胜如果双方都采用最佳方法甲先取，那么谁将获胜？改为“每次取走1～6根”其余不变情形会怎样？改为“谁取走最后一根火柴谁输”，其余不变，情形又将如何？今有两堆火柴，一堆35根，另一堆24根两人轮流在其中任一堆中拿取取的根数不限，但不能不取规定取得最后一根者为赢问：先取者有何策略能获胜本题虽然也是取火柴问题但由于火柴的堆数多于一堆故本题的获胜策略与前面的例题完全不同。先取者在35根一堆火柴中取11根火柴，使得取后剩下两堆的火柴数相同。以后无论对手在某一堆取几根火柴，你只须在另一堆也取同样多根火柴。只要对手有火柴可取，你也有火柴可取，也就是说，最后一根火柴总会被你拿到。这样先取者总可获胜。2minlater两人从1开始按自然数顺序轮流依次报数每人每次只能报1～5个数谁先报到50谁胜你选择先报数还是后报数怎样才能获胜？1111个空格排成一行最左端空格中放有一枚棋子甲先乙后轮流向右移动棋子每次移动1～7格规定将棋子移到最后一格者输甲为了获胜第一步必须向右移多少格？•1.桌上有30根火柴，两人轮流从中拿取，规定每人每次可取1～3根，且取最后一根者为赢。问：先取者如何拿才能保证获胜？•2.有1999个球，甲、乙两人轮流取球，每人每次至少取一个，最多取5个，取到最后一个球的人为输。如果甲先取，那么谁将获胜？•3.甲、乙二人轮流报数，甲先乙后，每次每人报1～4个数，谁报到第888个数谁胜。谁将获胜？怎样获胜？•4.有两堆枚数相等的棋子，甲、乙两人轮流在其中任意一堆里取，取的枚数不限，但不能不取，谁取到最后一枚棋子谁获胜。如果甲后取，那么他一定能获胜吗？•5.黑板上写着一排相连的自然数1，2，3，…，51。甲、乙两人轮流划掉连续的3个数。规定在谁划过之后另一人再也划不成了，谁就算取胜。问：甲有必胜的策略吗？•6.有三行棋子，分别有1，2，4枚棋子，两人轮流取，每人每次只能在同一行中至少取走1枚棋子，谁取走最后一枚棋子谁胜。问：要想获胜是先取还是后取？不高兴的津津无线网络发射器选址津津的储蓄计划乒乓球模拟？•模拟城市？•模拟人生？•模拟开火车？•模拟战争？•NO!NO!NO!•模拟算法模拟算法•当大家在谈论DP,DFS,SPFA的时候，模拟算法对于NOIP真的有用吗？•模拟算法的时间复杂度，空间复杂度，代码复杂度高吗？可以放心使用吗？•{没见过猪跑还没听过猪叫唤吗？}•你可以不知道计算机的门电路和工作原理（当然你最好知道），你可以不知道位运算和字符存储规则（当然你最好知道），但作为一个CodeMonkey，你至少应该知道你编写的程序是怎样被执行的。BACK模拟算法在自然界和日常生活中，许多现象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。BACK模拟的方法其实，模拟算法也就是将整个过程完完整整的走一遍。题目怎么叙述的，程序就怎么运行。所以模拟题对算法设计的要求不高，但是需要大家选择最适当的数据结构来进行模拟。BACK模拟题的形式⑴随机模拟：题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素；⑵过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。BACK例3：不高兴的津津津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且，上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。Input输入包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。Output输出包括一行，这一行只包含一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1,2,3,4,5,6,7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。SampleInput53627253540406SampleOutput3算法解析：采用模拟。当天不高兴程度=当天上午不高兴程度+当天下午不高兴程度注意：1.要求的是哪一天最不高兴2.不高兴程度8才算不高兴3.在不高兴的数据中取程度最高的，若存在多个就取靠前的天数4.若没有一天达到不高兴的条件则输出0BACK例4：乒乓球国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。【问题描述】华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果（截至记录末尾）。比如现在有这么一份记录，（其中W表示华华获得一分，L表示华华对手获得一分）：分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果是华华第一局21比0获胜，正在进行第二局，比分2比1。如果一局比赛刚开始，则此时比分为0比0。你的程序就是要对于一系列比赛信息的输入（WL形式），输出正确的结果。【输入格式】每个输入文件包含若干行字符串（每行至多20个字母），字符串有大写的W、L和E组成。其中E表示比赛信息结束，程序应该忽略E之后的所有内容。【输出格式】输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是11分制下的结果，第二部分是21分制下的结果，两部分之间由一个空行分隔。【样例输入】【样例输出】11:011:01:121:02:1解析：此题是一个字符串处理的简单题，但是简单题并不是随随便便就能拿到分的，解决此题首先要解决的问题是题意的理解上，很多同学初一看此题，把一局谁拿到11分或21分就作为此局的胜利，如果这样就犯了一个大错，此题没有在题目里明确说明，但是根据兵乓球的比赛规则是，除了要期中一位选手要达到局分外还要两名选手的分差要在2分或两分以上，这是其一，还有要对数据要有充分的分析，要考虑到特殊情况，此题的特殊情况就是，如果输入的第一个字符就是‘E’，那输出的结果应该是0:0，解决了以上问题，下面的实现虽然有点麻烦，但是仔细点应该问题就不大了.BACK例5：津津的储蓄计划（save.pas）。【题目描述】津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%利息、连本带息还给津津。因此，津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。例如，11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月末，津津手中会剩下3元钱。津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存在她那里的钱加上20%的利息，一并还给津津之后，津津手中会有多少钱。•【输入】•输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。•【输出】•输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】29023028020030017033050908020060【样例输出2】1580【算法分析】最简单、最基本的模拟加判断，连数组都不用开。只要读清题目，然后动手做就可以了。解决此类问题没有什么技巧，最重要的是不在关键时刻出现低级错误。BACK无线网络发射器选址•随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。假设该城市的布局为由严格平行的129条东西向街道和129条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值1。东西向街道从北到南依次编号为0,1,2…128,南北向街道从西到东依次编号为0,1,2…128。东西向街道和南北向街道相交形成路口，规定编号为x的南北向街道和编号为y的东西向街道形成的路口的坐标是（x,y）。在某些路口存在一定数量的公共场所。由于政府财政问题，只能安装一个大型无线网络发射器。该无线网络发射器的传播范围一个以该点为中心，边长为2*d的正方形。传播范围包括正方形边界。现在政府有关部门准备安装一个传播参数为d的无线网络发射器，希望你帮助他们在城市内找出合适的安装地点，使得覆盖的公共场所最多。•输入输出格式•输入格式：•输入文件名为wireless.in。第一行包含一个整数d，表示无线网络发射器的传播距离。第二行包含一个整数n，表示有公共场所的路口数目。接下来n行，每行给出三个整数x,y,k,中间用一个空格隔开，分别代表路口的坐标(x,y)以及该路口公共场所的数量。同一坐标只会给出一次。•输出格式：•输出文件名为wireless.out。输出一行，包含两个整数，用一个空格隔开，分别表示能覆盖最多公共场所的安装地点方案数，以及能覆盖的最多公共场所的数量。•输入输出样例•输入样例#1：1244106620输出样例#1：130•说明•对于100%的数据，1≤d≤20，1≤n≤200≤x≤128,0≤y≤128,0k≤1,000,000。•BACK分析与解本题采用逆推法分析。获胜方在最后一次取走最后一根；往前逆推，在倒数第二次取时，必须留给对方4根，此时无论对方取1，2或3根，获胜方都可以取走最后一根；再