資料結構與演算法（Python版）：用佇列（Queue）處理約瑟夫問題-有解無憂

在古羅馬時期，猶太人背叛了羅馬人，落到困境，約瑟夫和同行的一共39個猶太人只能夠自殺殉國，但是猶太教義規定不能自殺，因此只能夠讓別人將自己殺害，他們所有39個人坐成一圈，報數1—7，報到7則由身旁的人將自己殺死，結果約瑟夫靈機一動，給自己安排了一個位置，最后活了下來，那么約瑟夫給自己安排的是哪一個位置呢？

在這個題目當中，我們如果使用佇列，不僅可以處理任意人數坐成一圈，還可以將報數的值任意修改，最后都可以找到那一個不被殺死的人的位置，我們可以將所有人都放進一個大的佇列里，每報一次數字，那么就把佇列頭部的人放到佇列的尾部，直到報數報到一組數字的最后一個，比如1——7當中的7，這個時候就將佇列頭的這個人洗掉（也就是殺死），不斷執行這個程序，直到整個佇列當中的人數只有一個，則跳出回圈回傳最后活著的那個人的名字，

首先定義佇列（Queue）類的結構：

class Queue():

    def __init__(self):
        # 初始化一個空的串列
        self.__list=[]

        # 往佇列里插入元素
    def enqueue(self,item):
        self.__list.append(item)

    # 彈出佇列里的元素
    def dequeue(self):
        return self.__list.pop(0)# 彈出佇列里最先進入的元素

    # 判斷佇列是否為空
    def is_empty(self):
        return self.__list == []

    # 計算佇列的大小
    def size(self):
        return len(self.__list)

使用佇列類來初始化一個物件，sim_queue,然后撰寫剛才我們分析之后的程式：

def hot_potato(namelist,num):

    sim_queue = Queue()

    for name in namelist:
        sim_queue.enqueue(name) # 把拿到的名字全部都放到佇列里

    while sim_queue.size() > 1:
        for i in range(num):
            sim_queue.enqueue(sim_queue.dequeue())
        # 每執行完一次，就將佇列的頭拿出來彈出，相當于土豆傳遞給這個人，然后這個人就死了

        last_person=sim_queue.dequeue()

    return last_person

print("開始執行約瑟夫問題")
print(hot_potato(["bob","NAni","Ao li Gei!","HeHe","Mike","Suvennia"],4))

輸出：

開始執行約瑟夫問題
Ao li Gei!

得解，因此Ao li Gei!這個人不會被殺死，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/53396.html

標籤：其他

上一篇：一文帶你攻克二分查找

下一篇：【求助關于通信協議的問題】