最小无法表达的正整数

无心人

没有 算平方和的机器还在满负荷运算 10天出一个结果 打算等下个平方和出来就暂时停掉 另外，最近有点忙 上班做在机器前的时间有闲 学校电脑大搬家 老多事情 等10.1后差不多吧 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 我打算用我的部分结果的程序 然后对剩余的1000个无法表示的数字逐步淘汰 应该快于完整搜索 你考虑能再进一步优化算法 使得部分搜索能即简单又覆盖面大

mathe

原帖由 mathe 于 2008-8-21 10:31 发表 发现这道题目A060315也已经给到第10项了，和我结果相同。

发现A060315其实计算的是个不同的数据:它是部分数字构成的整数也算,不过非常有意思,前十项结果相同(我稍微修改了一下程序,至少很快就可以验证前8项都的确是相同的),所以现在有个问题,是不是这两个不同的序列结果总是相同.

无心人

呵呵 应该不是吧

无心人

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

无心人

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

无心人

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

无心人

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

无心人

测试下 按我前面的中序表示堆栈算法 从右到左读取序列 遇到数字压栈，遇到运算符号，弹出2个数字运算后结果压栈 有部分结果，2个数字的 + 2 3 表示5 - 4 1表示3 用*连接得到4个数字的 * + 2 3 - 4 1得到15 完全正确 但要定义一个结束标志0以区分不同长度

mathe

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

无心人

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