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

无心人 发表于 2008-9-11 11:04:15

:)

没有
算平方和的机器还在满负荷运算
10天出一个结果
打算等下个平方和出来就暂时停掉

另外，最近有点忙
上班做在机器前的时间有闲

学校电脑大搬家
老多事情
等10.1后差不多吧
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
我打算用我的部分结果的程序
然后对剩余的1000个无法表示的数字逐步淘汰

应该快于完整搜索
你考虑能再进一步优化算法
使得部分搜索能即简单又覆盖面大

mathe 发表于 2008-10-1 15:32:28

原帖由 mathe 于 2008-8-21 10:31 发表 http://bbs.emath.ac.cn/images/common/back.gif
发现这道题目A060315也已经给到第10项了，和我结果相同。
发现A060315其实计算的是个不同的数据:它是部分数字构成的整数也算,不过非常有意思,前十项结果相同(我稍微修改了一下程序,至少很快就可以验证前8项都的确是相同的),所以现在有个问题,是不是这两个不同的序列结果总是相同.

无心人 发表于 2008-10-1 16:20:43

呵呵

应该不是吧

无心人 发表于 2008-10-1 16:43:05

我在服务器启动了33#程序
计算11的部分结果
最后将在文件里记录下最先无法表示的1000个数字
看最后结果吧
应该在100-1000万之间
估计400万附近

无心人 发表于 2008-10-1 16:50:36

没记录得到结果的数字
要记录那个，估计要几个G的文本
太大了

无心人 发表于 2008-10-1 17:45:35

想到一个笨算法
从2个数字开始
计算表达式记录在文件
...
n个数字的等于
1个数字和n-1个数字运算
2个数字和n-2个数字运算
...
...
应该能穷尽所有可能
应该比穷举所有可能要大大减少运算
但可能算法速度不会很快
而且似乎要占很大的硬盘空间

无心人 发表于 2008-10-1 17:47:35

:)

还可以列个矩阵
顺便得到不完全数字情况下的结果
考虑到如果定义固定长度的结构
则完全可以在文件里实现随机存储

呵呵

无心人 发表于 2008-10-1 17:53:55

测试下
按我前面的中序表示堆栈算法
从右到左读取序列
遇到数字压栈，遇到运算符号，弹出2个数字运算后结果压栈
有部分结果，2个数字的
+ 2 3 表示5
-   41表示3
用*连接得到4个数字的
* + 2 3 - 4 1得到15
完全正确


但要定义一个结束标志0以区分不同长度

mathe 发表于 2008-10-1 17:55:06

使用外存储是正确的思路.而对于只使用纯整数的中间过程,可以使用动态规划的方法.由于只保存整数数据,中间数据还可以选择采用比特位保存结果.
你的程序对于n<=10的结果是多少?

无心人 发表于 2008-10-1 17:57:40

:)

我直接算的11
还没看到结果我就回家了
可能要到明天才能算出来

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