本文共 10773 字，大约阅读时间需要 35 分钟。
蒙蒂霍尔问题
While not strictly related to programming, logic puzzles are a good warm up to your next coding session. You may encounter a logic puzzle in your next technical interview as a way to judge your problem solving skills, so it's worth being prepared.
虽然与编程不严格相关，但逻辑难题是您下一次编码会议的良好准备。 在下一次技术面试中，您可能会遇到逻辑难题，以此来判断您的问题解决能力，因此值得做好准备。
In this article, we've collected a few famous logic puzzles and their solutions. Can you solve them without peeking at the answer?
在本文中，我们收集了一些著名的逻辑难题及其解决方案。 您能不偷看答案就能解决它们吗？
For this logic puzzle, imagine there are two types of people, knights and knaves. Knights only tell the truth, while Knaves only tell lies.
对于这个逻辑难题，想象一下有两种人，骑士和小刀。 骑士只说实话，而刀只讲谎言。
There are many variations of this puzzle, but most involve asking a question to figure out who is the knight and who is the knave.
这个难题有很多变体，但大多数都涉及问一个问题以弄清楚谁是骑士和谁是刀匠。
There are two people standing in front of you, Red and Blue. Blue says, "We are both knaves." Who is really the knight and who is the knave?
有两个人站在你面前，红色和蓝色。 蓝说：“我们都是刀子。” 谁是真正的骑士，谁是最专业的人？
SolutionIt's impossible for Blue to be the knight. If Blue was a knight, the statement, "We are both knaves," would actually be a lie. Therefore, Blue is a knave as his statement is a lie, and Red must be a knight.
解决方案 Blue不可能成为骑士。 如果布鲁是一个骑士，那么“我们都是刀”这样的说法实际上就是谎言。 因此，蓝色是个k夫，因为他的陈述是谎言，而红色必须是个骑士。
You arrive at a fork in the road and need to choose the correct path that leads to your destination. There are two people standing at the fork, and you know that one must be a knight and the other must be a knave.
您到达道路上的岔路口，需要选择通往目的地的正确路径。 有两个人站在叉子上，您知道一个人必须是骑士，另一个人必须是a夫。
What single question could you ask to one of the people to determine the correct path, A or B?
您可以问一个人哪个问题来确定正确的路径A或B？
SolutionThe question you can ask either person is, "What path would the other person tell me is the correct one?" The answer will always be the wrong path to take, and you can safely take the other path.Imagine the correct path is A. If you ask directly, "Which is the correct path?" the knave will say B is correct while the knight will say A.However, when asked which path the other person would say is correct, the knave will lie and say that the knight would tell you path B is correct. Meanwhile, the knight will tell the truth about the knave's answer, and say that the knave will tell you that path B is the correct one.In both cases you know that then answer, path B, is actually a lie, so you should take the other path.
解决方案您可以问一个人的问题是：“另一个人告诉我的是正确的道路？” 答案将永远是错误的路径，您可以放心地选择其他路径。想象一下正确的路径是A。如果您直接问“哪个是正确的路径？”。 刀会说B是正确的，而骑士会说A是正确的。但是，当被问到对方说哪条路径正确时，刀会撒谎并说骑士会告诉您路径B是正确的。 同时，骑士会说出关于刀法的答案的真相，并说刀法会告诉您路径B是正确的答案。在两种情况下，您都知道路径B实际上是一个谎言，因此您应该采取另一条路。
The Monty Hall Problem is a riddle on probability named after the host of the 70’s game show it’s based on, Let’s Make a Deal. This particular problem is a , which means that there is a solution that seems counter-intuitive, yet proven to be true.
蒙蒂·霍尔问题(Monty Hall Problem)是关于概率的一个谜，该概率是根据70年代的游戏节目主持人“ 让我们达成交易”而命名的。 这个特殊的问题是一个 ，这意味着有一种解决方案似乎违反直觉，但却被证明是正确的。
Imagine you are on a game show and there are 3 doors, each with a different prize behind them. Behind one of the three doors is a car. Behind the other two doors there are goats.
假设您正在一场游戏节目中，有3个门，每个门后面都有不同的奖品。 三扇门之一的后面是一辆汽车。 在其他两个门的后面是山羊。
You must choose one of the 3 doors to select as your prize.
您必须选择3个门之一来选择您的奖品。
Say you decide to open Door 1. The host, who knows where the car is, opens a different door, Door 2, which reveals a goat. He then asks if you would like to open Door 3 instead.
假设您决定打开1号门。知道车子在哪里的主人打开了另一扇门2，上面有只山羊。 然后，他询问您是否要打开3号门。
Should you choose Door 3 over your original choice? Does it even matter?
您是否应该选择3号门而不是原来的选择？ 有关系吗
SolutionIt turns out that your choice really does matter, and it is actually to your benefit to choose Door 3 instead of Door 1. Here's why.
解决方案事实证明，您的选择确实很重要，选择3号门而不是1号门实际上对您有利。这就是原因。
When you chose Door 1 from the 3 closed doors, you had a 1 out of 3 chance that you picked the right one. Both Door 2 and Door 3 also have a 1 out of the 3 chance of having a car behind it.
当您从3个关闭的门中选择1号门时，您有3个机会中有1个选择了正确的机会。 2号门和3号门在后面都有一辆汽车的可能性也为3的1。
Another way to think about it is that Doors 2 and 3 have a 2 out of 3 chance of having a car behind it combined.
另一种思考的方式是2号门和3号门有3分之二的机会将汽车组合在一起 。
But when the host opens Door 2 and reveals the goat, you suddenly have more information about the problem.
但是，当主持人打开2号门并露出山羊时，您突然有了有关该问题的更多信息。
Remember that Doors 2 and 3 have a combined probability hiding the car 2/3rds of the time. When Door 2 was opened you know that there was no car behind it.
请记住，第2和第3门的组合概率会将汽车隐瞒2/3次。 当2号门打开时，您会知道后面没有汽车。
But this reveal does not change the combined probability of the two doors. That’s the key takeaway here!
但这并没有改变两个门的组合概率。 这就是这里的重点！
Since you know that Door 2 has a 0/3 chance of hiding the car, you can now say that there's a 2/3 chance that the car is behind Door 3. Door 1 remains unchanged – there's only a 1/3 the car is behind it.
由于您知道2号门藏车的几率是0/3，因此现在您可以说3号门后面的车有2/3的几率。1号门保持不变–只有1/3的车是在它后面。
So if you decide to switch, you go from roughly a 33.33% chance to a 66.67% chance of finding the car. In other words, you are doubling your chances of success by opening Door 3 instead!
因此，如果您决定换车，那您从找到汽车的机会大约为33.33％到66.67％。 换句话说，通过打开3号门，您的成功机会翻倍！
Yes, it is possible that Door 1 was hiding all along and host tricked you. That doesn’t matter. You are gambling by taking the deal, but you’re gambling smart. You should make the best decision with the information you’re given and let the dice roll.
是的，很可能1号门一直隐藏着，主人欺骗了您。 没关系 您通过交易进行赌博，但您在赌博。 您应该根据所获得的信息做出最佳决定，然后掷骰子。
In the long run, you'd perform better by switching than a contestant who decides to go with their first choice. Though it's not immediately obvious, the host is actually doing you a favor by offering you a better deal.
从长远来看，与决定选择他们的第一选择的参赛者相比，通过切换来表现会更好。 尽管目前尚不清楚，但房东实际上通过为您提供更好的协议而帮您一个忙。
The dining philosophers problem is a classic example in computer science to illustrate issues with synchronization. It was originally created by Edsger Dijkstra in 1965, who presented it to his students as a handful of computers competing for access to shared tape drives.
餐饮哲学家问题是计算机科学中的一个经典示例，用于说明同步问题。 它最初是由Edsger Dijkstra于1965年创建的，他将它作为少数几台竞争共享磁带驱动器访问权限的计算机呈现给他的学生。
Imagine five silent philosophers sitting around a table, each with a bowl of spaghetti. There are forks on the table between each pair of adjacent philosophers.
想象一下，有五个沉默的哲学家围坐在一张桌子周围，每个哲学家都拿着一碗意大利面。 每对相邻的哲学家之间的桌子上都有叉子。
Each philosopher can only do one thing at a time: think and eat. However, a philosopher can only eat spaghetti when they have both the left and right forks. A fork can only be held by one philosopher at a time.
每个哲学家一次只能做一件事：思考和吃饭。 但是，只有在拥有左右叉的情况下，哲学家才能吃意大利面。 叉子一次只能由一位哲学家握住。
After a philosopher finishes eating, they need to put down both the left and right forks so they're available to the others. A philosopher can take a fork as soon as it's available, but can only start eating once they have both forks.
哲学家吃完饭后，他们需要放下左右叉，以便其他人都可以使用。 哲学家可以在有叉子的情况下尽快拿起叉子，但只有在拥有两个叉子后才能开始进食。
The philosophers are famous for their appetites – they can all eat endlessly and never get full. On top of that, the bowls of spaghetti magically replenish no matter how much is eaten.
哲学家以食欲而著称-他们都可以无休止地进食，并且永远不会饱食。 最重要的是，无论吃多少意大利面，都能神奇地补充面条。
The problem is, how can can you ensure that no philosopher will starve, and that they can continue eating and thinking forever?
问题是，您如何才能确保没有哲学家会饿死，并且他们可以永远继续进食和思考？
In simple terms, the dining philosophers problem is an illustration of how synchronized access to a shared resource can result in creation of a deadlock situation.
简单来说，餐饮哲学家的问题说明了对共享资源的同步访问如何导致死锁情况的产生。
Synchronization is used to control concurrent access to a shared resource. This is necessary in any situation where multiple independent actors may be competing for the use of one resource like the forks. Since there is only one resource available, we use synchronization to prevent confusion and chaos.
同步用于控制对共享资源的并发访问。 这在多个独立参与者可能争用叉子等一种资源的任何情况下都是必要的。 由于只有一种资源可用，因此我们使用同步来防止混乱和混乱。
A Deadlock is a system state where no progress is possible. This situation can occur when synchronization is enforced, and many processes end up waiting for a shared resource which is being held by some other process. Like with the philosophers who are either stuck eating or thinking, the processes just keep waiting and execute no further.
死锁是系统状态，无法进行进度。 当强制执行同步时，可能会发生这种情况，并且许多进程最终都在等待某个其他进程所持有的共享资源。 就像那些固守饮食或思考的哲学家一样，这些过程只是不断地等待，不再执行。
At first glance it appears like it would not be possible for a deadlock where all philosophers are stuck either eating or thinking. For example, pattern for each philosopher to follow might be:
乍一看，似乎不可能发生所有哲学家都陷入困境的僵局。 例如，每个哲学家可以遵循的模式可能是：
1: think until the left fork is available; when it is, pick it up;
1：思考，直到左叉可用； 如果是的话，拿起它；
1: think until the left fork is available; when it is, pick it up;
1：思考直到左叉可用； 如果是的话，拿起它；
2: think until the right fork is available; when it is, pick it up;
2：思考，直到合适的叉子可用； 如果是的话，拿起它；
2: think until the right fork is available; when it is, pick it up;
2：思考，直到合适的叉子可用； 如果是的话，拿起它；
3: when both forks are held, eat for a fixed amount of time;
3：握住两个叉子时，请进食固定的时间；
3: when both forks are held, eat for a fixed amount of time;
3：握住两个叉子时，请进食固定的时间；
4: then, put the right fork down;
4：然后放下右叉；
4: then, put the right fork down;
4：然后放下右叉；
5: then, put the left fork down;
5：然后放下左叉
5: then, put the left fork down;
5：然后放下左叉
6: repeat from the beginning.
6：从头开始重复
6: repeat from the beginning.
6：从头开始重复
Source:
资料来源：
There are many solutions possible to prevent deadlock. If we look closely, one problem in the algorithm above is that all philosophers have equal chance (have the same priority) of acquiring one fork. This prevents anyone from acquiring two forks and the whole system grinds to a halt.
有许多解决方案可以防止死锁。 如果我们仔细观察，上述算法中的一个问题是，所有哲学家都有相同的机会(具有相同的优先级)获得一把叉子。 这样可以防止任何人获得两个叉子，并且整个系统陷入停顿。
Here are some possible solutions:
以下是一些可能的解决方案：
Priority: Some philosophers are assigned higher priority, so that the chance of acquiring both forks is increased.
优先级 ：一些哲学家被赋予更高的优先级，因此增加了获得两把叉子的机会。
Preemption (Politeness): Philosophers relinquish the acquired fork without eating, in case the other fork is not available.
抢占 (礼貌)：如果没有其他叉子，则哲学家不吃东西就放弃获得的叉子。
Arbitration: A mediator allocates forks ensuring that two forks are given to one person, instead of one to many.
仲裁 ：调解员分配分叉，确保将两个分叉分配给一个人，而不是一对多。
Now that you know how to solve these logic puzzles, treat yourself to an endless bowl of spaghetti. You earned it.
既然您知道如何解决这些逻辑难题，那就请自己吃一碗无尽的意大利面。 你赚了
翻译自:
蒙蒂霍尔问题
转载地址：http://vmrwd.baihongyu.com/