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

无心人 发表于 2008-10-6 11:49:00

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

mathe 发表于 2008-10-6 18:35:31

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

无心人 发表于 2008-10-6 20:27:11

:)

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

jiangbin00cn 发表于 2008-10-6 22:09:16

r=10
r=29
r=76
r=284
r=1413
r=7187
r=38103
r=231051
r=1765186

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

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

jiangbin00cn 发表于 2008-10-6 22:18:57

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

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

mathe 发表于 2008-10-6 22:20:51

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

无心人 发表于 2008-10-7 08:19:00

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

mathe 发表于 2008-10-7 08:36:11

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

无心人 发表于 2008-10-7 09:17:32

:)

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

mathe 发表于 2008-10-7 10:01:42

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

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