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

[擂台] 求由0和1构成的最小十进制正整数,其是指定正整数的倍数

[复制链接]
 楼主| 发表于 2009-8-17 11:27:49 | 显示全部楼层
附带两个新问题:

限定输入的N范围为:1~4294967295,请问:
1、对应结果字串中含“0”的数目最大可为多少?
2、当N与10互素且(N+1)不为10的整数次幂时,对应结果位数最长可达多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-8-17 11:38:53 | 显示全部楼层
关于第2个问题,我现在有一个比较大的结果:
N=4294960461
1101111111111010111111111111001101111101111
它有43位,不知最长的可就是它了?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-8-17 13:48:11 | 显示全部楼层
接着搜了几个小时,又得到几个返回结果比较长的数据,它们均有43位:
  1. N=4294960461
  2. 1101111111111010111111111111001101111101111

  3. N=4294940463
  4. 1101110111100111111110110111111111111011111

  5. N=4294880469
  6. 1100111111111111000111111111101111111111011

  7. N=4294860471
  8. 1101111100011111111111111011011111101111111
复制代码
14# 编译好的程序运行,耗时依次如下:
search_pid21021.exe(代码见  2# ):21156ms、19469ms、19875ms、23750ms
search_pid21101.exe(代码见 14#):12719ms、12578ms、12422ms、12782ms
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-8-17 14:03:37 | 显示全部楼层
69999993
的结果可以达到64位
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-8-17 14:05:51 | 显示全部楼层
在你指定的范围,很可能结果为2999999997,长度为73
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-8-17 14:08:15 | 显示全部楼层
N=69999993
1111111111111111111111111111011111111111111111111111111111111111

这么奇妙的数据是如何得到的?理论推导出来的吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-8-17 14:38:02 | 显示全部楼层
我们知道$10^n-1$的对应值长度为9n,远远大于其它数.
所以对于这些数的倍数,它们的对应值不可能短于9n
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-8-17 14:40:24 | 显示全部楼层
在你指定的范围,很可能结果为2999999997,长度为73
mathe 发表于 2009-8-17 14:05


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

我的程序则无法得到结果,因为它最多可搜到有效长度为64位,
如果要把它计算出来,则必须再追加一段类似的以64位value存储的代码。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-8-17 14:50:05 | 显示全部楼层
2999999997计算结果应该为82,而不是73.但是用gxqcn的程序为73,可能有溢出?
N=2999999997
1111111111111111110111111111111111111111111111111111111111111111111111111111111111
len 82
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-8-17 14:52:20 | 显示全部楼层
原来如此
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 13:52 , Processed in 0.042453 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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