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

无心人 发表于 2008-10-1 17:59:09

你的程序能改写下
来验证某个数字存在或者不存在表达式么？

mathe 发表于 2008-10-2 05:49:51

呵呵,验算程序当然需要重新写.挺有复杂度的,但是应该能写出一个效率挺高的算法.
而我现在在考虑另外一种情况,其实非常可能只使用+,-,*三种操作符就可以得到我们需要的大部分整数结果(甚至于全部).
而对于这个情况,由于肯定只产生整数结果,可以使用动态规划

mathe 发表于 2008-10-2 05:52:12

可以参考一个Java程序:
http://www.mitbbs.cn/bbsann2/scitech.faq/Science/Amusement/24points/M.1017979781.A/the%20program
这个程序对除法使用了"整数除",所以是错误的代码.
但是如果我们删除除法运算,那么代码就是完全可用的了.
只是我没有Java编译器,谁试着修改运行一下?或者改成C代码也行.

无心人 发表于 2008-10-2 07:28:15

11的到现在还没出结果
有点怀疑是否当了
已经超过14小时了

你老提动态规划
你想做几个动态规划
假设11的有400万个
你想解400万个动态规划问题么？

无心人 发表于 2008-10-2 07:40:02

挺好改的

不过要安装个J2SE6 update 7
太大了
在安装中

无心人 发表于 2008-10-2 07:48:11

也忒大了点
中断掉了

在寻找不是很大的版本

无心人 发表于 2008-10-2 09:05:12

通过Java编译后执行出现问题
唉

看不懂

mathe 发表于 2008-10-2 09:29:13

应该先运行一个规模小一点的,不要以上来就n=11.

mathe 发表于 2008-10-2 09:33:28

原帖由 无心人 于 2008-10-2 07:28 发表 http://bbs.emath.ac.cn/images/common/back.gif
11的到现在还没出结果
有点怀疑是否当了
已经超过14小时了

你老提动态规划
你想做几个动态规划
假设11的有400万个
你想解400万个动态规划问题么？
11的问题复杂度很大的.你应该先运行一下小一点的n,这样对运行时间才可以大概估计一下.比如我前面的程序n=10已经需要两天了,n=11我就没有试了.
最好的方法应该是结合我的代码和那个Java代码的思想.不过挺复杂的,短期内我不会有时间去试验

无心人 发表于 2008-10-2 10:01:00

我前面有个测试的
刚计算了是每分钟5673个表达式

但中间存在停顿现象
所以要比估计的慢

估计在400万-1000万表达式
所以估计时间是11.75-29.38小时
如果考虑停顿，则要乘以1.5-2.0的系数

我还是去看看去吧
呵呵

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