蒙蒂霍爾問題_常見的邏輯難題–騎士和刀，蒙蒂·霍爾和就餐哲學家的問題解釋...

蒙蒂霍爾問題

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?

在本文中，我們收集了一些著名的邏輯難題及其解決方案。您能不偷看答案就能解決它們嗎？

騎士和小刀 (Knights and Knaves)

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.

這個難題有很多變體，但大多數都涉及問一個問題以弄清楚誰是騎士和誰是刀匠。

紅色和藍色 (Red and Blue)

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夫，因為他的陳述是謊言，而紅色必須是個騎士。

兩條路 (Two Paths)

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)

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 veridical paradox, 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)

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?

問題是，您如何才能確保沒有哲學家會餓死，并且他們可以永遠繼續進食和思考？

同步與死鎖 (Synchronization and Deadlock)

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.

死鎖是系統狀態，無法進行進度。當強制執行同步時，可能會發生這種情況，并且許多進程最終都在等待某個其他進程所持有的共享資源。就像那些固守飲食或思考的哲學家一樣，這些過程只是不斷地等待，不再執行。

解決方案 (Solutions)

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: Wikipedia
資料來源：維基百科

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.

既然您知道如何解決這些邏輯難題，那就請自己吃一碗無盡的意大利面。你賺了