4模拟策略1.pptVIP

模拟策略 在自然界和日常生活中，许多现象具有不确定的性质，有些问题甚至很难建立数学模型，或者很难用计算机建立递推、递归、枚举、回溯法等算法。在这种情况下，一般采用模拟策略。所谓模拟策略就是模拟某个过程，通过改变数学模型的各种参数，进而观察变更这些参数所引起过程状态的变化，由此展开算法设计。 模拟题的形式 ⑴随机模拟：题目给定或者隐含某一概率。设计者利用随机函数和取整函数设定某一范围的随机值，将符合概率的随机值作为参数。然后根据这一模拟的数学模型展开算法设计。由于解题过程借助了计算机的伪随机数发生数，其随机的意义要比实际问题中真实的随机变量稍差一些，因此模拟效果有不确定的因素； ⑵过程模拟：题目不给出概率，要求编程者按照题意设计数学模型的各种参数，观察变更这些参数所引起过程状态的变化，由此展开算法设计。模拟效果完全取决于过程模拟的真实性和算法的正确性，不含任何不确定因素。由于过程模拟的结果无二义性，因此竞赛大都采用过程模拟。 模拟的解题方法的类型 ⑴直叙式模拟 ⑵筛选法模拟 ⑶构造法模拟 ⑴直叙式模拟 直叙式模拟即按照试题要求展开模拟过程。编程者要忠实于原题，认真审题，千万不要疏漏任何条件，精心设计方便模拟的数据结构。“直叙式模拟”的难度取决于模拟对象所包含的动态变化的属性有多少，动态属性愈多，则难度愈大。 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+} var degree ： array[1 .. 20] of integer；{ 存储系数个数的栈} co ： array[1 .. 20， 0 .. 64] of extended；{存储多项式的栈} tmp ： array[0 .. 64] of extended；{系数序列} I， j， d， a， b， top ： integer；{ 栈顶指针为top } s ： string；{ Dam程序} first ： boolean； begin top ← 1；{ 栈顶指针初始化} fillchar(co， sizeof(co)， 0)；{ 存储多项式的栈清零} degree[1] ← 1；{初始时栈里只有一个元素x} co[1， 1] ← 1； read(s)；{输入Dam程序} for I ← 1 to length(s) do{依次执行Dam程序中的每一条命令} case s[I] of ‘D’： begin { 把栈顶元素复制一次加到栈顶} inc(top)；degree[top] ← degree[top – 1]； for j ← 0 to degree[top] do co[top， j] ← co[top – 1， j]； end；{ ‘D’} ‘ A’： begin{ 把栈顶元素取出，加到新的栈顶元素中} dec(top)； if degree[top] degree[top + 1] then degree[top] ← degree[top + 1]；