Prolog 人工智能语言中文论坛---打造优质Prolog学习交流园地

一个供Prolog爱好者学习与交流的地方


您没有登录。 请登录注册

秤重问题

浏览上一个主题 浏览下一个主题 向下  留言 [第1页/共1页]

1 秤重问题 于 周三 十一月 21, 2012 5:30 pm

最近与朋友谈一些秤重问题,如从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件物品挑一件。此外,没了。我会从这样的想法开始来解这个问题。

查阅用户资料 http://yauhsien.wordpress.com

2 回复: 秤重问题 于 周四 十一月 22, 2012 1:21 am

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个是看成是相同的还是不同的。

查阅用户资料 http://prolog.longluntan.net

3 回复: 秤重问题 于 周五 十一月 23, 2012 10:55 pm

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

这样会是个消耗战:
代码:
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 所讲的,求出结果是一列一列解题步骤,解题步骤彼此有先後次序不同。

查阅用户资料 http://yauhsien.wordpress.com

浏览上一个主题 浏览下一个主题 返回页首  留言 [第1页/共1页]

您在这个论坛的权限:
不能在这个论坛回复主题