当前位置:首页 >> 学科竞赛 >>

NOIP2005提高组equal等价表达式


NOIP2005 提高组 equal 等价表达式
【问题描述】 明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻烦的选择题。这个题目的题干中首先给出了 一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式 是和题干中的表达式等价的。 这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不是可以用计算机来解

决这个问题。假设 你是明明,能完成这个任务吗? 这个选择题中的每个表达式都满足下面的性质: 1. 表达式只可能包含一个变量‘a’。 2. 表达式中出现的数都是正整数,而且都小于 10000。 3. 表达式中可以包括四种运算‘+’(加),‘-’(减),‘*’(乘),‘^’(乘幂),以及小括号‘(’,‘)’。小括号的优先级最高, 其次是‘^’,然后是‘*’,最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。(注意:运 算符‘+’,‘-’,‘*’,‘^’以及小括号‘(’,‘)’都是英文字符) 4. 幂指数只可能是 1 到 10 之间的正整数(包括 1 和 10)。 5. 表达式内部,头部或者尾部都可能有一些多余的空格。 下面是一些合理的表达式的例子: ((a^1) ^ 2)^3,a*a+a-a,((a+a)),9999+(a-a)*a,1 + (a -1)^3,1^10^9…… 【输入文件】 输入文件 equal.in 的第一行给出的是题干中的表达式。第二行是一个整数 n(2 <= n <= 26),表示选项的 个数。后面 n 行,每行包括一个选项中的表达式。这 n 个选项的标号分别是 A,B,C,D…… 输入中的表达式的长度都不超过 50 个字符,而且保证选项中总有表达式和题干中的表达式是等价的。 【输出文件】 输出文件 equal.out 包括一行,这一行包括一系列选项的标号,表示哪些选项是和题干中的表达式等价的。选 项的标号按照字母顺序排列,而且之间没有空格。 【样例输入】 ( a + 1) ^2 3 (a-1)^2+4*a a + 1+ a a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a 【样例输出】 AC 【数据规模】 对于 30%的数据,表达式中只可能出现两种运算符‘+’和‘-’;对于其它的数据,四种运算符‘+’,‘-’,‘*’,‘^’ 在表达式中都可能出现。 对于全部的数据,表达式中都可能出现小括号‘(’和‘)’。

第 1 页

2009-06-04

NOIP2005 提高组 equal 等价表达式
算法分析: 用栈的方法求表达式的值是经典的算法。考虑到多项式的处理比较麻烦,不妨对变量 a 进行多次赋值以判断表 达式是否等价。 值得注意,由于进行数值运算,采用哪种数据类型成为程序是否正确的关键。下面的程序,采取 mod m 的 方法,其中 m 为任意正整数。当对 a 多次赋值,且 m 取不同的较大的正整数时,可以保证算法的正确性。 const max=maxlongint; com:array[1..7,1..7] of char=(('>','>','<','<','<','>','>'), ('>','>','<','<','<','>','>'), ('>','>','>','<','<','>','>'), ('>','>','>','>','<','>','>'), ('<','<','<','<','<','=','X'), ('>','>','>','>','X','>','>'), ('<','<','<','<','<','X','X')); var oped:array[1..1000] of longint; optr:array[1..1000] of char; s:array[0..26] of string; value:array[0..26,-4..4] of int64; ans:array[0..26] of boolean; n,i,j,p,q:longint; a,b,ned,ntr:int64; there:char; flag:boolean; function compare(w1,w2:char):char; var x1,x2:integer; begin case w1 of '+':x1:=1; '-':x1:=2; '*':x1:=3; '^':x1:=4; '(':x1:=5; ')':x1:=6; '#':x1:=7; end; case w2 of '+':x2:=1; '-':x2:=2; '*':x2:=3; '^':x2:=4; '(':x2:=5; ')':x2:=6; '#':x2:=7; end; compare:=com[x1,x2]; end;

第 2 页

2009-06-04

NOIP2005 提高组 equal 等价表达式
function operation(a:int64;there:char;b:int64):int64; var i:longint; begin case there of '+':operation:=(a+b) mod max; '-':operation:=(a-b) mod max; '*':operation:=(a*b) mod max; '^':begin operation:=1; for i:=1 to b do operation:=operation*a mod max; end; end; end; function exp(s:string;aa:int64):int64; var i:int64; begin s:=s+'#'; i:=1; ned:=0;ntr:=1; fillchar(oped,sizeof(oped),0); optr:=''; optr[1]:='#';flag:=false; while not ((s[i]='#')and (optr[ntr]='#')) do begin if s[i] in ['0'..'9'] then begin if not flag then begin ned:=ned+1; oped[ned]:=ord(s[i])-ord('0'); flag:=true; inc(i); end else begin oped[ned]:=oped[ned]*10+ord(s[i])-ord('0'); inc(i); end; end else

第 3 页

2009-06-04

NOIP2005 提高组 equal 等价表达式
if s[i]='a' then begin inc(ned);oped[ned]:=aa;inc(i);end else if s[i]=' ' then inc(i) else begin flag:=false; case compare(optr[ntr],s[i]) of '<':begin ntr:=ntr+1;optr[ntr]:=s[i];inc(i);end; '>':begin there:=optr[ntr];ntr:=ntr-1; b:=oped[ned];ned:=ned-1; a:=oped[ned]; oped[ned]:=operation(a,there,b); end; '=':begin ntr:=ntr-1;inc(i);end; end; end; end; exp:=oped[1]; end; begin assign(input,'equal.in');reset(input); assign(output,'equal.out');rewrite(output); readln(s[0]);readln(n); for i:=1 to n do readln(s[i]); fillchar(ans,sizeof(ans),true); for i:=0 to n do if ans[i] then for j:=-4 to 4 do begin value[i,j]:=exp(s[i],j); if value[i,j]<>value[0,j] then begin ans[i]:=false;break;end; end; for i:=1 to n do if ans[i] then write(chr(ord('A')+i-1)); writeln; close(input);close(output); end.

