Bing Yee程序人生

关注互联网产品技术学习,应用开发~

这辈子,我还能搞懂吗?

2011-11-26 10:22:07 类别:经验分享
摘要:孙膑,庞涓都是鬼谷子的徒弟;一天鬼出了这道题目:他从2到99中选出两个不同的整数,把积告诉孙,把和告诉庞。 庞说:我虽然不能确定这两个数是什么,但是我肯定你也不知道这两个数是什么。 孙说:我本来的确不知道,但是听你这么一说,我现在能够确定这两个数字了。 庞说:既然你这么说,我现在也知道这两个数字是什么了。 问这两个数字是什么?为什么?

 1、庞涓能确定孙膑肯定不知道这两个数,可以有这样几个推论。
  (A)庞涓手上的数字是5-197之间的数字。
  (B)庞涓的和数一定不能拆成两个质数之和,否则就不会有确信。这可以分解为两点:
  庞涓手上不是偶数,只可能是奇数,因为任意大于4偶数能被拆成两个奇质数之和,这是由歌德巴赫猜想来保证;
  并且庞涓手上的奇数不是2+质数。举例:如果庞涓手上是28,可以拆成11+17,当孙膑拿到了181这个积,
  马上就可以猜出鬼谷子给他的两个数是11和17,与庞涓肯定孙膑不知道这两个数相矛盾,因此将所有偶数排除。
  举例:当庞涓手上的数为质数+2时,例如21,而正好是19+2,那样孙膑手上的数是38,只有一种分解方法2*19,
  因此孙膑同样一开始就能确定这两个数字。
  (C)庞涓的和数一定不是大于53的奇数。因为大于53的奇数始终能够拆成偶数和53(是质数)的乘积,
  这个乘积只能唯一的推断出53和该偶数的乘积,否则就要大于99了。另外97是质数,
  同理应该排除97+2到97+98的所有奇数。最后剩下的是99+98的奇数,因为都是最大的数,
  孙膑本来就可以推理出来,与孙膑本来不知道的前提相矛盾,自然排除了。
  因此由此可以排除超过53以上的所有奇数。举例:如果庞涓手上的数字是59,那有一种可能是53+6,
  当孙膑拿到318时也只有一种分解方式是53*6,因为106*3和159*2中的106和159都大于了99这个最大的数字,
  因此这与孙膑事先不能肯定相矛盾。同理可以推理到195=97+98这中间的所有奇数都被排除,因为97是质数。
  因此,当庞涓手上是53以上的奇数不会有这种把握孙膑肯定不知道这两个数。
  (D)满足以上条件的这样的数字仅有10个:11,17,23,27,29,35,37,47,51,53。
  2、孙膑知道自己手中的积,并说本来不知道,但现在知道了。意味着,
  孙膑看了自己手上的积后分解因式对应的所有组合的和,只可能是上述10个数中的一个。
  也就是10个和数拆开的乘积不于其他和数拆开乘积重合的才可能是孙膑的积。
  从这句话可以得出能够相乘等于孙膑手上积的数里面,有且仅有一对是一奇一偶,别的都是两偶。所以由这个推论可以得出这个奇数肯定是个质数。而这个偶数肯定是只能被2整除(也就是说它是2的N次方)。也就是说鬼谷子选的两个数(假设是a,b,不分顺序)会满足 :a是个质数 , b是2的N次方(N是大于1的整数)。
  这种积有许多种,关键是庞涓的第三句话。
  3、庞涓是知道自己手中的和数,当孙膑说了这句话的时候,庞涓说也知道这两个数字了,
  那庞涓手上的和数有一个特点,就是除一个例外的可能积,其他可能的积都无法满足前面所言,
  否则庞涓没有这种自信。也就是在10个和数中找出积的数组合中只有唯一一对数可以满足前面的条件。
  这时需要结合第二个条件,怎么利用这个条件呢?以17做为例子:
  假设分解为3+14,那么积为42,而42=3*14=2*21=6*7,对应的和有17,23,13
  而当中的17和23均为候选解,也就是说假如孙膑手上的数是42,他就无法知道正确的分解,
  所以17不能分解为3+14。类似地可以构造以下这个可以满足第二条件的分解列表:
  11的可能的分解:(4,7),(3,8),
  17的可能的分解:(4,13),
  23的可能的分解:(7,16),(4,19),
  27的可能的分解:(11,16)(8,19)(4,23)
  29的可能的分解:(2,27)(3,26)(13,16)
  35的可能的分解:(16,19)(4,31),(3,32),
  37的可能的分解:(8,29)(5,32),
  47的可能的分解:(16,31)(4,43),
  53的可能的分解:(2,51)(16,37)
  当中只有17,29,41,53有唯一可行的分解,所以庞涓才可能确定自己手上的数。
  所以本问题的答案为(4,13)
  具体是哪一个,得看孙和庞手上的数了
  下面是我用JAVA的求解过程: 作者(koolening)
 

 class GuiGuZi { 
  public static void main(String [] args){ 
  new GuiGuZi().locate(); 
  } 
  public void locate(){ 
  for(int i = 2;i<=53;i++){ 
  if(i%2==0) continue; 
  if(!isPrimzahlenSum(i)) continue; 
  if(factoring(i)>0){ 
  int a = factoring(i); 
  int b = i - a; 
  System.out.println("鬼谷子选的数是" + a + "和" + b); 
  } 
  } 
  } 
  public boolean isPrimzahlen(int a){ //检验是不是质数 
  if(a==2) return true; 
  for(int i=2;i<=(int)Math.sqrt(a);i++){ 
  if(a%i==0) return false; 
  } 
  return true; 
  } 
  public boolean isPrimzahlenSum(int sum){ //检验两数之和能不能被分解为两个质数 
  for(int i=2;i<=99;i++){ 
  if(isPrimzahlen(i)) 
  for(int j=2; j<=99;j++){ 
  if(i==j) continue; 
  if(isPrimzahlen(j)){ 
  if((i+j)==sum) 
  return false; 
  } 
  } 
  } 
  return true; 
  } 
  public int factoring(int sum){ //检验是不是庞的数是不是能分解成 质数2的N次方,并且是不是唯一的 
  int count = 0; 
  int a = -1; 
  for(int i=2;i<sum-2;i=i*2){ 
  if(isPrimzahlen(sum-i)) { 
  count++; 
  a = i; 
  } 
  } 
  if(count==1) return a; 
  else return -1; 
  } 
  } 

 

2692次阅读  标签:
下一篇:Access 2007 操作或事件已被禁用模式阻止如何解决?
上一篇:[分享]巧用SQLServer 作业 解决数据校验功能

共11条评论

cykzbnekz(1楼)-2014-4-26 10:51:11
审核中

goxqprmb(2楼)-2014-4-26 11:22:37
审核中

发表评论

文章分类


友情链接