gxqcn 发表于 2009-8-17 11:27:49

附带两个新问题:

限定输入的N范围为:1~4294967295,请问:
1、对应结果字串中含“0”的数目最大可为多少?
2、当N与10互素且(N+1)不为10的整数次幂时,对应结果位数最长可达多少?

gxqcn 发表于 2009-8-17 11:38:53

关于第2个问题,我现在有一个比较大的结果:
N=4294960461
1101111111111010111111111111001101111101111
它有43位,不知最长的可就是它了?

gxqcn 发表于 2009-8-17 13:48:11

接着搜了几个小时,又得到几个返回结果比较长的数据,它们均有43位:N=4294960461
1101111111111010111111111111001101111101111

N=4294940463
1101110111100111111110110111111111111011111

N=4294880469
1100111111111111000111111111101111111111011

N=4294860471
1101111100011111111111111011011111101111111用 14# 编译好的程序运行,耗时依次如下:
search_pid21021.exe(代码见2# ):21156ms、19469ms、19875ms、23750ms
search_pid21101.exe(代码见 14#):12719ms、12578ms、12422ms、12782ms

mathe 发表于 2009-8-17 14:03:37

69999993
的结果可以达到64位

mathe 发表于 2009-8-17 14:05:51

在你指定的范围,很可能结果为2999999997,长度为73

gxqcn 发表于 2009-8-17 14:08:15

N=69999993
1111111111111111111111111111011111111111111111111111111111111111

这么奇妙的数据是如何得到的?理论推导出来的吗?

mathe 发表于 2009-8-17 14:38:02

我们知道$10^n-1$的对应值长度为9n,远远大于其它数.
所以对于这些数的倍数,它们的对应值不可能短于9n

gxqcn 发表于 2009-8-17 14:40:24

在你指定的范围,很可能结果为2999999997,长度为73
mathe 发表于 2009-8-17 14:05 http://bbs.emath.ac.cn/images/common/back.gif

那现有的程序对该数搜索的效率都还不够高。

我的程序则无法得到结果,因为它最多可搜到有效长度为64位,
如果要把它计算出来,则必须再追加一段类似的以64位value存储的代码。

mathe 发表于 2009-8-17 14:50:05

2999999997计算结果应该为82,而不是73.但是用gxqcn的程序为73,可能有溢出?
N=2999999997
1111111111111111110111111111111111111111111111111111111111111111111111111111111111
len 82

mathe 发表于 2009-8-17 14:52:20

原来如此
页: 1 2 [3] 4
查看完整版本: 求由0和1构成的最小十进制正整数,其是指定正整数的倍数