大家练练手,征集下面这个小程序的算法!!!(很有趣的阿!!)

Question

1:由于x,y>1及甲说的第一句话,所以甲手中的数具有以下的性质:
     a: 4应该是它的一个约数,3也因该是它的一个约数.但,4,3只要至少一 
      为甲手中数的约数就可!(因为甲不能自己听过手中的数确定这两 个数,  所以这个数最少有2种可能的结果,不算1*n=n这种)这样我们就考虑  6,8,9,12,15,16,18,20,24等等
   b:假如甲的数为6,则只有2*3这种情况,(1*6不合题意)
     假如甲的数为6,则只有2*4这种情况,(1*8不合题意)
     假如甲的数为6,则只有3*3这种情况,(1*9不合题意)
2:现在考虑甲手中的数是12,此时甲猜x,y的情况为:3*4,2*6这两种情况
 所以他还不能确定
3:乙是知道自己的数是多少,若为7的话(这个要和假设的甲的数相符),乙认为情况为2+5,3+4;但是如果是2+5的话,甲就可以知道是x,y为2,5了,甲就不会说自己不知道了,如果是3+4的话乙就知道x,y为3,4,就他自己不会说也不知道了
再考虑乙手中的数为8,则有以下的情况:2+6,3+5,4+4;
   a:2+6的话,乙认为甲的数为12,甲2*6=3*4两种情况不能确定,有可能!
   b:3+5的话,乙如上面所说,甲的数为15,甲就知道是3和5了
   c:4+4的话,乙认为是可能的,甲的4*4=2*8两种情况不能确定,也有可能!
所以乙是8的话,只认为有2,6和4,4两种情况,自己不能确认!
4:乙说也自己不知道,也知道甲不知道!所以甲通过这句话,可以把乙为7的可能排除!只有乙为8了,剩下的解方程,得出x,y为2,6
以上是个人想法,不知道大家觉得怎么样!??
至于甲为12以后的我就没算了!(我是想可能只有一个解,也就懒的算了)
欢迎大家指点!  
   
   

Answer 1

噢，错了错了！
再看一编 Jarky(武阳松清) 的贴子才发现原来有一个很重要的地方没考虑...
：P
出丑咯

Answer 2

to: maoxianwang(大大㊣BETAⅡ我想赶快结婚那样就可以) 
 我说过有人看过的,既然你知道把算法写出来把!
你看豆沙包就有自己的看法!

Answer 3

不过我再考虑一下，发现 Jarky(武阳松清) 的分析有点问题 
题目里面提到只是甲知道乙不知道，而乙在甲说不知道以前并不知道甲不知道(至少题目没说明)。那样的话，其实 3 4也是满足得。
因为甲拿着12 知道可能是 3 2*2=4 或者 2 2*3=6 ，而这两组的和是7 和 8 都
都不可能让乙马上知道是那两个数。

Answer 4

我总觉得越想脑袋里越乱。
to:Jarky (武阳松清) 你认为解唯一嘛？

Answer 5

