奇尺问题

镜子580

奇尺问题

1、在9cm长的直尺上只标记3个刻度，即可把1-9之间的正整数全部测量出来。
2、在10cm长的直尺上只标记3个刻度，要全部测出从1到10的整数长度是不可能的。
3、在12cm长的直尺上如果只标记3个刻度，可以测出10种不同的长度。
4、如果要想在12cm长的直尺上测出1-12之间的全部长度，至少需要标记4个刻度。
5、在13cm长的直尺上只需要标记4个刻度，就可以测出1-13之间的全部长度。

（1=1，2=2；3=13-10；4=6-2；5=6-1；6=6；7=13-6；8=10-2；9=10-1；10=10；11=13-2；12=13-1；13=13）

根据以上命题原则，请各位贤人继续努力找出直尺长度36cm以内的用最少刻度测出直尺全部尺寸的标注刻度方法，每把尺子的刻度数不要超过8个。当然如果还有精力还可以继续寻找最佳刻度，只是尺子太长了手里不太好拿。


直尺13刻度标注示意图：


[ 本帖最后由 镜子580 于 2009-6-28 20:46 编辑 ]

superacid

这是一个NP问题，好像没有理论方法...

金眼睛

画个图吧  ：）

镜子580

还是编程法算得又快又准，可惜没学会。不妨把标法都贴出来欣赏一下。

金眼睛

我觉得提加减容易使人混淆，其实就是N以内的正整数长度均能利用刻度线一次量出。

可以有两种表述形式：
1：像LZ那样用刻度线表示，即要求，刻度线之间的差的绝对值能够覆盖1~N，是减的概念。
2：如果用各段的长度表示，则要求，各个连通段（说白了就是形成一团）的长度能够覆盖1~N，是加的概念。

给出36单位长度尺的分法：
1：用刻度表示
解1：0—1—3—6—13—20—27—31—35—36
解2：0—1—5—9—16—23—30—33—35—36
2：用各段长度表示
解1：1—2—3—7—7—7—4—4—1
解2：1—4—4—7—7—7—3—2—1               即是12楼所说的镜像情况。

我是用程序算的，算法不是很复杂，36以下的都可以很快得到的，期待高手介绍一下理论上的方法！o(∩_∩)o...

edmond-xym

原帖由 骰迷 于 2009-6-28 15:35 发表
樓上，減是沒問題，加就不能了。其實不是什麼加減，而是兩個刻劃之間的距離。

那LZ的题目没有说清楚啊。没有了加法，反倒不难了。这种人为的规定只能使得题目不严谨。

[ 本帖最后由 edmond-xym 于 2009-6-28 23:44 编辑 ]

镜子580

6楼的理解正确。我在题目中增加了一个举例，只能用减法。

金眼睛

恩，很有意思的题目，LZ的意思是长度必须一次量出，不可累加亦不可相减。

否则，可以利用1，2，4，8，16 ……   这个数列来解决所有整数尺寸的度量，这倒是有助于商品化，呵呵！

因为任何一个10进制数可以表示为2进制数，1的位置代表加，0的位置代表不加，就可以了。

比如6为110，110—421，也就是用4+2即可度量出来。

镜子580

非常感谢提供相关资料！不过还是自己能研究出来才有趣味，国外的研究总是领先我们一步，我辈还需努力啊，但愿有后起之秀，能人辈出！（说明一点：我是把原来的英寸改为cm了）

superacid

我在数学协作体做过36cm这道题，要8个刻度，只有两个解（互为镜像）