织女的六把黄金尺子问题

毒酒滴冻鸭

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

利用编程手段可以找出六把金尺的各段长度吗？

mathe

这个规模感觉计算机穷举没有问题，如果规模再大一些就比较困难了

liangbch

mathe 发表于 2014-12-16 06:16
这个规模感觉计算机穷举没有问题，如果规模再大一些就比较困难了

尽管如此，其搜索规模依然是很大的。
以5个刻度的尺子为例。其全部方案有  $56^6/2=15.4G $之多。

liangbch

将规模降低，推算一下3把尺子能否度量1-10之间10个数的问题。

liangbch

找到一个3把尺子的方案,见下

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

liangbch

liangbch 发表于 2014-12-16 08:14
尽管如此，其搜索规模依然是很大的。
以5个刻度的尺子为例。其全部方案有  $56^6/2=15.4G $之多。

这是一个很松的上界。实际上，许多分支可以剪掉。比如所有各段的总长度不能超过56. 任何2段（每段指相邻2个刻度的部分）的长度必须互不相同。

zeroieme

liangbch 发表于 2014-12-16 09:47
找到一个3把尺子的方案,见下

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

暴搜3把尺子花了多久？

mathe

解不唯一

mathe

为了编程方便，我先使用位置刻度，即刻度线到一端的距离。一端的刻度为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

mathe

程序还在运行中，总数可能不少