奇尺问题

榕城之蓝

对啊，其实只要有1就可以测出全部的长度，只是费事一点。

superacid

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

镜子580

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

金眼睛

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

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

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

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

镜子580

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

edmond-xym

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

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

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

金眼睛

我觉得提加减容易使人混淆，其实就是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...

镜子580

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

金眼睛

画个图吧  ：）

superacid

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