首页 > Prolog解逻辑问题

Prolog解逻辑问题

我在写prolog程序解决这个问题。
题目是这样的:
有两个不相等的整数 x,y ,它们都大于 1 且和小于 100 ,x+y<100,数学家“和先生”知道这两个数的和,数学家“积先生”知道这两个数的积,他们进行了如下对话:
积先生:我不知道 x 和 y 分别是啥。
和先生:我知道你不知道,我也不知道。
积先生:我现在知道了。
和先生:那我也知道了。
那么,x 和 y 各是多少?答案我知道了是(4,13)下面有答案的链接,
这个我是找到的感觉最接近的答案
但是里面目前有几句话我不是很明白,为什么在第一次积先生说“我不知道 x 和 y 分别是啥。”之后可以得到这个结论:p does not contain a prime factor greater that 50.
还有为什么在何先生说完“我知道你不知道”之后,我们就能知道“s < 55 (for 53 is the smallest prime greater that 50)”这个条件?这个条件是怎么来的?
求教大神帮忙啊!感觉这题目好难懂!如果哪个高手知道更好的完整解题的方法,能全部解释一下,就更加万分感谢了!!!!!谢谢!!


你可以用你熟悉的语言,然后把所有大于1且和小于100的x,y的组合穷举出来。然后一一验证那些推论。

例如,

为什么在第一次积先生说“我不知道 x 和 y 分别是啥。”之后可以得到这个结论:p does not contain a prime factor greater that 50.

既然不知道分别是啥,那你就把p=x*y对应的x,y不唯一的都找出来,然后验证这些p中是否存在包含质因子大于50的数。


积的质因子不可能是大于50的(例如53,2x53已经大于100,所以如果有53就直接明确答案了)


没人出手?那我来。不给你发网上找的了,那些我都看不懂。

积先生:我不知道 xy 分别是啥。

积先生目前的底牌是知道积的质因子分解。他的话向和先生提供了这些讯息:
1. 积至少有3个质因子,且不能是n^3
2. 质因子不可能是大于50的(例如532*53已经大于100,所以如果有53就直接明确答案了)。可能的质因子只有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47这几个。
3. 考虑信息1后,积不可能是98*993*4这样的顶端值。此时可得到和的区间为[8,196]
4. 积不能是32*64,因为这也能直接得出结论。

和先生:我知道你不知道,我也不知道。

和先生目前的底牌是知道和以及积先生透露的信息。而他的话向积先生提供了这些讯息:

  1. 和不可能是一个大于53 + 3、小于97 + 100的数,否则必定能构造出一个大质数 + 合数的组合,可以被积先生一猜而中,和先生也就不能肯定地说出“我知道你不知道”。例如57 = 53 + 4时积先生必能一猜而中。此时和的区间缩小为[8,55]
  2. 排除所有两个质数的和,这也是会产生积先生猜中可能的情况。先排除所有偶数,再排除质数 + 2。此时和的取值可能为[11,17,23,27,29,35,37,41,47,51,53],只剩下11种。当然此时可判断,两数有且只有一个数是偶数。
  3. 和至少能有两种分解方式可以满足上述条件。(这条似乎已经没有进一步约束力了……)

积先生:我现在知道了。

积先生目前的底牌是知道积的质因子分解,知道了和的11种取值可能,他依此直接得到了答案。
他的话向和先生提供了这些讯息:

  1. 质因子构成的X、Y组合中,有且只有一组可以得到这11个和中的一种。
  2. 考虑积为2^n * 质数,由于只有一种拆分方式,是能够在这一步让积先生猜到答案的。可取值包括[4*7, 4*13, 4*19, 4*23, 4*31, 4*37, 4*43, 4*47, 8*3, 8*19, 8*29, 8*43, 16*7, 16*11, 16*13, 16*19, 16*31, 16*37, 32*3, 32*5, 32*19]这几种,全部保留。(我没弄错吧?眼花了已经。)。
  3. 考虑积的质因子含相同非2质数,则有[9,25,27,45,49]。可取值为[8*9, 32*9 ,16*25, 2*27, 8*27, 8*45, 4*49]。其中8*9=3*24,3+24=29,剔除;32*9=96*396+3=99,保留;16*25=80*580+5=85,保留;2*27=6*9=18*3,保留;8*27=24*9=72*3,保留;8*45=24*15=72*5=40*9,保留;4*49=28*7,28+7=35;剔除。
  4. 考虑积的质因子含不同非2质数,则有[15,21,33,35,39,51](45在上面用掉了)。可取值为[2*15, 8*15, 32*15, 2*21, 8*21, 16*21, ...省略]2*15=5*6,5+6=11,剔除;8*15=24*5=40*324+5=29剔除……(已经不用列下去了,因为这时候已经可以注意到一个问题了……)
  5. 没有下一种情况了。

和先生:那我也知道了。

  1. 要让和先生在这一轮猜到答案,那他手中的和有且只能有一组拆法,可以让积先生在上一轮命中,即拆成我们对上一轮分析中保留的值。
  2. 发现上面说的一个问题了没?上一轮2-4中保留的那些可取值,观察下它们的和。比如:2中[11 17 23 27 35 41 47 51 11 27 37 51 23 27 29 35 47 53 35 37 51],3中[41, 41, 29, 35, 53],4中的[...](不用列了,因为注意到即使有也一定会比17大)。我们可以发现,只有17这个和出现了一次,其它和都出现了两次或更多。要保证和先生在这一轮可以得出结论,必须剔除所有多选,于是和的取值只可能是17,对应的积为4*13

答案至此真相大白:两个数为413,和先生手中是17,积先生手中是52


什么,你说如何编程解决?对不起以上都都是我瞎编的,我已经编不下去了。
拜拜。

【热门文章】
【热门文章】