转一篇:(另好象以前的数据算法版上也讨论了，不知道最后讨论出来没有)S先生与P先生我们来看看一道世界闻名的逻辑难题吧，它可比前面的五五迷题要困难许多哟。这道题目来自美国斯坦福大学的麦卡锡教授----S先生与P先生谜题。题目：S先生与P先生谜题 设有两个自然数X、Y，2<=X<=Y<=99,S先生知道这两个数的和S，P先生知道这两个数的积P，他们二人进行了如下对话： S：我确信你不知道这两个数是什么，但我也不知道。P: 一听你说这句话，我就知道这两个数是什么了。 S: 我也是，现在我也知道了。现在你能通过他们的会话推断出这两个数是什么吗？（当然，S和P先生都是非常聪明的）这道题目乍看起来无法入手，当然就更不要说使用Prolog编程解决了。所以在介绍编程算法以前，有必要对这个题目做一下研究。首先，S先生只知道这两个数的和，那么他为什么能够确信P先生不知道这两个数呢？我们先考虑在什么情况下P先生能够通过两个数的积推出这两个数来，当然，还有前提条件X、Y为自然数，且2<=X<=Y<=99。先举个例子，假设P先生知道的数为14，他就会有如下的想法：“14可以是1*14，或者2*7，但是因为条件：2<=X<=Y<=99，所以X只能是2，而Y只能是7。”看出门道来了么？我们假设P先生对自己的数进行的分析叫做P分析，而S先生对自己的数的分析叫做S分析。这个假设有点难懂。我们来看个实例：若P先生的数为32，那么P先生的分析有如下两种：2*16，4*8。若S先生的数为12，那么他有如下的分析：2+10，3+9，4+8，5+7，6+6。如果P先生的分析是唯一的，那么P先生就能够知道这两个数X、Y了，例如14。我们再来看第一个条件：S：我确信你不知道这两个数是什么，但我也不知道。它的意思就是：S先生的每一个S分析为X1与Y1，X1与Y1的积的P分析都不唯一。太拗口了，还是来举个例子来说明吧。假设S先生知道的数为11，请看下图的分析过程：  上图显示的是S先生的分析过程。他先对自己的数11进行S分析，有四种情况：2+9、3+8、4+7、5+6（图中的第二层），而这些分解所对应的乘积P分别为：18、24、28、30，图中的第三层。最后对每一个乘积P进行P分析，得到上图的第四层。我们发现任何一个S分析所对应P分析都不只一个，所以S先生能够确信P先生绝对不能直接得出X和Y这两个数来。作为比较，我们再来看看S先生的数是10的情况。  可以看出，如果这两个数是3、7，或者5、5，那么P先生就可以直接根据他们的乘积得出这两个数。这就是说S先生不能确信P先生不知道这两个数。注意：S先生是确信P先生不知道，所以只要存在一种情况使得S的分析的P分析唯一，那么S先生就不能说第一句话。如果我们手工对所有的数进行分析，我们发现：S只能是下面的几个之一：SA={11，17，23，27，29，35，37，41，47，51，53}那么X和Y就只能是下面的集合中之一。A={(2,9),(3,8),...,(5,6),(2,15),(3,14),(8,9),...}看懂了么？下面将更加复杂，所以你一定要完全搞懂之后，再往下看。当P先生听了S先生的这句话后，他就能够知道这两个数了，为什么？首先，我们知道P先生的P分析是不唯一的，有两种以上。但是，当他知道这两个数的和只能在集合SA中时（由于P先生很聪明，我们以上的分析他也能想出来），他发现他的数的P分析之和只有一个在集合SA中，所以他就能够确定这两个数了。是不是又有点糊涂了？我们来看个例子。假设P先生的数是18，那么他有两个P分析：2*9、3*6，如下图：我们可以看到11是SA中的数，9不是，所以如果P先生的数是18，那么在听了S先生的话后，他就能够得出X和Y了，即2和9。如果P先生的数是30，那么有下图：11和17都在集合SA中，所以P先生不能确定X和Y，因此可以排除积为30的数。这样我们又能够缩小我们的搜索范围，假设缩小后的范围是：B={(2,9),(3,8),...,(3,14),...}注意我们排除了A中的(5,6),(2,15),(8,9)等组合。最后S先生也知道这两个数了，这说明......好了，不管它说明什么了，反正大概的思路你已经清楚了。我们看到这个例子和前面的五五迷题有相似之处：都是条件约束问题。根据所给出的条件我们可以一步一步地排除一些情况，直到最后所剩下就是我们的答案。那么我们的Prolog程序也有相似之处：使用“选择再校验”的方法。先来计算一下工作量：M和N的所有组合情况有：98+97+96+...+1=4851种可能情况。不算很大，所以完全可以使用穷举法，不过比起五五迷题来说可是多了好多倍啊。先来编写能够穷举所有情况的谓词。get_integer(L,H,X):-L>H,!,fail.
get_integer(L,H,L). 
get_integer(L,H,X):-L1 is L+1,get_integer(L1,H,X).谓词get_integer/3，返回从L到H的所有整数。第一个子句考虑L>H的情况，当然是失败，并且使用截断，不需要再考虑下面的子句了。（边界条件）第二个子句直接返回L，它是第一个数。第三个子句递归调用get_integer/3，不过下限加了1。好了我们来看看它的功能：?- get_integer(3,7,X).X = 3 ;X = 4 ;X = 5 ;X = 6 ;X = 7 ;
no不错，正是我们需要的。再让我们同时使用两个get_integer/3，来产生所有的X和Y的组合。?- get_integer(3,5,X),get_integer(X,5,Y).X = 3
Y = 3 ;
X = 3
Y = 4 ;
X = 3
Y = 5 ;
X = 4
Y = 4 ;
X = 4
Y = 5 ;
X = 5
Y = 5 ;
no
好了，选择部分做好了。再来看看我们的程序中要经常用到的一个谓词。% find(A,B,C).
% find寻找在A到B之间，B的可能的因子C。之所以称之为可能，是因为find并不测试B是否能整除C。
find(Lb,Z1,M2):-
Q is Z1 divs Lb,
Q =< Lb,
!,fail.
find(Lb,Z1,Lb).
find(Lb,Z1,M2):-
Lb1 is Lb+1,find(Lb1,Z1,M2).由于在P分析中需要使用因子分解，所以就先编写了一个find/3谓词，它并不能真正找到B的因子，而只是找出B的可能的因子，什么叫做可能？看一个例子就明白了。?- find(1,50,X).X = 1 ;X = 2 ;X = 3 ;X = 4 ;X = 5 ;X = 6 ;
no为什么只有1--6是50的可能的因子？因为50开根号为7.07，所以它的因子就一定有一半在1---6之间，而另外一半只需使用50除以这些因子就可以得到。下面开始正式编写三个条件：% 条件一，也就是S先生的第一句话。
% 条件一：把和S分成任意的两个数M和N的和之后，再判断M和N的乘积P是否只有M和N这一对因子。
%         如果只有一对因子，则S先生不能肯定 P先生不能说出这两个数。所以失败。
cond1(Lb,Hb,X,Y):-
  %Lb与Hb为X、Y的取值界限，本题中为2和99，X和Y就是要判断的一组可能情况。
     S is X+Y,            % S为S先生知道的数---两个数之和。
     H is S divs 2,  
     get_integer(Lb,H,M),
     N is S-M，           % M和N就是S先生的S分析，这应该不难理解。
     unique_d(Lb,Hb,M,N)，% 本句测试M和N的积的P分析是否唯一,
     !,fail.              % 唯一，就失败了。cond1(Lb,Hb,X,Y).% 否则，就成功，条件一通过。
 % 判断M和N的乘积P是否只有M和N这一对因子。
