秤重问题

最近与朋友谈一些秤重问题，如从12枚金币中经由秤3次而找到其中1枚伪币，或者从8个球中经由秤2次而找到其中1个比较重的球。觉得像这类问题，要找到一个答案都比较简单。不过，归纳之後发现，同一个方法可能解得超过一种情况，例如秤8个球，第一次先拿6个平分为二边来秤，如果平衡则秤其他2个球，否则选比较重的一边3个球再秤一次做判断。同样这个秤重次数，可以决定7个球挑1个球，也可以决定8个球挑一个球的结果。相对来讲，给12枚金币秤3次找1枚伪币，可以找到好几种秤法。

我想问一个问题是，给N件同类物品，其中有1件物品的重量较不同，人要求你秤M次找出那一件重量较特别的物品，总共可以找到多少种秤重次序？写成prolog程序是什麽样子？

注：粗浅想到的原理，我想，秤1次可以决定多少件物品挑1件的情况？秤1次可以决定2件物品挑1件，以及3件物品挑一件。此外，没了。我会从这样的想法开始来解这个问题。

yauhsien 写道:最近与朋友谈一些秤重问题，如从12枚金币中经由秤3次而找到其中1枚伪币，或者从8个球中经由秤2次而找到其中1个比较重的球。觉得像这类问题，要找到一个答案都比较简单。不过，归纳之後发现，同一个方法可能解得超过一种情况，例如秤8个球，第一次先拿6个平分为二边来秤，如果平衡则秤其他2个球，否则选比较重的一边3个球再秤一次做判断。同样这个秤重次数，可以决定7个球挑1个球，也可以决定8个球挑一个球的结果。相对来讲，给12枚金币秤3次找1枚伪币，可以找到好几种秤法。

我想问一个问题是，给N件同类物品，其中有1件物品的重量较不同，人要求你秤M次找出那一件重量较特别的物品，总共可以找到多少种秤重次序？写成prolog程序是什麽样子？

注：粗浅想到的原理，我想，秤1次可以决定多少件物品挑1件的情况？秤1次可以决定2件物品挑1件，以及3件物品挑一件。此外，没了。我会从这样的想法开始来解这个问题。

"总共可以找到多少种秤重次序"是什么意思？
你是说总共有多少种解法能找出那个不同重量的物件是吧？

那假如有8个，编号1-8，我先把1-6摆上去，留7、8，
和我先把3-8摆上去，留1、2，这应该算两种还是一种？

其实就是想问这8个是看成是相同的还是不同的。

抽空再想了一会儿，觉得这问题我一开始定义得较大。目标只是搜寻全部可以的秤重法。

这样会是个消耗战：

代码:

weight(0, Weighting_sequences) :- !, Weighting_sequences = [].
weight(1, Ws) :- !, Ws = [].
weight(2, Ws) :- !,
    Step = [1,1], Ws = [[Step]].
weight(3, Ws) :- !,
    Step = [1,1], Ws = [[Step]].
weight(N, Ws) :-
    (Take=2; Take=3), N1 is N-Take, weight(Take, [S]),
    weight(N1, Sqs),
    bagof(Z, (member(S1,Sqs), Z=[S|S1]), Ws).

可若要只求最佳解，基本模式不外乎分成2群或3群。当物件数量是偶数时，分成2群放到秤子二端。当物件数量是奇数，分成接近均等的3群，可以决定伪币放在上秤子的二端之一、或是第三群，或者是三群之外的另一个。当分为3群时，若上秤子的二群各自数目为N，则第三群的数目可以在1~N+1之间。

由以上基础，一则问题若说「给M个物件，要以秤子秤最少次找到其中唯一一枚伪币，问需要秤多少次？」解答是肯定一个，解题程序也很好写。而前次所提的问题是「给M个物件，限定以秤重N次找到其中唯一一枚伪币，问总共可以有几种秤法？」则是像以上 weight/2 所讲的，求出结果是一列一列解题步骤，解题步骤彼此有先後次序不同。