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
原来如此