演算法修煉 第04級：囚犯

① 每個人關一個牢房。

② 每個牢房相互之間相互隔絕。

③ 每天隨機抽取一個人防風。

④ 放風的地方有一盞電燈，放風的囚犯可以通電開啟它，也可以關閉它。

⑤ 電燈永遠不會斷電，僅取決於開關是否開啟，並且電燈永遠不會壞。

⑥ 囚犯去的路上和回來的路上都不會被觀察到，別人無法知道是誰去防風和回來。

⑦ 向獄警彙報到那一天為止，所有人都至少出去防風過一次，那麼所有人都釋放。

思路：

① 班長的作用就是用來計數。

② 除班長外，其他人的為普通人。

普通人，第一次出門，如果燈是滅的，就開啟燈，通知班長。

普通人，如果不是第一次出門，那麼他就什麼也不做。

import numpy as np

def prison（prisoners）：

turn_on = ［False］ * prisoners # 所有人都沒開過燈

monitor = prisoners - 1 # 把最後一個人作為班長，其餘人為普通犯人

num = 1 # 班長自己肯定會出去一次，所以初始技術為 1

lamp = False # 燈初始化是滅的

while num < prisoners： # 當計數小於犯人數目時，繼續迴圈

# 返回燈的情況，計數情況

lamp，num = select（prisoners，monitor，turn_on，lamp，num）

print（“All prisoners get free”）

def select（prisoners，monitor，turn_on，lamp，num）：

luck = np。random。randint（0，prisoners） # 幸運兒，出去防風的人

print（“luck：”，luck） # 第幾號幸運兒

if luck == monitor：

if lamp：

num += 1

lamp = False

else：

if not lamp： # 如果燈是滅的

if not turn_on［luck］： # 如果沒有開過燈

lamp = True

turn_on［luck］ = True # 表明他已經開過燈

print（‘lamp：’，lamp， ‘ num’，num）

return lamp，num

if __name__==‘__main__’：

prison（4）

執行結果：

luck： 1

lamp： True num 1

luck： 2

lamp： True num 1

luck： 3

lamp： False num 2

luck： 0

lamp： True num 2

luck： 3

lamp： False num 3

luck： 1

lamp： False num 3

luck： 3

lamp： False num 3

luck： 3

lamp： False num 3

luck： 0

lamp： False num 3

luck： 2

lamp： True num 3

luck： 3

lamp： False num 4

“♥

我寫的筆記，希望對你有幫助

♥”