织女的六把黄金尺子问题
https://bbs.emath.ac.cn/data/attachment/forum/201412/15/030801aa88gn85w70aognn.pnghttps://bbs.emath.ac.cn/static/image/common/jh.gif传说玉帝赐给织女六把黄金尺子，我们称为金尺1、金尺2、…、金尺6。
在金尺k的正面有 k-1 条刻度线，将尺子划为k 段，在每段的中部标有该段的长度，皆为整数寸。
一把尺子的每两个刻度线（包括两端）间可直接量出一个长度。把两个刻度间包含的各段长度累加起来就行了。
易知，用金尺k 可直接量出 k(k+1)/2 个整数寸长度——仙匠有心，将这些整数寸都在金尺k的背面列出来了，从小到大。
所以，六把金尺的背面，合计标有单尺可直量的长度56个。
御赐金尺的妙处在于，这56个长度刚好是1至56寸。
也就是说，织女每次裁布想量出1至56寸的任何整数长度时，只需使用一把尺子就能直接量出。
至于该用哪把尺子，织女看看尺子背面就知道了。
利用编程手段可以找出六把金尺的各段长度吗？ 这个规模感觉计算机穷举没有问题，如果规模再大一些就比较困难了 尽管如此，其搜索规模依然是很大的。
以5个刻度的尺子为例。其全部方案有$56^6/2=15.4G $之多。 将规模降低，推算一下3把尺子能否度量1-10之间10个数的问题。 找到一个3把尺子的方案,见下
第1把尺子：3段长度分别为1,2,5, 可度量1，2，3，5，7，8
第2把尺子：2段长度分别为4，6, 可度量4，6，10
第3把尺子：长度为9, 可度量9 这是一个很松的上界。实际上，许多分支可以剪掉。比如所有各段的总长度不能超过56. 任何2段（每段指相邻2个刻度的部分）的长度必须互不相同。 暴搜3把尺子花了多久？ 解不唯一 为了编程方便，我先使用位置刻度，即刻度线到一端的距离。一端的刻度为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 程序还在运行中，总数可能不少
页:
[1]