×

Loading...

Topic

This topic has been archived. It cannot be replied.
  • 工作学习 / 学科技术 / 大学时看过的一道算法题，据说也是现在Google招程序员的面试题。 -sailor(Ocean & Mountain); 2016-3-30 {513} (#10018553@0)
    Every man in a village of 100 married couples has cheated on his wife. Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?
    • If we call the annoucement day as Day 1, then nothing happens in the first 99 days. On Day 100, all wives kill their husbands. -thinkinger(thinkinger); 2016-4-15 (#10051832@0)
      • why? -kakaka(小胖子); 2016-4-15 (#10051836@0) +1
        • 简单的排除法呗。不过申明我没学过此算法。 -icespeeder(Speeder On Ice); 2016-4-15 (#10051885@0)
          • 你觉得这是正确答案？ -kakaka(小胖子); 2016-4-15 (#10051889@0)
            • 我要是知道的话就在google上班干大事，那还有功夫跟你闲聊。 -icespeeder(Speeder On Ice); 2016-4-15 (#10051913@0)
              • 叫你说的google跟政协似的 -facenorthface(小北); 2016-4-15 (#10051914@0)
                • 60+的。。。中年干部才让进。 -kakaka(小胖子); 2016-4-15 (#10051929@0)
                • 没明白你个中的逻辑。 -icespeeder(Speeder On Ice); 2016-4-15 (#10051980@0)
              • 那你就能得出结论是个。。。【简单的排除法】。。。而不是复杂的推算法？ -kakaka(小胖子); 2016-4-15 (#10051916@0)
                • not hers, not hers, ...., skip 97 times, then, oh my God, it must be ... -icespeeder(Speeder On Ice); 2016-4-15 (#10051938@0) +1
                  • 为啥就不能是只死1个？另99个wife都知道，就是不说而已。。。。或是死2个，或是死3个。。。 -kakaka(小胖子); 2016-4-15 (#10051956@0)
                    • 抓马抓马！有抓马才好看啊。 -icespeeder(Speeder On Ice); 2016-4-15 (#10051975@0)
      • I will write a detailed prove later. It's not guess. -thinkinger(thinkinger); 2016-4-15 (#10051966@0)
        • ok, don't leave us hanging. -kakaka(小胖子); 2016-4-15 (#10051968@0)
    • Here is my prove. -thinkinger(thinkinger); 2016-4-15 {1313} (#10052000@0)
      本文发表在 rolia.net 枫下论坛Sorry, can't type Chinese.

      Let's start from two couples: a-A, and b-B (a/b for wives, and A/B for husbands):
      *Every wife holds a number 1, which is the number of total unfaithful husbands except their own, but they don't know whether the other wife is holding 1 or 0.
      *On Day 1, they know if the other wife is holding 0, that wife will find out her husband is the only unfaithful husband. Therefore that wife will cook a good last meal for her husband, kisses him, asks passwords for bank accounts/Gmail/Facebook, and lastly but most importantly kills her husband by the end of Day 1. That wouldn't happen because no wife is holding 0.
      *On Day 2, because no husband is killed, both of them find out the fact that every one is holding 1, which means their own husbands is unfaithful, they do what they suppose to do (kill..)

      Let's move to three couples: a-A, b-B, and c-C:
      *Every wife holds a number 2
      *On Day 1, they are waiting for wives with number 0. It didn't happen.
      *On Day 2, they are waiting for wives with number 1. It didn't happen.
      *On Day 3, they realize the fact, and they all start on the same day (exact time may vary)

      So on so on...

      As a summary, 2 couples wait until Day 2, 3 couples wait until Day 3,...100 couples wait until Day 100.

      That's it.更多精彩文章及讨论，请光临枫下论坛 rolia.net
      • why, [On Day 1, they know if the other wife is holding 0]... there is no requirement that the wives consult with each other to find out who is cheating. -kakaka(小胖子); 2016-4-15 (#10052036@0)
        • That's why they have to wait until Day 2. They don't communicate, -thinkinger(thinkinger); 2016-4-15 {196} (#10052047@0)
          they observe. On Day 1, only those who has number 0 can kill, because that means no other husband is cheating, but the Queen said there is at least one, so only their own husband will be that one.
          • 不错。是可以用这点怎么确认出轨的是自己家的。但。为啥要等到第100天？100个wife，第1天都是0。第二天没人死。照你的逻辑不该立马开杀？ -kakaka(小胖子); 2016-4-15 (#10052068@0)
            • 或者这么说。一开始是0的，为啥要等，或是需要等谁呢？ 照你说的不该直接开杀？ -kakaka(小胖子); 2016-4-15 (#10052091@0)
              • 因为第二天只有那些手里有1号的人可以杀人，第三天只有那些手里有2号的可以杀，依此类推。手里是99号，你是不能提前杀人的,对因为你掌握的证据是不充分的。 -thinkinger(thinkinger); 2016-4-15 (#10052113@0)
                • 还是不明白为啥要等100天。。。要是事实上只有1个出轨，那就第一天死1个。然后。。。就没有然后了？ 或是女王说错了，一个出轨的都没。那第一天不就都死光了？ -kakaka(小胖子); 2016-4-18 (#10054578@0)
              • 回到三对夫妇那个例子。你手上是2，但是你不知道别人是0，1， 还是2。第一天没有人死，说明没人有0号。第二天，如果有人死了。说明有人有1号，而且，这是最重要的一步，说明你老公是没问题的，你不能杀他了。所以如果你不等到你可以杀人的那天就动手的话，你可能误杀的 -thinkinger(thinkinger); 2016-4-15 (#10052129@0)
        • If you still don't get it, hold on. I will re-write the answer in Chinese this weekend. -thinkinger(thinkinger); 2016-4-15 (#10052049@0)
    • 有无数种可能性。这是面试题，不是数学题。考察至少两点：脑筋还清楚，能think out of box。 -geekcode(文心雕码); 2016-4-15 (#10052309@0)
    • 没看明白，谁能翻译成中文再讲一遍？ -binghongcha76(一只大猫); 2016-4-20 (#10060228@0)
    • 非程序员的答案，some guy(s)in the village slept with the Queen during her visiting...that what happened -8daysaweek(8daysaweek); 2016-6-10 (#10144501@0)
    • 直觉上感觉这是要考deadlock（hold and wait），前提是wives不能相互交流，不然的话，wives一起叽叽咂咂，一圈下来都咔嚓了个球 -fuan(更换昵称); 2016-6-10 (#10144548@0)

More Topics

  • 这里有没有搞通讯协议，又是wireshark高手的同学，有问题想请教请教
  • 工业制造技术不是靠大嗓门提高的，也不是靠弯道超车取得的，而是靠每一天，每一月，每一年辛勤的钻研取得的。我在工厂工作过，我在工程公司做过，深深体会到这一点。脚踏实地，是提高制造技术的精髓。
  • 怎样理解reverse stress testing? 和stress testing 有什么相互关系吗？
  • 惨了。今天一个同事做编程讲座，我跟她辩论说oo,多态怎样怎样。结果她说，现在编程界OO和多态已被批倒批臭，并踏上亿万只脚。现在是革命小将functional Programming的时代！可怜我OO还没学明白呐，就变天了。。。我同事说的对吗？
  • The two assumptions we need about the cost function
    • 枫下论坛主坛 /  工作学习 /  学科技术