搜索

nullnull上海市控江中学 王建德null 虽然最近三年全国奥林匹克信息学复赛中含许多可“一题多解” 的试题，但如果按照较优算法分类的话，大致可分为 虽然最近三年全国奥林匹克信息学复赛中含许多可“一题多解” 的试题，但如果按照较优算法标准分类的话，大致可分为 null特 点 1、凸现信息学知识和学科知识整合的趋势。为了考核学生运用学科知识的能力，激发学生的创造力，2002年全国奥林匹克信息联赛(NOIP)中学科类的试题增加，并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与学科的依赖关系日益凸现，学科基础好、尤其是数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和爱好，他们中愈来愈多的人也希望深造数学。各门学科的交融和整合是奥林匹克信息学联赛活动发展的一个大趋势（有专家提议，数学教材讲算法，信息科技教材讲语言，上海的信息科技教材出现真值表（初中）和c语言（高中））。 2、“构造法” 或贪心策略类试题的引入，使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质—知识是不断推陈出新的。null3、试题的综合性增加，并不一定随知识的分类而发生变化，有时几乎找不到一个单一的经典算法(字串变换——回溯法中有字符串处理)，也找不到一个纯粹的数据结构问题（级数求和——需要为表达式的计算结果合适的数据类型），关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质愈高，得胜的机率愈大；   4、经常面对着不知道算法的试题，面对着谁都不知如何处置的情境（经常出现许多选手在一题中得0分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战，成为培训的基本要求和目标。null 1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考，有了思考才有解决问题的方法，才有找到独立思路的可能（陶行知）”。有问题虽然不一定有创造，但没有问题一定没有创造（想一想当前的解法有没有缺陷，有没有更好的算法，它与哪些问题有联系，与哪些知识相关联，还可以拓延出哪些问题，要解决这些问题还需要哪些知识）；       启 示2、处理好基础性与前沿性、直线培训和散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序，不谋求跳跃式学习，将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍比科学上的障碍更难跨越，敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的跳跃（ 爱笛生三年级退学、比尔.盖茨大学三年级退学）null学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和兴趣结构）和竞争需要的知识结构 培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同，有的同年级同学科的教材相差三分之二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。 3、参与活动的学生应由竞争关系和独立关系（你做你的，我干我的，程序和算法互相保密，彼此津津乐道于对方的失败和自己的成功）转向合作学习的关系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务） null学生的心理调适： 我掌握的知识仅不过是沧海一粟(进取心)； 固守错误的概念比一无所知更可怕（明智）； 三人之行必有我师（谦虚）； 知识生产社会化条件下人的基本素质之一是合作精神（现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作，例如制作windows，人类基因工程）（现代意识）；前提条件：水平相当的同质成员或各有所长（包括数学知识、编程能力和思维方式等解题所需的各种因素）的异质成员是开展合作学习的组织基础；合作学习的效应： 集思广益容易出好的算法； 群体设计的测试数据相对全面； 在群体活动中能比较客观的反映自己能力情况； 每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相容性好、 乐于帮助他人，并且善于取他人之长的学生（符文杰、张一飞等）。null4、选手面对从未遇到过的挑战应调整好心态，不要急功近利，要只管耕耘、不问收获、潜心钻研、其乐无穷。那怕是一两次失误，也是砥砺之石，可从中汲取有益的经验和教训。“不是一番寒彻骨，哪得梅花扑鼻香”。搜索搜索 无论什么类型的试题，只要能归纳出数学模型，我们尽量用解析方法求解。因为一个好的数学模型建立了客观事物间准确的运算关系。运用这个数学模型直接求解是再合适不过的了。当然，这仅是一种可能性，因为并非所有选手都能在竞赛的“一瞬间”把问题分析得如此透彻，并非所有给定的问题都能建立数学模型，即便有了数学模型，但解该模型的准确方法也不一定能立即运用现成算法。因此在某些情况下，还得需要通过搜索（列举所有可能情况）来寻求问题的解。 典型的算法：枚举法、回溯法 枚举法 枚举法 枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：        ⑴可预先确定每个状态的元素个数n； ⑵状态元素a1，a2，…，an的可能值为一个连续的值域。 设 ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k， ai1≤ai≤aik，……，an1≤an≤ank for a1←a11 to a1k do fo a2←a21 to a2k do …………………… for ai←ai1 to aik do …………………… for an←an1 to ank do if 状态(a1，…，ai，…，an)满足检验条件 then 输出问题的解； null枚举法的优点： ⑴由于枚举算法一般是现实生活中问题的“直译”，因此比较直观，易于理解； ⑵由于枚举算法建立在考察大量状态、甚至是穷举所有状态的基础上，所以算法的正确性比较容易证明。枚举法的缺点： 枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。 null优化枚举“直译”枚举“直译”的枚举算法“直译”的枚举算法直接根据题意设定枚举对象、范围和约束条件。 注意认真审题，不要疏漏任何条件 跳远跳远在水平面上整齐的放着n个正三角形，相邻两个三角形的底边之间无空隙， 如左图所示。一个小孩子想站在某个三角形i的顶端，跳到三角形j的顶端上(i v0 then break；{若大于极限速度v0，则无法从三角形i起跳} ok ← true； for k ← i + 1 to j - 1 do{判断跳跃过程中是否碰到其他三角形} begin t ← (x[k] - x[i]) / v；{计算到达三角形k的时间} null if (v * t - 5 * t * t) - (y[k] - y[i]) < 1e-6 then begin{如果该时刻的竖直坐标增量大于起点到顶点k的竖直坐标增量，则抛物线在上方} ok ← false； break； end；{then} end；{for} if ok then best ← j {若跳远成功，则三角形j为目前三角形i所能到达的最远点，否则跳远不能完成} else break； end；{for} write(best，' ')；{输出从三角形i的顶点出发所能到达的最右的三角形编号） end；{for} writeln； end.{main} 一元三次方程求解一元三次方程求解 有形如：ax3+bx2+cx+d＝0这样的一个一元三次方程。给出该方程中各项的系数（a，b，c，d 均为实数），并约定该方程存在三个不同实根（根的范围在—100至100之间），且根与根之差的绝对值≥1。 要求由小到大依次在同一行输出这三个实根（根与根之间留有空格），并精确到小数点后2位。 提示：记方程f（x）=0，若存在2个数x1和x2，且x10，则确定根在右区间[x，x2]内，将x设为该区间的左指针（x1=x），继续对右区间进行对分； 上述对分过程一直进行到区间的间距满足精度要求为止（x2-x1<0.001）。此时确定x1为f’(x)的根。 null输入方程中各项的系数a，b，c，d ； b←b/a； c←c/a； d←d/a；a←1；{将方程变换为x3+b’*x2+c’*x+d’=0的形式} for x←-100 to 100 do{枚举每一个可能的根} begin x1←x；x2←x+1；{确定根的可能区间} if f(x1)=0 {若x1为根，则输出} then write(x1:0:2，’ ’) else if (f(x1)*f(x2)<0) {若根在区间[x1，x2]中} then begin while x2-x1>=0.001 do{若区间[x1，x2]不满足精度要求，则循环} begin xx←(x2+x1)/2；{计算区间[x1，x2]的中间位置} if f(x1)*f(xx)<=0{若根在左区间，则调整右指针} then x2←xx else x1←xx； {若根在右区间，则调整左指针} end；{while} write(x1:0:2，’ ’)；{区间[x1，x2]满足精度要求，确定x1为根} end；{then} end；{for}选择尺子刻度 选择尺子刻度 一根29厘米长的尺子只允许上面刻7个刻度。在能用它量出1~29厘米的各种长度，试问刻度应该怎样选择。 枚举变量有:a1，a2，…，a7。1~29厘米中选择7个刻度的

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

数为c(29,7)=1560780 利用对称性 利用对称性 若目前已知的刻度有a1‥ai (1≤i≤7)，则可以量出的尺寸为ak， ak-aj|1≤j≤k-1，n-ak (1≤k≤i)。例如 a1，29-a1； a2，a2-a1，29-a2； a3，a3-a1，a3-a2，29-a3； … … … … 用对称性（ai←→29-ai）仅考虑a10 then for j：=1 to pi do 输出旋转方法i； 优化方法优化方法1、枚举p1、p2、p3 2、计算 p4＝order(c1－p1－p2 )； p6＝order(c3－p2－p3 )； p5＝order(c2－p1－p2－p3 )； p7＝order(c4－p1－p4－p5 )； p9＝order(c6－p3－p5－p6 )；p8＝order(c8－p7－p9－p5 )； 其中order(c)＝ 3、将p1…p9 代入下述三个检验条件 c7＝(p4 +p7 +p8 ) mod 4 c5＝(p5 +p1 +p3 +p7 +p9 ) mod 4 c9＝(p6 +p8 +p9 ) mod 4侦探推理 侦探推理 明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说： null 证词中出现的其他话，都不列入逻辑推理的内容。明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。 现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！  【输入格式】输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）。M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，每行是明明的一个同学的名字（英文字母组成，没有空格，全部大写）。往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。  【输出格式】如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。 1、根据输入信息建立几张表 1、根据输入信息建立几张表 设同学数为m，有效证词数为proofs；name为名字表，其中name[i]为第i个同学的名字（1≤i≤m）； function person(s:string):byte;{输入姓名串s。若s在名字表name中，则返回其序号；否则返回0} function weekday(s:string):byte;{输入日期串s，返回对应的数字} 计算证词的属性计算证词的属性将证词分为三类 证词的内容是指认谁是罪犯（包括自己）； 证词的内容是指认谁不是罪犯（包括自己）； 证词的内容是指认今天的日期； 证词的属性包括证言人、证词类别和指认对象（同学序号或日期）。设 from为证词的证言人序列，其中from[i]为证词I的证言人序号(1≤i≤proofs)； kind为证词类型序列，其中 obj为指认对象序列，其中obj[i] 为证词i(1≤i≤proofs)指认的同学序号（kind[i]=1，2）或日期（kind[i]=3）； nullprocedure record_proof(s:string);{输入证词s。计算证言人的序号、指认罪犯的同学序号（或日期）和证词类型，分别存入from序列、obj序列和kind序列} var f,k,o,x:byte; begin x:=pos(': ',s);{ 计算证言人的序号f} if x=0 then exit; f:=person(copy(s,1,x-1)); if f=0 then exit; delete(s,1,x+1);{删除证言人的名字} if s='I am guilty.'{若证词内容是“我是罪犯”，则返回指认其为罪犯的同学序号o和证词类型1} then begin k:=1;o:=f;end else if s='I am not guilty.'{若证词内容是“我不是罪犯”，则返回指认其不是罪犯的同学序号o和证词类型2 } then begin k:=2;o:=f;endnullelse if copy(s,length(s)-10,11)='is guilty.'{若证词内容是“***是罪犯”，则返回指认其为罪犯词的同学序号o和证词类型1} then begin o:=person(copy(s,1,length(s)-11));if o=0 then exit;k:=1;end else if copy(s,length(s)-14,15)='is not guilty.'{若证词内容是“***不是罪犯”，则返回指认其不是罪犯的同学序号o和证词类型2 } then begin o:=person(copy(s,1,length(s)-15));if o=0 then exit;k:=2;end else if copy(s,1,9)='Today is'{若证词内容是“今天星期几”，则返回日期o和证词类型3} then begin delete(s,1,9);o:=weekday(s);if o=0 then exit;k:=3;end else exit;{否则失败返回} inc(proofs);{累计证词数} from[proofs]:=f; kind[proofs]:=k;obj[proofs]:=o;{记下第proofs句证词的证言人序号、证词类型和指认对象} end; 在计算证词的同时，计算有效证词数proofs和每句有效证词的属性： 在计算证词的同时，计算有效证词数proofs和每句有效证词的属性： 读同学数m、始终说假话的人数n和证言数p； for i:=1 to m do 读第i个同学的名字name[i]； proofs:=0;{有效的证词数初始化} for i:=1 to p do begin 读第i句证词s； record_proof(s);{记下第i句证词的证言人序号、证词类型和指认对象} end； 2、判断某同学是否为罪犯2、判断某同学是否为罪犯设 当前指认是否为罪犯的同学序号为criminal（kind[i]=1或2，obj[i]=criminal），指认的日期为day（ind[i]=3，obj[i]=criminal），可能成为罪犯的人数为suspects，可能说谎的人数下限为minliars，上限为maxliars； 诚信表为honest。其中honest[i]= ； 罪犯表为possible。其中possible[i]= ； 指认对象是否成立的标志为h。其中h= 判断同学criminal 是否为罪犯判断同学criminal 是否为罪犯procedure judge; var i,minliars,maxliars:byte;{可能说谎的人数下限为minliars，上限为maxliars} h:shortint;{ 指认对象是否成立} begin fillchar(honest,sizeof(honest),0); minliars:=0;maxliars:=m;{可能说谎人数的下限和上限初始化} for i:=1 to proofs do begin{枚举每一条有效证词} case kind[i] of{根据证词I的内容确认同学criminal是罪犯（或日期day）成立与否} 1:if obj[i]=criminal then h:=1 else h:=-1;{若第I句证词指认criminal同学为罪犯，则h为1；否则h为-1} 2:if obj[i]=criminal then h:=-1 else h:=1;{ 若第I句证词指认criminal同学不是罪犯，则h为-1；否则h为1} 3:if obj[i]=day then h:=1 else h:=-1; {若第I句证词指认的日期与当前被枚举的日期一致，则h为1；否则h为-1} end; null if h+honest[from[i]]=0 then exit;{若提供证词的同学的诚信情况与指认结果相反，则退出过程} if honest[from[i]]=0 then{若提供证词的同学的诚信情况未确定，则根据h值计算可能说谎人数的下限minliars和上限maxliars} if h=1 then dec(maxliars) else inc(minliars); if (n>maxliars) or (nbest then best←sum； 这个算法相当粗糙，枚举状态的费用为O（n9） 2、从减少重复计算入手 记录先前考察的结果。在统计长方体2时，只要将长方体1的统计结果加上长方体3就可以了，而不必按上述算法那样重新进行计算。 nullfor x1←1 to n do {枚举所有可能的水平面} for x2←1 to n do for y1←1 to n do for y2←1 to n do for z1←1 to n do {枚举上平面的z轴坐标} begin sum←0； {长方体的体积初始化} for z2←1 to n do {枚举下底面的z轴坐标} 考察状态（x1，y1，z1，x2，y2，z2）； end；{for} 考察过程改为 for x←x1 to x2 do {计算长方体的体积} for y←y1 to y2 do sum←sum+map[x，y，z2]； if sum>best then best←sum； {调整最优解} 由于利用了计算出的结果，整个算法的时间复杂度降为O（n8）。 null3、提取恰当的信息 上述考察实际上求出z轴坐标为z2的平面中矩形（x1，y1，x2，y2）的数和。我们将这个数和记为value(a) value(A)=value(ABCD)+value(B)-value(BC)-value(BD) 这就启发我们用另一种方法表示立方体的信息：设rec[x，y，z]表示z轴坐标为z的水平面中矩形（1，1，x，y）的数和。  z轴坐标为z的水平面中左上角为（x1，y1）、右下角为（x2，y2）的矩阵的数和为rec[x2，y2，z]+ rec[x1，y1，z]-rec[x2，y1，z]-rec[x1，y2，z]  nullRec数组可以在输入数据的同时计算 fillchar(rec，size(rec)，0)；{rec数组初始化} for z←1 to n do {逐层输入信息} for x←1 to n do {逐行输入z平面的信息} begin for y←1 to n do {逐列输入z平面上x行的信息} begin read(map[x，y，z])； {输入z平面上（x,y）中的数} if (x=1)and(y=1){计算z平面上以（1，1）为左上角、（x,y）为右下角的矩形的数和} then rec[1，1，z]←map[1，1，z] else if y=1 then rec[x，y，z]←rec[x-1，y，z]+map[x，y，z] else if x=1 then rec[x，y，z]←rec[x，y-1，z]+map[x，y，z] else rec[x，y，z]←rec[x，y-1，z]+rec[x-1，y，z]-rec[x-1，y-1，z]+map[x，y，z]； end；{for} readln； end；{for}   null这样，考察过程就可以改为 sum←sum+rec[x2，y2，z2]+rec[x1，y1，z2]-rec[x2，y1，z2]-rec[x1，y2，z2]； if sum>best then best←sum； 时间复杂度降为O（n6）。 如果长方体a的数和是负数，则长方体a的计算结果废弃，考察长方体b-a。因为长方体b的数和=长方体b-a的数和+长方体a的数和，由于长方体a的数和为负，长方体b-a的数和一定大于等于长方体b的数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底面的z轴坐标即可。设total(z)——以z轴坐标为z的平面为下底面的长方体的最大数和 total(z)= nullfor x1←1 to n do {枚举所有可能的子平面} for x2←1 to n do for y1←1 to n do for y2←1 to n do begin total←0；{长方体b（该长方体的平面以（x1,y1）为左上角、（x2,y2）为右下上角）的最大数和初始化} for z←1 to n do {枚举长方体b下底面的z轴坐标} begin total←max{total,0}+ rec[x2，y2，z]+ rec[x1-1，y1-1，z]-rec[x2，y1-1，z]-rec[x-1-1，y2，z] ,0]；{计算以z为下底面的长方体b的最大数和} if total> best then best←total； {调整最优解} end；{for} end；{for} 这一改进使得考察的状态整数降为n5， 回溯法 回溯法 回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 null运用算法

框架

财政支出绩效评价指标框架幼儿园园本课程框架学校德育工作框架世界古代史知识框架质量保证体系框架图

解题回溯法的优化算法框架算法框架procedure run（当前状态）； var i：integer； begin if 当前状态为边界 then begin if 当前状态为最佳目标状态 then 记下最优结果；exit；{回溯} end；{then} for i←算符最小值 to 算符最大值 do begin 算符i作用于当前状态，扩展出一个子状态； if (子状态满足约束条件) and (子状态满足最优性要求)then run(子状态)； end；{for} end；{run} 在应用算法框架解题时应考虑的因素在应用算法框架解题时应考虑的因素⑴定义状态：即如何描述问题求解过程中每一步的状况。为了精简程序，增加可读性，我们一般将参与子结点扩展运算的变量组合成当前状态列入值参，以便回溯时能恢复递归前的状态，重新计算下一条路径； ⑵边界条件：即在什么情况下程序不再递归下去。如果是求满足某个特定条件的一条最佳路径，则当前状态到达边界时并非一定意味着此时就是最佳目标状态。因此还须增加判别最优目标状态的条件； ⑶搜索范围：在当前状态不满足边界条件的情况下，应如何设计算符值的范围。换句话说，如何设定for语句中循环变量的初值和终值。 ⑷约束条件和最优性要求：当前扩展出一个子结点后应满足什么条件方可继续递归下去；如果是求满足某个特定条件的一条最佳路径，那么在扩展出某个子状态后是否继续递归搜索下去，不仅取决于子状态是否满足约束条件，而且还取决于子状态是否满足最优性要求。 ⑸参与递归运算的参数：将参与递归运算的参数设为递归子程序的值参或局部变量。若这些参数的存储量大（例如数组）且初始值需由主程序传入，为避免内存溢出，则必须将其设为全局变量，且回溯前需恢复其递归前的值。 null构造字串 生成长度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时 ‘a b C b a’满足条件 ‘a b C b C’不满足条件 输入：n，p 输出：所有满足条件的字串分析 状态：待扩展的字母序号at。实际上字串s亦参与了递归运算，但是由于该变量的存储量太大，因此我们将s设为全局变量； 边界条件和目标状态：产生了一个满足条件的字串，即at=n+1； 搜索范围：第at位置可填的字母集{'a'.. chr(ord('a')+p-1)}； 约束条件：当前字串没有相邻子串相等的情况 var n，p：integer；{字串长度和可选字母的个数} tl：longint； { 满足条件的字串数} ed：char； { 可选字母集中的最大字母} s：string； {满足条件的字串}nullprocedure solve(at：integer)；{递归扩展第at个字母} var ch：char； i：integer； begin if at=n+1 {若产生了一个满足条件的字串，则输出，满足条件的字串数+1} then begin writeln(f，s)； inc(tl)；exit{回溯}end；{then} for ch←'a' to ed do {搜索每一个可填字母} begin s←s+ch；i←1；{检查当前字串是否符合条件} while(i<=atdiv2)and(copy(s，length(s)-i+1，i)<>copy(s，length(s)-2*i+1，i)) do inc(i)； nullif i>at div 2 then solve(at+1)；{若当前字串符合条件，则递归扩展下一个字母} delete(s，length(s)，1){恢复填前的字串} end{for} end；{solve} begin readln(n，p)；{输入字串长度和前缀长短} ed←chr(ord('a')+p-1)；{计算可选字母集中的最大字母} s←''； tl←0；{满足条件的字串初始化为空，字串数为0} solve(1)；{从第1个字母开始递归计算所有满足条件的字串} writeln('Total：'，tl)；{输出满足条件的字串数} end.{main} null 字串变换 [问题描述]：已知有两个字串A$，B$及一组字串变换的规则： A1$→B1$ A2$→B2$ ……… 规则的含义为：在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…..。例如：A$ =‘abcd’ B$=‘xyz’ 变换规则为： ‘abc’→‘xu’ ‘ud’→‘y’ ‘y’→‘yz’ 则此时，A$可以经过一系列的变换变为B$，其变换的过程为： ‘abcd’→‘xud’→‘xy’→‘xyz’ 共进行了三次变换，使得A$变换为B$。 null[输入]：输入文件名为A.in。文件格式如下： A$，B$ A1$ → B1$ A2$ → B2$ 变换规则 ……… 所有字符串长度的上限为255。 [输 出]：输出文件名为A.out。若在30步（包含30步）以内能将A$变换为B$，则向A.out输出最少的变换步数；否则向A.out输出‘ERROR！’。 [输入输出样例] A.in文件： abcd,xyz abc->xu ud->y y->yz A.out文件： 3 null1、分析变换规则 设 规则序列为rule，其中第i条规则为rule[i，1]→rule[i，2]； 当前串为now，其中tmp为now的一个待匹配子串。由于匹配过程的由左而右进行的，因此设j为now的指针，即从now的第j个字符开始匹配rule[i,1]。now适用第i条规则的条件是 now中的子串被第i条规则替换后的长度小于255，即 length(now)+length(rule[i,2])-length(rule[i,1])≤255 rule[i,1]是now的一个子串（k=pos(rule[i,1],tmp)≠0）在使用了第i条规则后，n