unique_d(Lb,Hb,M,N):-
not_unique_d(Lb,Hb,M,N),
!,fail.
unique_d(Lb,Hb,M,N).  %采用了截断那一章所介绍的否定方法，当然也可以直接使用内部谓词not/1。not_unique_d(Lb,Hb,M,N):-  %如果M和N的乘积P的P分析不唯一就成功，即M与N的乘积P有其它的因子。
P is M*N,      %首先，得出M与N的乘积P。
find(Lb,P,V),  %再来找P的其它分解，
V =\= M,       %V不等于M，(M为小的那个因子）
0=:=P mod V.   %但是，V也是P的因子(此句的意思是P除以V的余数为0)，所以不唯一，成功。% 条件二
%  把X和Y的积P，分成另外一组因子M2和N2后，再用条件一判断。
%  如果条件一成功，则表示P先生的P分析有两个满足条件一，(此处已经假设X，Y满足条件一）
%  所以P先生就不能通过S先生的第一句话得出这两个数。
%  则条件二失败。
cond2(Lb,Hb,X,Y):-
P is X*Y,
find(Lb,P,M2),
M2=\=X,
0 =:=P mod M2,
N2 is P divs M2,
N2 < Hb,
cond1(Lb,Hb,M2,N2),
!,fail.
cond2(Lb,Hb,X,Y). % 否则，就成功，条件二通过。% 条件三
%  同条件二一样编写，如果S先生的S分析除了X和Y以外，
%  还有可以满足条件二的S分析(M3,N3)，(此处已经假设X，Y满足条件二）
%  就是说S先生不能通过前面的对话确定这两个数。
%  则条件三失败，否则成功。
cond3(Lb,Hb,X,Y):-
S is X+Y,
Q3 is S divs 2,
get_integer(Lb,Q3,M3),
M3=\=X,
N3 is S-M3,
cond2(Lb,Hb,M3,N3),
!,fail.
cond3(Lb,Hb,X,Y).看明白了么？这道题本来就是一道世界性的难题，所以就算讲的再清楚，你还是要好好集中注意力才能真正懂得这道题的深奥之处。我们看到条件二中使用了条件一，而条件三中又使用了条件二。这是很明白的，我们知道，S先生和P先生之所以能够得出这两个数，是因为每一步都没有其它的情况满足。例如：如果P先生的P分析有两个满足条件一，那么就算P先生分析了S先生说的第一句话，他也不能区别出这两个分析哪一个才是真正的解。同理，S先生的S分析也只能有一个满足条件二时，他才能得出这两个数。好了，最后我们把选择部分与校验部分连接起来。% 主程序，调用方法：puzzle(2,99,X,Y).
puzzle(Lb,Hb,X,Y):-
get_integer(Lb,Hb,X), 
get_integer(X,Hb,Y),  %首先生成可能的组合情况。
cond1(Lb,Hb,X,Y),
cond2(Lb,Hb,X,Y).
cond3(Lb,Hb,X,Y),!.    %再用三个条件分别测试。这个主程序很好理解，就不多讲了，最后的那个！ (cut)，表示我们只需找到一个解（也只可能有一个解）就够了。我们来运行一下程序，看看这两个烦了我们半天的数到底是什么？?- puzzle(2,99,X,Y).X = 4
Y = 13 ;
no
呀，我

Answer 6

http://go4.163.com/cdtzx/htmindex.htm
http://go4.163.com/cdtzx/bcbd.htm
http://go4.163.com/cdtzx/prolog/bcpsap.htm