论坛 › 编程擂台 › 最小无法表达的正整数

无心人 发表于 2008-8-5 14:01:31

就是根据n个数字的表达式实际上是一个以操作符做根节点
操作数做叶节点的二叉树

然后根据二叉树的中序遍历方式生成所有的树
一旦树生成,则计算得到的树的值

无心人 发表于 2008-8-5 14:03:15

(5-1/5)*5是什么意思?
似乎不符合四则运算的本意

mathe 发表于 2008-8-5 14:45:50

原帖由 无心人 于 2008-8-5 14:03 发表 http://bbs.emath.ac.cn/images/common/back.gif
(5-1/5)*5是什么意思?
似乎不符合四则运算的本意
也就是我的运算过程是允许出现分数的
:lol

无心人 发表于 2008-8-5 15:33:41

你说一个必须是分数的例子

分数计算要使用GMP了
太慢

mathe 发表于 2008-8-5 16:12:17

很有可能不需要用分数:lol
这也是为什么我们可能存在更加好的办法，可以先使用中间没有分数的版本给大部分可以的整数找到解。
然后证明余下最小的整数不存在表达式。（而如果的确构造出一个解，在检查次大的...）这个方法应该可以超越我现在的程序

无心人 发表于 2008-8-5 20:38:03

:)

我想我的程序速度应该比你的快吧
不过，我无法证明是否中间数字必然小于等于2^32
在n <= 16时

无心人 发表于 2008-8-5 21:26:36

我还是要换一种表达式树构造方式
我想能否直接把数字和操作符写到对应位置
然后对每种状态求值
我目前的递归，似乎存在状态的丢失
即已经产生，但无法达到检测状态的条件

6的就是丢失了 * +开头的所有序列
我看代码绝对产生了该类型序列
但序列可能仅仅空循环递归了
而在叶子数测试的过程中
未满足条件，结果全部未测试之

[ 本帖最后由 无心人 于 2008-8-5 21:33 编辑 ]

shshsh_0510 发表于 2008-8-6 11:35:17

看看:)

无心人 发表于 2008-8-7 08:51:57

我想了
可能你说的任何带分数的解应该都能有对应的无分数解
但我无法证明
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
今天早上想起来一个思路
打算用栈来处理递归
把要作的工作保存到栈
只有栈为空才能输出
而且，每个循环一定要调用函数
去处理栈上的未完成工作
以保证不会出现空循环而不输出的情况

无心人 发表于 2008-8-7 08:57:03

至于栈上保存什么？

n个数字的完全表达式
其四则运算操作符数量一定是n - 1
考虑一个二叉树
根节点一定是操作符，叶节点一定是操作数
定义根节点的度是其所有子节点中，非叶节点的个数

那我们可以证明
对每个根节点，其度等于左右子节点的度的和加一等于

那么只要循环生成所有子节点的度的组合形式就能生成所有的子节点
这是一个简单的单重循环

而栈里保存了上级节点的未处理的节点的度

查看完整版本: 最小无法表达的正整数