数学研发论坛

 找回密码
 欢迎注册
查看: 18066|回复: 64

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

[复制链接]
发表于 2010-3-23 13:52:48 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
将 sqrt 1,sqrt 2, ... , sqrt 50 ( 1 到 50的平方根)分成两组,把每组中的数相加,得出两个数, 然后比较这两个数的差别。
问题: 用常见的计算机语言之一编写一个程序,找出最小的差别的两组, 要求该程序在计算机上运算得出结果所花费的时间不超过10秒。
精华


------->
  1. import Data.List

  2. samp = [sqrt x | x <- [1..50]]

  3. minDiff = (sort [(abs \$ (sum x) - (sum \$ samp\\x), x) | x <- subsequences samp]) !! 0
复制代码
这是最笨的方法(穷举), 如果你要试请先将50改成10, 否则后果自负

最佳答案,及程序源码 请见: 33# mathe
---gxqcn
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-23 17:17:49 | 显示全部楼层
可以这样来考虑吧,
$\sqrt{1}+\sqrt{2}+...+\sqrt{50}=239.0358006035207771$
一半等于 $119.5179003017603885$
问题变成我们从1~50中选一定数目的数使其最总和最接近119.5179003017603885
应该就是一个动态规划的问题了吧?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-23 17:26:16 | 显示全部楼层
非也。

$01$背包问题。

没有有效算法。

对于$N=50$,分$2$组,每组$25$,各有$2^25=33554432$种结果。

把$2$组结果列成两张表,对其排序。

接下来的工作你知道的。

就是顺序枚举第$1$张表取哪个数,然后倒序查看第$2$张表,保持结果最接近但不超过$119.5179003017603885$。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-23 18:17:43 | 显示全部楼层
3# KeyTo9_Fans
学习了,
不过题目中说分两组并没有说数目一样,所以情况还是要很大的吧。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-23 18:21:46 | 显示全部楼层
没说两组个数相等啊。
应该有些数学关系吧。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-24 00:14:13 | 显示全部楼层
$\sum_(n=1)^31 \sqrt{n}=117.651$

所以分组最偏也就是31项对19项了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-24 17:16:31 | 显示全部楼层
一个想法:
求出$sqrt(1),sqrt(2),...,sqrt(50)$,  将它们都乘以$10^6$,并向下取整,得到:
$a_{1},a_{2},...,a_{50}$
设一个分组为:
${b_{1},b_{2},...,b_{k}}$
如果${b_{1},b_{2},...,b_{k}}$是最优分组,我们可以知道$b_{1}+b_{2}+...+b_{k}$只能是119517900,119517901,...,119517949中的一个。
从上面的数值中选定一个,比如选119517900,然后,我们得到了:
$b_{1}+b_{2}+...+b_{k}=119517900$
选取一个素数模,比如选m=4999。
计算$a_{1}%m$,$a_{2}%m$,...,$a_{50}%m$, 119517900%m。
于是,我们可以通过动态规划来求出全部候选解。
对求得的候选解,我们再进一步验算就可以得到最优解了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-24 18:35:00 | 显示全部楼层
50个数中部分和有$2^50$中情况,所以平均来看应该存在一组数,同正好一半的误差小于$239/{2^50}$
所以上面的方法还远远不够
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-24 18:54:45 | 显示全部楼层
将50个数分为2组,考虑其中的一组数,最少有19个数,最多有25个数。
则总的可能组合为Combo(50,19)+Combo(50,20)+Combo(50,21)+Combo(50,22)+Combo(50,23)+Combo(50,24)+Combo(50,25)=5.89615E+14,和$2^50$=1.1259E+15,差别不大。求最优解依然没有突破复杂度$2^50$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-3-24 20:04:03 | 显示全部楼层
没想到要真正领会$3$楼中的Fans精神竟然如此困难。

无奈之下,只好用数据来说话。

在$\sqrt(1)$,$\sqrt(2)$,$\sqrt(3)$,...,$\sqrt(25)$共$25$个数中,取其子集,有$2^25$种选取方案。

把它们的和从小到大排序,得到第$1$张长度为$2^25$的表:

$0$
$\sqrt(1)$
$\sqrt(2)$
$\sqrt(3)$
$\sqrt(4)$
$\sqrt(5)$
$\sqrt(1)+\sqrt(2)$
$\sqrt(6)$
$\sqrt(7)$
$\sqrt(1)+\sqrt(3)$
$\sqrt(8)$
$\sqrt(1)+\sqrt(4)$
$\sqrt(9)$
$\sqrt(2)+\sqrt(3)$
$\sqrt(10)$
……
(中间省略$33554415$个数)
……
$\sqrt(2)+\sqrt(3)+\sqrt(4)+...+\sqrt(25)$
$\sqrt(1)+\sqrt(2)+\sqrt(3)+...+\sqrt(25)$

在$\sqrt(26)$,$\sqrt(27)$,$\sqrt(28)$,...,$\sqrt(50)$共$25$个数中,取其子集,有$2^25$种选取方案。

把它们的和从小到大排序,得到第$2$张长度为$2^25$的表:

$0$
$\sqrt(26)$
$\sqrt(27)$
$\sqrt(28)$
$\sqrt(29)$
……
(中间省略$33554425$个数)
……
$\sqrt(27)+\sqrt(28)+\sqrt(29)+...+\sqrt(50)$
$\sqrt(26)+\sqrt(27)+\sqrt(28)+...+\sqrt(50)$

好了。

在两张表中各取$1$个数,让这$2$个数的和最接近$\sqrt(1)+\sqrt(2)+\sqrt(3)+...+\sqrt(50)$的一半即可。

如果你说这个步骤需要$2^25$*$2^25$=$2^50$次运算,那Fans就无话可说了。

因为Fans认为这两个$2^25$是相加的而不是相乘的。

所需运算次数为$2^25$+$2^25$=$2^26$。

所以显然地,把$2^50$分成两个$2^25$相加是最佳方案。

如果不是$N=50$,而是$N=51$,那就没法均分,只好分成$2^25$和$2^26$了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-10-27 14:23 , Processed in 0.073901 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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