學點演算法之隊列的學習及應用

原文： 學點演算法之隊列的學習及應用

約瑟夫問題

約瑟夫問題

有 n 個囚犯站成一個圓圈，準備處決。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），並殺掉第k個人。接著，再越過 k-1個人，並殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。

問題是，給定了n和k，一開始要站在什麼地方才能避免被處決？

這個問題是以弗拉維奧·約瑟夫命名的，它是1世紀的一名猶太歷史學家。他在自己的日記中寫道，他和他的40個戰友被羅馬軍隊包圍在洞中。他們討論是自殺還是被俘，最終決定自殺，並以抽籤的方式決定誰殺掉誰。約瑟夫斯和另外一個人是最後兩個留下的人。約瑟夫斯說服了那個人，他們將向羅馬軍隊投降，不再自殺。約瑟夫斯把他的存活歸因於運氣或天意，他不知道是哪一個。

隊列是什麼

這道題有多種解法，這裡先不說別的，要引出今天的主角——隊列。隊列的定義很好理解：

隊列是項的有序結合，其中添加新項的一端稱為隊尾，移除項的一端稱為隊首。當一個元素從隊尾進入隊列時，一直向隊首移動，直到它成為下一個需要移除的元素為止。

隊列抽象數據類型由以下結構和操作定義。如上所述，隊列被構造為在隊尾添加項的有序集合，並且從隊首移除。隊列保持 FIFO 排序屬性。 隊列操作如下。

• Queue() 創建一個空的新隊列。 它不需要參數，並返回一個空隊列。
• enqueue(item) 將新項添加到隊尾。 它需要 item 作為參數，並不返回任何內容。
• dequeue() 從隊首移除項。它不需要參數並返回 item。 隊列被修改。
• isEmpty() 查看隊列是否為空。它不需要參數，並返回布爾值。
• size() 返回隊列中的項數。它不需要參數，並返回一個整數。

隊列的Python演算法實現

為了實現隊列抽象數據類型創建一個新類

pythonds/basic/queue.py

class Queue: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self, item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items)

想明白了其實就是對 list 的簡單操作

如何活到最後

那我們回到上面的問題，如果是你，你要如何選擇並活到最後呢？

我們的程序將輸入名稱列表和一個稱為 num 常量用於報數。它將返回以 num 為單位重複報數後剩餘的最後一個人的姓名。

假設第一個人是a。從他開始計數，a將先出列再入隊列，把他放在隊列的最後。經過 num 次的出隊入隊後，前面的人將被永久移除隊列。並且另一個周期開始，繼續此過程，直到只剩下一個名字（隊列的大小為 1）。

from pythonds.basic.queue import Queuedef hotPotato(namelist, num): simqueue = Queue() for name in namelist: simqueue.enqueue(name) while simqueue.size() > 1: for i in range(num): simqueue.enqueue(simqueue.dequeue()) simqueue.dequeue() return simqueue.dequeue()print(hotPotato([a, b, c, d, e, f, g, h, i, j], 7))# output: f

其他解法

比較簡單的做法是用循環單鏈表模擬整個過程，時間複雜度是O(n*m)。如果只是想求得最後剩下的人，則可以用數學推導的方式得出公式。先看看模擬過程的解法。

# -*- coding: utf-8 -*- class Node(object): def __init__(self, value): self.value = value self.next = Nonedef create_linkList(n): head = Node(1) pre = head for i in range(2, n+1): newNode = Node(i) pre.next= newNode pre = newNode pre.next = head return headn = 5 #總的個數m = 2 #數的數目if m == 1: #如果是1的話，特殊處理，直接輸出 print(n) else: head = create_linkList(n) pre = None cur = head while cur.next != cur: #終止條件是節點的下一個節點指向本身 for i in range(m-1): pre = cur cur = cur.next print(cur.value) pre.next = cur.next cur.next = None cur = pre.next print(cur.value)

作業

假設實驗室里有一台印表機供學生共性。當學生向共享印表機發送列印任務時，任務被放置在隊列中以便以先來先服務的方式被處理。如何才能通過python程序模擬的方式得到每次提交任務的平均等待時間呢？（平均等待時間不包括列印本身的時間，僅指在隊列中排隊的時間。）

• 學生們每次列印的頁數在1到20頁之間。
• 印表機平均每小時會收到20個列印請求，即平均每180秒1個請求。
• 每秒新增任務的可能性相等，即任務的產生為獨立同分布
• 印表機的列印速度恆定。

挖坑，要一起來填嗎？

推薦閱讀：