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

[讨论] 高德纳书中一道很普通的题目

[复制链接]
发表于 2010-3-27 14:15:03 | 显示全部楼层
你们的程序都精彩极了
Orz
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-29 13:02:40 | 显示全部楼层
KeyTo9
KeyTo9_Fan
Fans_Fans
组成了一个树形结构
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-29 13:08:10 | 显示全部楼层
literally and virtually exact
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-29 16:34:45 | 显示全部楼层
fans的方法很好!
zgg的想法总是和我很一致

fans的两个25个数的集合,我认为将一个改为hash可能会更快一些,
如zgg的第二个集合:1-5倍根号2,1-4倍根号3,1-3倍根号5,1-2倍的根号6,7,10,11
相加,小数部分共有(5+1)(4+1)(3+1)(2+1)(2+1)(2+1)(2+1)=9720种可能(包含了27个数的子集小数和的可能性),
对于119.517900301760320754230296092170,取51790030一段做成约100M的hash,
则遍历另外10^23个集合有约1/10000的几率命中,即可以得到约2^23/10000 =2^10个结果
再筛选
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-31 13:33:01 | 显示全部楼层
mathe提供的数据不是1-50的平方根啊,平方根乘以10^16数据应该是
70710678118654752,70000000000000000,69282032302755091,68556546004010441,67823299831252681,
67082039324993690,66332495807107996,65574385243020006,64807406984078602,64031242374328486,
63245553203367586,62449979983983982,61644140029689764,60827625302982196,60000000000000000,
59160797830996160,58309518948453004,57445626465380286,56568542494923801,55677643628300219,
54772255750516611,53851648071345040,52915026221291811,51961524227066318,50990195135927848,
50000000000000000,48989794855663561,47958315233127195,46904157598234295,45825756949558400,
44721359549995793,43588989435406735,42426406871192851,41231056256176605,40000000000000000,
38729833462074168,37416573867739413,36055512754639892,34641016151377545,33166247903553998,
31622776601683793,30000000000000000,28284271247461900,26457513110645905,24494897427831780,
22360679774997896,20000000000000000,17320508075688772,14142135623730950,10000000000000000

50个数的平方根和的一半是1195175767982871040
我算出来的解是一组是50,49,48,47,46,45,44,43,42,41,39,38,37,36,34,31,30,28,27
不知对不对,希望对照一下


原来mathe的精度约是10^18的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-31 14:35:29 | 显示全部楼层
他们的量化因子是
$2^56*10^{-17}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-31 22:12:52 | 显示全部楼层
有点难度   考虑考虑
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-5-2 08:10:55 | 显示全部楼层
好啊,期限定为一个月,就截止到2010年4月30日,给最佳答案提供者奖励50枚金币。
现在我把该主题醒目处理。
gxqcn 发表于 2010-3-26 11:15


现在已到期,即将兑现奖励。

求最优解不难,一下四组皆可
1, 4, 5, 7, 8, 9, 12, 13, 15, 16, 20, 25, 27, 30, 31, 33, 37, 38, 41, 43,44, 46, 47, 48, 49
1, 5, 7, 8, 9, 12, 13, 15, 20, 25, 27, 30, 31, 33, 36, 37, 38, 41, 43, 44, 46, 47, 48, 49
1, 4, 7, 8, 9, 12, 13, 15, 16, 25, 27, 30, 31, 33, 37, 38, 41, 43, 44, 45, 46, 47, 48, 49
7, 8, 12, 13, 15, 16, 25, 27, 30, 31, 33, 36, 37, 38, 41, 43, 44, 45, 46,47, 48, 49
和为
119.5179003017603207542302960921700499402435778084733414943130797735074
所有和的一半为119.5179003017603922470202231131221884062508285908309350855973734662694
误差为$7.15*10^-14$
mathe 发表于 2010-3-26 13:46


从现有结果看,最佳答案是上述帖子。

现有7天公示期,如果之前有得到更好结果的请回复说明;
在公示期间,若有更好的结果,将另得100枚金币的奖励!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-5-2 20:41:32 | 显示全部楼层
几点建议:
1、由于正值五一节,可能有些人不便上坛来,或者来了也只能像我这样看一看,所以公示期是否适当延长几天。(mathe别拿砖拍我
2、公示期间最好置顶,免得被挤下去了。
3、我这一帖看完后也最好是删掉,哈哈哈。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-5-3 20:08:03 | 显示全部楼层
好建议,再醒目置顶一周。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 20:53 , Processed in 0.045447 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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