4模拟策略1

模拟策略在自然界和日常生活中，许多现象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟题的形式⑴随机模拟：题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素；⑵过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。模拟的解题方法的类型⑴直叙式模拟⑵筛选法模拟⑶构造法模拟⑴直叙式模拟直叙式模拟即按照试题要求展开模拟过程。编程者要忠实于原题，认真审题，千万不要疏漏任何条件，精心设计方便模拟的数据结构。“直叙式模拟”的难度取决于模拟对象所包含的动态变化的属性有多少，动态属性愈多，则难度愈大。DAM语言有个机器执行一种DASM语言。该机器有一个栈，初始时栈里只有一个元素x，随着DAM语言程序的执行，栈里的元素会发生变化。DAM语言有四种指令：D指令：把栈顶元素复制一次加到栈顶A指令：把栈顶元素取出，加到新的栈顶元素中。M指令：把栈顶元素取出，乘到新的栈顶元素中。如果执行A或M指令的时候栈内只有一个元素，则机器会发出错误信息。如果程序无误，那么执行完毕以后，栈顶元素应该是x的多项式，例如，程序DADDMA的执行情况为（栈内元素按照从底到顶的顺序从左至右排列，用逗号隔开）：xx，x2x2x，2x2x，2x，2x2x，4x24x2+2x给出一段DAM程序，求出执行完毕后栈顶元素。输入输入仅一行，包含一个不空的字符串s，长度不超过12，代表一段DAM程序。输入程序保证合法且不会导致错误。输出仅输出一行，即栈顶多项式。须按照习惯写法降幂输出，即：等于1的系数不要打印，系数为0的项不打印，第一项不打印正号。一次方不打印’^1’。模拟需要注意的问题：⑴多项式的表示方式。有的选手或许会觉得：本题没有说明次数的上限，因此最好用链表做。其实完全没有必要。由于指令不超过12条，而D指令和A，M指令总数应该相等，因此最多有6条M指令，因此次数上限为26=64。我们可以用数组来表示多项式，又方便又不会导致时间和空间上的问题。⑵本题也没有说明系数的最大值。稍微细心的选手发现：它最大可能为232，超过长整数的范围，因此需要采用extended类型，当然，也不存在非得用高精度的必要。{$n+}vardegree：array[1..20]ofinteger；{存储系数个数的栈}co：array[1..20，0..64]ofextended；{存储多项式的栈}tmp：array[0..64]ofextended；{系数序列}I，j，d，a，b，top：integer；{栈顶指针为top}s：string；{Dam程序}first：boolean；begintop←1；{栈顶指针初始化}fillchar(co，sizeof(co)，0)；{存储多项式的栈清零}degree[1]←1；{初始时栈里只有一个元素x}co[1，1]←1；read(s)；{输入Dam程序}forI←1tolength(s)do{依次执行Dam程序中的每一条命令}cases[I]of‘D’：begin{把栈顶元素复制一次加到栈顶}inc(top)；degree[top]←degree[top–1]；forj←0todegree[top]doco[top，j]←co[top–1，j]；end；{‘D’}‘A’：begin{把栈顶元素取出，加到新的栈顶元素中}dec(top)；ifdegree[top]degree[top+1]thendegree[top]←degree[top+1]；forj←0todegree[top]doco[top，j]←co[top，j]+co[top+1，j]；end；{‘A’}‘M’：begin{把栈顶元素取出，乘到新的栈顶元素中}dec(top)；fillchar(tmp，sizeof(tmp)，0)；d←degree[top]+degree[top+1]；fora←0todegree[top]doforb←0todegree[top+1]dotmp[a+b]←tmp[a+b]+co[top，a]*co[top+1，b]degree[top]←d；forj←0toddoco[top，j]←tmp[j]；end；{‘M’}end；{case}first←true；{按照降幂的顺序输出栈顶多项式}forI←degree[top]downto1doifco[top，I]0thenbeginiffirstthenfirst←falseelsewrite(‘+’)；ifabs(co[top，I]–1.0)1e-6thenwrite(co[top，I]：0：0)；write(‘x’)；ifI1thenwrite(‘^’，I)；end；{then}writeln；end.{main}筛选法模拟模拟过程中可能产生的所有解组成一个筛。筛选法模拟即先从题意中找出约束条件，然后将筛中的每一个可能解放到约束条件的过滤器上，一次一次地将不符合条件的解过滤掉，最后沉淀在筛中的即为问题的解。“筛选法模拟”的结构和思路简明、清晰，但带有盲目性，因此时间效率并不一定令人满意。“筛选法模拟”的关键是找准约束条件，任何错误和疏漏都会导致模拟失败。蒙特卡洛法计算定积分其中ab，0f(x)d，输入：abda0a1…ak(表示f(x)=ak*xk+…a1*x+a0)badxxfs)()}({maxxfdbxa产生n(足够大)个均匀分布在长方形abcd上的随机数点(xi，yi)。其中xi—均匀分布在区间[a，b]上的随机数，即xi=a+(b-a)*random(1)；yi—均匀分布在区间[0，d]上的随机数，即yi=d*random(1)；n个随机数点组成一个筛。约束条件的过滤器是某点(xi，yi)是否落在曲边梯形aefb外。如果是（yi≥f(xi)），则该点从筛中过滤掉。最后有m个随机数点留在筛中（这些随机数点落在曲边梯形aefb内）。曲边梯形aefb的面积应该为m和n的比值乘以长方形abcd的面积ndabms*)(*functionf(x)：real；{计算f(x)}beginf(x)←akxk+ak-1kk-1+‥+a1x+a0；end；{f}functionamoncar(a，b，d，n)：real；{计算}beginrandomize；m←0；fori←1tondobeginx←a+(b-a)*random(1)；{产生ki}y←d*random(1)；{产生yi}ifyf(x)thenm←m+1；{若(xi，yI)落入曲边梯形内，则累计其点数}end；{for}amoncar←p/n*(b-a)*d；{返回曲边梯形面积}end；{amoncar}在主程序中，输入随机点的个数n和a，b，d，然后通过调用函数amoncar(a，b，d，n)计算和输出定积分的值。注意，n愈大，定积分的值愈精确，但速度愈慢。badxxfs)(构造法模拟构造法模拟需要完整精确地构造出反映问题本质的数学模型，根据该模型设计状态变化的参数，计算模拟结果。由于数学模型建立了客观事物间准确的运算关系，因此其效率一般比较高。“构造法模拟”的关键是找到数学模型。问题是，能产生正确结果的数学模型并不是唯一的，从不同的思维角度看问题，可以得出不同的数学模型，而模拟效率和编程复杂度往往因数学模型而异。即便有数学模型，但解该模型的准确方法是否有现成算法、编程复杂度如何，这些都是我们要考虑的问题。化学试验安排阿扁是一位出色的化学研究员。近日，他正致力于研制一种化学药物，用以纠正他糟糕的嗓音。阿扁给他这次研究起的代号是”acm”（arbain’schemicalmagic，“阿扁的化学魔术”)。经过两个星期的寻找，阿扁已经采集了若干种化学原料。现在，他需要对每种原料进行精密的分析，以确定有效成分的含量。每种原料的分析都必须依次经过两个步骤：首先让原料接受一定时间一定量的α粒子轰击（称放射试验）；然后在156.0973℃下与浓硫酸共热（称加热试验），两个试验都必须在特制的精密昂贵的仪器内进行。现在的问题是，由于经费的问题，阿扁的实验室里只有一台做放射试验的仪器及一台做加热试验的仪器。换句话说，同一时间内最多只能做一个放射试验和一个加热试验。而各种原料需做试验的时间是不尽相同的（幸而关于这些时间的数据阿扁已经做了做精确的预算）。现在请你预计一下阿扁能结束试验的最早时间。输入：第一行为原料的数量n（整数，0=n=1000）。以下n行每行各两整数ai，bi，表示第i种原料做放射试验的时间为ai，做加热试验的时间为bi。（0≤ai，bi≤100且ai≠bi）输出：只有一行，为结束试验的最早时间。本题“分析试验”的特殊性在于：每份原料必须先进行放射试验，再进行加热试验；一次只能有一份原料在某一台仪器上做试验。整个试验的进行非常类似于计算机的“并行处理”。易知，由于放射实验所受到的限制少，没有“空闲”的时间，所以放射试验的总时间是确定的（=∑ai）。问题就在于加热试验对放射试验的“等待”。⑴从最简单的情况开始首先，当只有一份原料时，无需安排，先“放射”再“加热”就可以了。当有两份原料时，如Sample1，情况也很简单，无非是1-2和2-1的区别。放射试验a1a2时间12345678910加热试验b1b2放射试验a2a1时间123456789加热试验b2b1结论考虑两份原料i、j，当按照先i后j的顺序做试验时，总耗时进一步，我们设，其含义为在两台仪器上同时试验的时间。那么jijjiiijabbabaT,minjiijab,minjiijjjiijiijbabaTT,max,min⑵再分析原料数增多的情况确定原料两两之间的较优顺序ippipippippiipaabaab即,min,min应把p排在试验最前面piipppiippippibabbab即,min,min应把p排在最后试验constTaskLim=1000；{最多原料数}vartask:array[1..2，1..TaskLim]ofbyte；{每种原料做放射、加热试验的时间}odr:array[1..TaskLim]ofinteger；{最优化顺序}n，totTime:longint；procedureinit；{读入数据}vari，j，k:integer；beginreadln(n)；{读原料数}fori←1tondoreadln(task[1，i]，task[2，i])；{读每种原料的放射试验时间和加热试验时间}end；{init}procedureOrder；{安排试验顺序}vari，j，k，min，bestj，bestk，{当前安排试验的费时、原料和实验内容}pfront，ptail:integer；{头、尾指针}tick:array[1..TaskLim]of0..1；{试验工序}beginfillchar(tick，sizeof(tick)，0)；{试验工序初始化}pfront←0；ptail←n+1；{头尾指针初始化}fori←1tondo{依次安排每个试验}beginmin←30000；{在未安排试验的原料中，寻找试验时间最短的原料bestj,试验内容为k}forj←1tondoif(tick[j]=0)thenfork←1t