This website requires Javascript to function properly. Please go to the setting of your web browser and enable Javascript for this website.

Ad by

推荐 OXIO 加拿大高速网络，最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务

Ad by

推荐 OXIO 加拿大高速网络，最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务

大学时看过的一道算法题，据说也是现在Google招程序员的面试题。

sailor(Ocean & Mountain)

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?

(#10018553@0)
Last Updated: 2016-3-30
This post has been archived. It cannot be replied.

Report

Replies, comments and Discussions:

工作学习 / 学科技术 / 大学时看过的一道算法题，据说也是现在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)

@Florida

大学时看过的一道算法题，据说也是现在Google招程序员的面试题。

Replies, comments and Discussions:

More Topics