数学研发论坛

 找回密码
 欢迎注册
楼主: mathe

[擂台] 最小无法表达的正整数

[复制链接]
发表于 2008-10-6 11:49:00 | 显示全部楼层
你估计13的需要多少资源?
最好优化下程序
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-6 18:35:31 | 显示全部楼层
如果顺利,今天晚上应该能够出结果,就剩下4093和4095两个文件了.
不过程序对内存的使用已经超过1.6G了(写代码时没有注意内存使用量会这么大)
对于N>=13以上,就要修改算法了.我觉得仅仅对于+,-,*三种操作符,应该能够处理到N=14.
不过如果验证对于+,-,*,/的结果,能做到N=12我觉得就挺不错了,要到达更大的比较难.
而仅仅做到N=12的验证工作,代码已经会比较复杂了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-6 20:27:11 | 显示全部楼层


能否输出若干的无法表示的(比如最小的1000个)
如果可以
则验证应该不会很复杂
否则
可能验证比寻找还复杂
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-6 22:09:16 | 显示全部楼层
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)之间的数
这能够降低保存的数据,对速度没有什么改进
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-6 22:18:57 | 显示全部楼层
r[k]=a
==〉r[k+1] <= a*(k+1)

这个是根据上面的结论推导出来的,似乎无法证明
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-6 22:20:51 | 显示全部楼层
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通过+,-,*表示出来的整数.扫描一下这个文件就可以了.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 08:19:00 | 显示全部楼层
那就说明
n=13的数据量应该还不至于太大
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-7 08:36:11 | 显示全部楼层
仅仅使用+,-,*,我觉得计算到N=14没有问题.只是这时候还需要面临int表达的数据范围太小的问题.当然将数据类型改成long long就可以了.但是算法还是要修改一下,不然太慢了.
但是如果添加了/以后,验证算法还是比较难写的.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-7 09:17:32 | 显示全部楼层


你觉得是否需要验证下11,12的结果?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-7 10:01:42 | 显示全部楼层
当然.其实如果验证的结果不通过我会更加高兴
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-30 15:47 , Processed in 0.058199 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表