智力吧 关注:36,876贴子:250,778

回复:经典高难度智力题之《死囚试毒酒》

只看楼主收藏回复

这是40人中级解法(请用取代功能把“~”符号全部改成空格):
from random import randrange
def to_b4(n):
~~~~return [n/4**k%4 for k in range(5)]
def fr_b4(li):
~~~~return sum([li[k]*4**k for k in range(5)])
def drink(p1,p2):
~~~~li1,li2 = to_b4(p1),to_b4(p2)
~~~~g0 = [li1[k]==0 or li2[k]==0 for k in range(5)]
~~~~g1 = [li1[k]==1 or li2[k]==1 for k in range(5)]
~~~~g2 = [li1[k]==2 or li2[k]==2 for k in range(5)]
~~~~g3 = [li1[k]==3 or li2[k]==3 for k in range(5)]
~~~~gc,gf = {},{}
~~~~for i in range(4):
~~~~~~~~for j in range(i+1,5):
~~~~~~~~~~~~diff1 = abs(li1[i]-li1[j])
~~~~~~~~~~~~diff2 = abs(li2[i]-li2[j])
~~~~~~~~~~~~gc[i,j] = diff1 == 1 or diff2 == 1
~~~~~~~~~~~~gf[i,j] = diff1 > 1 or diff2 > 1
~~~~return g0,g1,g2,g3,gc,gf
def check(u,v,d1,d2,c,f):
~~~~a = [[0,1,2,2],[1,0,1,2],[2,1,0,1],[2,2,1,0]]
~~~~a11 = a[u][d1]
~~~~a22 = a[v][d2]
~~~~c1 = a11 == 1 or a22 == 1
~~~~f1 = a11 == 2 or a22 == 2
~~~~if c == c1 and f == f1:
~~~~~~~~return u,v
~~~~else:
~~~~~~~~return v,u
def test(g0,g1,g2,g3,gc,gf):
~~~~diff = 5
~~~~t1,t2 = range(5),range(5)
~~~~for k in range(4,-1,-1):
~~~~~~~~li = [g0[k],g1[k],g2[k],g3[k]]
~~~~~~~~u = li.index(True)
~~~~~~~~if (li.count(True) == 1):
~~~~~~~~~~~~t1[k],t2[k] = u,u
~~~~~~~~else:
~~~~~~~~~~~~li[u] = False
~~~~~~~~~~~~v = li.index(True)
~~~~~~~~~~~~if diff == 5:
~~~~~~~~~~~~~~~~diff = k
~~~~~~~~~~~~~~~~t1[k],t2[k] = u,v
~~~~~~~~~~~~else:
~~~~~~~~~~~~~~~~t1[k],t2[k] = check(u,v,t1[diff],t2[diff],gc[k,diff],gf[k,diff])
~~~~return fr_b4(t1),fr_b4(t2)
poison1 = randrange(1024)
poison2 = (poison1 + randrange(1,1024)) % 1024
g0,g1,g2,g3,gc,gf = drink(poison1,poison2)
target1,target2 = test(g0,g1,g2,g3,gc,gf)
print poison1,poison2
print to_b4(poison1)
print to_b4(poison2)
print "0:",g0
print "1:",g1
print "2:",g2
print "3:",g3
print "c:",gc
print "f:",gf
print target1,target2


IP属地:澳大利亚51楼2014-02-26 20:51
收起回复
    原帖我去看了一下,竟然用随机函数去找解。我理解,随机函数是有可能找到解决的解,但是不科学,有找到的就可能有遗漏的,所以我觉得应该从理论上再完善一下。


    IP属地:四川来自Android客户端52楼2014-02-26 21:49
    收起回复
      大王叫我来巡山
      —— 前 排 带 上
         大 禽 受
      @宇宙吉尼斯纪录
      ——节操是怎么丢掉的


      IP属地:福建53楼2014-02-27 09:41
      回复
        上面有人说用公式算最少20人,也就是最少20万,1024瓶酒,也就是每瓶200元左右。


        IP属地:新疆来自Android客户端55楼2014-02-27 22:01
        回复


          来自Android客户端56楼2014-02-28 00:34
          回复
            表示想出方法了,但是懒得算。大概算法是第一瓶每人来一滴,第二瓶一号人到三十九号来一滴,第三瓶除了39号都来一滴,第四瓶除了38都来一滴,一直到第四十一瓶后再空出来两个人不喝。。。这样应该可以算出来吧。。毕竟这些可能性是很多的,应该能超过1024种,,具体数字求大神算


            来自Android客户端57楼2014-03-20 21:19
            收起回复
              基本方法是利用方阵确定位置,推升至十维,至少要20人。


              58楼2014-03-21 15:41
              收起回复
                C(1024,2)=523776,2^19=524288,所以19人
                假设死人后编号为X,X代表某2瓶有毒,则未死的人不能喝该两瓶中的任意一瓶
                未验算,应该能排列出来


                IP属地:湖北60楼2014-03-23 12:13
                收起回复
                  高手们,求帮助


                  来自Android客户端61楼2014-08-05 22:16
                  回复
                    ♚ ♔♚ iPhone 5s 至尊版土豪金你值得拥有♔ ♚ ♔


                    来自Android客户端62楼2014-08-06 03:10
                    回复
                      楼主我想请教下你们说的C(5,2)代表什么啊,我数学没学好,它是代表从5个中选2个吗?如果是能解释一下为什么要这样选啊?


                      来自Android客户端67楼2014-08-06 13:29
                      回复
                        排列组合?


                        IP属地:浙江来自Android客户端68楼2014-08-06 19:46
                        回复
                          我认为给我一个人我就能解决。


                          IP属地:江西来自Android客户端69楼2014-08-07 18:38
                          回复
                            在第一天的不同的时间段喝下这些酒,并记录下时间。过了7天以后看在哪个时间段死的。


                            IP属地:江西来自Android客户端70楼2014-08-07 18:40
                            回复
                              这样就能找出是那瓶酒了


                              IP属地:江西来自Android客户端71楼2014-08-07 18:40
                              回复