高德纳书中一道很普通的题目

wayne

你们的程序都精彩极了 Orz

litaoye

KeyTo9 KeyTo9_Fan Fans_Fans 组成了一个树形结构

wayne

literally and virtually exact

shshsh_0510

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个结果 再筛选

qianyb

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的

wayne

他们的量化因子是 $2^56*10^{-17}$

dalaopeng

有点难度 考虑考虑

gxqcn

好啊，期限定为一个月，就截止到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枚金币的奖励！

hujunhua

几点建议： 1、由于正值五一节，可能有些人不便上坛来，或者来了也只能像我这样看一看，所以公示期是否适当延长几天。（mathe别拿砖拍我） 2、公示期间最好置顶，免得被挤下去了。 3、我这一帖看完后也最好是删掉，哈哈哈。

gxqcn

好建议，再醒目置顶一周。