数学研发论坛

 找回密码
 欢迎注册
查看: 5204|回复: 51

[讨论] 织女的六把黄金尺子问题

[复制链接]
发表于 2014-12-15 03:09:30 | 显示全部楼层 |阅读模式

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

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

x
rulers6a.png
精华


传说玉帝赐给织女六把黄金尺子,我们称为金尺1、金尺2、…、金尺6。
在金尺k的正面有 k-1 条刻度线,将尺子划为k 段,在每段的中部标有该段的长度,皆为整数寸。
一把尺子的每两个刻度线(包括两端)间可直接量出一个长度。把两个刻度间包含的各段长度累加起来就行了。
易知,用金尺k 可直接量出 k(k+1)/2 个整数寸长度——仙匠有心,将这些整数寸都在金尺k的背面列出来了,从小到大。
所以,六把金尺的背面,合计标有单尺可直量的长度56个。
御赐金尺的妙处在于,这56个长度刚好是1至56寸。
也就是说,织女每次裁布想量出1至56寸的任何整数长度时,只需使用一把尺子就能直接量出。
至于该用哪把尺子,织女看看尺子背面就知道了。

利用编程手段可以找出六把金尺的各段长度吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 06:16:58 | 显示全部楼层
这个规模感觉计算机穷举没有问题,如果规模再大一些就比较困难了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 08:14:44 | 显示全部楼层
mathe 发表于 2014-12-16 06:16
这个规模感觉计算机穷举没有问题,如果规模再大一些就比较困难了


尽管如此,其搜索规模依然是很大的。
以5个刻度的尺子为例。其全部方案有  $56^6/2=15.4G $之多。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 08:52:01 | 显示全部楼层
将规模降低,推算一下3把尺子能否度量1-10之间10个数的问题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 09:47:09 | 显示全部楼层
找到一个3把尺子的方案,见下

第1把尺子:3段长度分别为1,2,5, 可度量1,2,3,5,7,8
第2把尺子:2段长度分别为4,6, 可度量4,6,10
第3把尺子:长度为9, 可度量9

点评

这是其中一个答案,答案数量不多,一只手可以数完。。。  发表于 2014-12-16 14:50
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 09:50:07 | 显示全部楼层
liangbch 发表于 2014-12-16 08:14
尽管如此,其搜索规模依然是很大的。
以5个刻度的尺子为例。其全部方案有  $56^6/2=15.4G $之多。

这是一个很松的上界。实际上,许多分支可以剪掉。比如所有各段的总长度不能超过56. 任何2段(每段指相邻2个刻度的部分)的长度必须互不相同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 10:48:20 | 显示全部楼层
liangbch 发表于 2014-12-16 09:47
找到一个3把尺子的方案,见下

第1把尺子:3段长度分别为1,2,5, 可度量1,2,3,5,7,8

暴搜3把尺子花了多久?

点评

3把尺子不止这个答案。。。穷搜应该是几ms的功夫。。。  发表于 2014-12-16 14:50
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 12:49:18 来自手机 | 显示全部楼层
解不唯一
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2014-12-16 12:50:44 来自手机 | 显示全部楼层
为了编程方便,我先使用位置刻度,即刻度线到一端的距离。一端的刻度为0,就省略了。
1 5 30 36 50 53;  9 21 37 47 55; 13 32 54 56; 11 44 51; 27 42; 39
求一个差分,就得到各段的长度。
1 4 25 11 14 3;  9 12 16 10 8;  13 19 22 2;  11 33 7;  27 15;  39
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-12-16 12:51:56 来自手机 | 显示全部楼层
程序还在运行中,总数可能不少
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2020-1-20 11:10 , Processed in 0.063716 second(s), 24 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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