最小无法表达的正整数

无心人 · 发表于 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/sci ... 781.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 发表 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的系数我还是去看看去吧呵呵

账号		自动登录	找回密码
密码			欢迎注册

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