第 4 页

2009-06-04

NOIP2005 提高组 equal 等价表达式
[问题分析] 这道题目拿到手后,一般可以想到的方法就是可不可以将所有的表达式全部转化为最简形式,这时,你就想到 了一种一般的解决方案。即将所有的表达式全部化为最简,然后再计算,这种方法是一种准确的方法。但要在考场 上实现,有一些麻烦,需要一些时间。这种方法的解决过程是:先将阶乘化乘,再展开。计算同时合并同类项,留 下一个数组。然后比较每一个表达式的数组与题目数组是否相同,时间效率也并不高。那么怎么办呢?

[模型建立和实现] 我们这里介绍一种利用必要条件的解决方案。 即两个表达式如果等价,那么无论 a 为何值,两个表达式计算出的值都相等。这时,我们以不同的 a 值代入各 式,可以快速排斥那些不同的表达式,留下的便是等价的了。 我们怎样取值呢?这里推荐几种有效的方法: 1>取随机函数生成的数列。这种方法比较有效,无规律。 2>取伪随机数列。这是一种比较便于人工控制的手段。 3>取实数。由于其他皆为整数,小数部分便成为判断的优越条件。 一般情况下取 4~7 组值便可通过极大部分情况,实数需要更小。如果取更多组的值,便可以通过几乎所有的情况 (将两式连立,只有当取值都为方程的解时才会出现误判,显然这样的几率是极小的)。 补充:这道题可能会有选手在数据类型上选择不当,导致一些情况会出现溢出。 [表达式求值] 经过上面的叙述,难点落在了表达式求值上,在这里我们介绍一下最一般、最简单的方法,栈运算。 用栈实现表达式求值的方法: 首先,我们要给每一个符号一个优先级: 符号 栈内级别 栈外级别 + 2 1 * 4 3 / ^ 6 5 ( 0 8 ) 8 0

可以看到,优先级高的符号先算。为了方便起见,我们定义特殊符号#,它级别最低(赋-1) 先将它置栈底,然后依次读入每个字符,如果是数字则入数栈。如果是符号,就与栈顶符号比较优先级。如果相等, 则退栈,读下一字符。如果栈外大,则入栈。如果栈内大,则取栈顶元素与数栈最顶 2 元素运算,结果入数栈。这 个符号继续处理(再与栈顶比较)。直到读到最后符号#使栈底#出栈时。数栈顶即为表达式结果。 由此,本题已经变得清晰了,剩下的就是具体将我们的表述变成代码。

第 5 页

2009-06-04


相关文章:
NOIP2005提高组试题
NOIP2005提高组试题_其它考试_资格考试/认证_教育专区。历届NOIP试题NOIP...等价表达式(equal.pas/c/cpp) 【问题描述】 明明进了中学之后,学到了代数...
NOIP2005提高组解题报告
NOIP2005提高组解题报告_初一理化生_理化生_初中教育_教育专区。NOIP2005提高组NOIP...第3页 共5页 等价表达式第四题 等价表达式 Equal [问题分析 问题分析] 问题...
NOIP2005提高组解题报告
程序: program equal; const max=maxlongint; const com:array[1..7,1..7...noip2005提高组解题报告... 52页 免费 等价表达式_NOIP2005提高... 6页 2下载...
NOIP 2005-95 解题报告 北极天南星2005
NOIP2007普及组解题报告 12页 免费 NOIP2005提高组解题报告 5页 免费 NOIP提高...4.等价表达式(equal) 表达式是比较复杂的,特别是加上^后,如果要化简的话还要...
NOIP2005提高组初赛试题及答案
NOIP2005提高组初赛试题及答案_财会/金融考试_资格考试/认证_教育专区。第十一届...11. 设A = true,B = false,C = false,D = true,以下逻辑运算表达式值为...
NOIP2005提高组复赛第二题 过河分析
NOIP2005提高组复赛第二题 过河分析_IT/计算机_专业资料。NOIP2005 青蛙过河 详细分析 过河【问题描述】在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到...
NOIP2005提高组(pascal)初赛试题及答案
NOIP2005提高组(pascal)初赛试题及答案_IT/计算机_专业资料。NOIP2005提高组(pascal...11. 设A = true,B = false,C = false,D = true,以下逻辑运算表达式值...
NOIP2002-2005解题报告
NOIP2005提高组解题报告 4页 免费 noip2005提高组解题...(-n/2<=T<=n/2) 2 2 题四:等价表达式【...文件 equal.in 的第一行给出的是题干中的表达式。...
等价表达式
等价表达式_数学_自然科学_专业资料。NOIP2005-4 解题报告:等价表达式 (equal.pas...第1章状空表达式 暂无评价 104页 2下载券 NOIP2005提高组equal等价... 5页 ...
NOIP基本程序题集解题报告
等价表达式_NOIP2005提高组... 6页 5财富值 NOIP 2007解题报告 11页 免费 NOIP2010普及组第四题《三... 5页 5财富值 Noip 2010普及组解题报告 5页 2财富...
更多相关标签: