队列和广搜.pptVIP

例4. 程序复杂度 给出一段程序，计算它的时间复杂度。这段程序只有三种语句： –OP x：执行一条时间耗费为x 的指令。这里的x 为不超过100 的正整数。 –LOOP x：与} 配套，中间的语句循环x 次，其中x 可以为规模n，也可以是不超过100 的正整数。 end：与LOOP 配套，循环终止。 注意：OP 语句的参数不能为变量n，而LOOP 语句的参数可以为变量n，但不允许有其他名字的变量。这样，整个程序的时间复杂度应为n 的多项式。你的任务就是计算并显示出这个多项式。 输出仅包含一行，即时间复杂度的多项式。这个多项式应该按通常的方式显示处理，即不要输出0n 这样的项，n项也不要输出为n^1，等等。 使用栈计算表达式 由于Loop与最近的NED配对，因此进入循环（Loop）相当于入栈；退出循环（end）相当于出栈 分析没有变量n只有常数的简单情况 基于栈的扫描算法： –LOOP y和OP x: 把语句入栈 –end:不断从栈里弹出语句，直到弹出LOOP y。弹出op x过程中累加操作数x，最后乘以循环次数y，把OP x*y压入栈中，相当于用一条OP等效一个LOOP 直接推广栈扫描算法 –栈里的每个操作数不是数，而是多项式 –多项式加法，多项式与整数的乘积 问题: –多项式如何表示 –多项式操作的时间复杂度是怎样的？ “把括号展开” 先想办法去掉所有LOOP/end 借助当前乘数确定这次OP的最终效果 基本算法 设 m2为当前n的次幂；m1为乘数，即当前项nm2的系数；max为n的最高次幂。初始时m1=1，m2=0，max=0。 a为存储循环次数的栈，栈顶指针为p。若循环次数为n的话，a[p]=0； ans为结果表达式，其中ans[i]为ni的系数。 主循环：一条一条语句处理 –遇到LOP (n)x命令: ⑴LOP n: 0入栈a；m2←m2+1，并调整max ⑵LOP x: x入栈a；m1←m1*x –遇到OP x命令: ans[m2]←ans[m2]+m1*x; {结果使nm2的系数增加m1*x} –遇到end命令: 若a的栈顶元素为0，则m2←m2-1；否则m1←m1 div a[p]。a出栈操作； 数据结构 var  a,ans:array[0..10000]of longint; /*a为存储循环次数的栈，栈顶指针为p。若循环次数为n的话，a[p]=0，n的次幂为m2；ans为结果表达式，其中ans[i]为ni的系数*/ m1,m2,p,max,x,i:longint; /*m1为乘数，m2为当前n的次幂，max为n的最高次幂*/  s：string; /*命令行*/ 注意输入格式 1、用字符串输入一行命令，命令串的首字符可辨别出其类型（‘L’、‘O’、‘E’）。删除命令字后处理操作数； 2、一条命令中的命令字与操作数间用空格隔开；同行的命令与命令之间用空格隔开，最后一条命令尾没有空格； 3、逐行处理命令。读入当前行命令后，处理一条命令即删除该命令子串，直至串空为止。 处理当前行命令s while s do/*由左而由处理当前命令*/ { while (length(s)0)and(s[1]= ) do delete(s,1,1); /*略去命令前的无用空格*/ case s[1] of /*分析命令类型*/ O: /*处理OP命令*/ { i ← pos( ,s);delete(s,1,i); /*删除’OP’*/ i ← pos( ,s); /*将时间耗费串转换为整数x*/ if i=0 /* OP命令是否为当前行的最后一条命令*/ then { val(s,x,ok);s ← ‘ } else { val(copy(s,1,i-1),x,ok);delete(s,1,i);}; ans[m2] ← ans[m2]+m1*x; /*结果使nm2的系数增加m1*x*/ continue; };/*O*/ L: /*处理LOP命令*/ { i←pos(‘ ’,s);delete(