数学建模 24点游戏问题 在线等

1个回答

  • 利用计算程序来完成这个计算二十四点的程序

    方法如下:

    首先穷举的可行性问题。把表达式如下分成三类——

    1、 无括号的简单表达式。

    2、 有一个括号的简单表达式。

    3、 有两个括号的较复杂表达式。

    在栈中,元素的插入称为压入(push)或入栈,元素的删除称为弹出(pop)或退栈。

    栈的基本运算有三种,其中包括入栈运算、退栈运算以及读栈顶元素,这些请参考相关数据结构资料。根据这些基本运算就可以用数组模拟出栈来。

    那么作为栈的著名应用,表达式的计算可以有两种方法。

    第一种方法:

    首先建立两个栈,操作数栈OVS和运算符栈OPS。其中,操作数栈用来记忆表达式中的操作数,其栈顶指针为topv,初始时为空,即topv=0;运算符栈用来记忆表达式中的运算符,其栈顶指针为topp,初始时,栈中只有一个表达式结束符,即topp=1,且OPS(1)=‘;’。此处的‘;’即表达式结束符。

    然后自左至右的扫描待处理的表达式,并假设当前扫描到的符号为W,根据不同的符号W做如下不同的处理:

    1、 若W为操作数

    2、 则将W压入操作数栈OVS

    3、 且继续扫描下一个字符

    4、 若W为运算符

    5、 则根据运算符的性质做相应的处理:

    6、若运算符为左括号或者运算符的优先级大于运算符栈栈顶的运算符(即OPS(top)),则将运算符W压入运算符栈OPS,并继续扫描下一个字符。

    7、若运算符W为表达式结束符‘;’且运算符栈栈顶的运算符也为表达式结束符(即OPS(topp)=’;’),则处理过程结束,此时,操作数栈栈顶元素(即OVS(topv))即为表达式的值。

    8、若运算符W为右括号且运算符栈栈顶的运算符为左括号(即OPS(topp)=’(‘),则将左括号从运算符栈谈出,且继续扫描下一个符号。

    9、若运算符的右不大于运算符栈栈顶的运算符(即OPS(topp)),则从操作数栈OVS中弹出两个操作数,设先后弹出的操作数为a、b,再从运算符栈OPS中弹出一个运算符,设为+,然后作运算a+b,并将运算结果压入操作数栈OVS。本次的运算符下次将重新考虑。

    第二种方法:

    首先对表达式进行线性化,然后将线性表达式转换成机器指令序列以便进行求值。

    那么什么是表达式的线性化呢?人们所习惯的表达式的表达方法称为中缀表示。中缀表示的特点是运算符位于运算对象的中间。但这种表示方式,有时必须借助括号才能将运算顺序表达清楚,而且处理也比较复杂。

    1929年,波兰逻辑学家Lukasiewicz提出一种不用括号的逻辑符号体系,后来人们称之为波兰表示法(Polish notation)。波兰表达式的特点是运算符位于运算对象的后面,因此称为后缀表示。在对波兰表达式进行运算,严格按照自左至右的顺序进行。下面给出一些表达式及其相应的波兰表达式。

    表达式波兰表达式

    A-B AB-

    OK,所谓表达式的线性化是指将中缀表达的表达式转化为波兰表达式。对于每一个表达式,利用栈可以把表达式变换成波兰表达式,也可以利用栈来计算波兰表达式的值。

    至于转换和计算的过程和第一种方法大同小异,这里就不再赘述了。

    下面给出转换和计算的具体实现程序——

    这样这个程序基本上就算解决了,回过头来拿这个程序来算一算文章开始的那个问题。很快就算出来了,原来如此简单——(6-3)*10-6=24。