最小无法表达的正整数

无心人

你估计13的需要多少资源？
最好优化下程序

mathe

如果顺利,今天晚上应该能够出结果,就剩下4093和4095两个文件了.
不过程序对内存的使用已经超过1.6G了(写代码时没有注意内存使用量会这么大)
对于N>=13以上,就要修改算法了.我觉得仅仅对于+,-,*三种操作符,应该能够处理到N=14.
不过如果验证对于+,-,*,/的结果,能做到N=12我觉得就挺不错了,要到达更大的比较难.
而仅仅做到N=12的验证工作,代码已经会比较复杂了

无心人

能否输出若干的无法表示的（比如最小的1000个）
如果可以
则验证应该不会很复杂
否则
可能验证比寻找还复杂

jiangbin00cn

r[3]=10
r[4]=29
r[5]=76
r[6]=284
r[7]=1413
r[8]=7187
r[9]=38103
r[10]=231051
r[11]=1765186

//////////////////////////////////////////////
假设
r[k]=a
==〉r[k+1] <= a*(k+1)

那么实际上需要验证的是 a~a*(k+1)之间的数
但是验证所花费的时间相当与穷尽，只不过只需要保存 a~a*(k+1)之间的数
这能够降低保存的数据，对速度没有什么改进

jiangbin00cn

r[k]=a
==〉r[k+1] <= a*(k+1)

这个是根据上面的结论推导出来的，似乎无法证明

mathe

r[3]=10
r[4]=29
r[5]=76
r[6]=284
r[7]=1413
r[8]=7187
r[9]=38103
r[10]=231051
r[11]=1765186
r[12]=10539427
19:46得到最后一个结果. 产生的所有文件总共1.63G.
至于无心人说的输出若干的无法表示的没有任何问题.现在比如文件4095里面保存的就是所有能够用1~12通过+,-,*表示出来的整数.扫描一下这个文件就可以了.

无心人

那就说明
n=13的数据量应该还不至于太大

mathe

仅仅使用+,-,*,我觉得计算到N=14没有问题.只是这时候还需要面临int表达的数据范围太小的问题.当然将数据类型改成long long就可以了.但是算法还是要修改一下,不然太慢了.
但是如果添加了/以后,验证算法还是比较难写的.

无心人

你觉得是否需要验证下11，12的结果？

mathe

当然.其实如果验证的结果不通过我会更加高兴