0 寫在前面

josephus問題是數(shù)據(jù)結(jié)構(gòu)教材中的一個(gè)常見實(shí)例，其問題可以描述為：

設(shè)nnn個(gè)人圍坐一圈，現(xiàn)在要求從第kkk個(gè)人開始報(bào)數(shù)，報(bào)到第mmm個(gè)的人退出。然后從下一個(gè)人開始繼續(xù)按照同樣規(guī)則報(bào)數(shù)并退出，直到所有人退出為止。要求按照順序輸出每個(gè)人的序列號(hào)。

1 基于數(shù)組概念的解法

首先考慮基于python的list和固定大小的數(shù)組概念，即將list看作元素個(gè)數(shù)固定的對(duì)象，只改變值而不刪除元素，相當(dāng)于擺了一圈nnn把椅子，人雖然退出但是椅子還在，我們可以給每個(gè)人從111到nnn編號(hào)，沒有人的位置用000表示，思路如下：

初始

建立包含nnn個(gè)人(編號(hào))的list 找到第kkk個(gè)人開始

運(yùn)行

從kkk的位置開始數(shù)到mmm，中間遇到000的就跳過 數(shù)到mmm之后，將其值改為000 然后繼續(xù)循環(huán)，總共循環(huán)nnn次(因?yàn)槊看窝h(huán)就會(huì)退出一個(gè)人)

代碼如下：

def josephus_A(n, k, m): people = list(range(1, (n+1))) i = k-1 for num in range(n): count = 0 while count < m: if people[i] > 0:count += 1 if count == m:print(people[i], end=' ')people[i] = 0 i = (i+1) % n # count只是flag，真正記的數(shù)是i if num < n-1: print(end=',', ) else: print(' ')

2 基于順序表的解法

順序表是線性表的一種，即表中元素放在一塊足夠大的連續(xù)存儲(chǔ)區(qū)里，首元素存入存儲(chǔ)區(qū)開始位置，其余元素依次存放。順序表在python中的也是list，跟第一種解法不同，當(dāng)?shù)趍mm個(gè)人退出需要進(jìn)行刪除元素的操作，才是順序表。而第一種解法的數(shù)組想要?jiǎng)h除并不是那么容易，這里是因?yàn)閜ython中沒有內(nèi)置對(duì)數(shù)組的支持，所以用list代替，具體可以參照c++中的數(shù)組，如果要?jiǎng)h除中間的某個(gè)元素的話，必須對(duì)后面的元素重新編號(hào)。代碼實(shí)現(xiàn)如下：

def josephus_L(n, k, m): people = list(range(1, (n+1))) i=k-1 for num in range(n,0,-1): i=(i+m-1)%num print(people.pop(i),end=', ' if num>1 else 'n')

3 基于循環(huán)單鏈表的解法

單鏈表即單向鏈接表，典型的就是c++中的鏈表，循環(huán)單鏈表就是頭尾相連的單鏈表，也是線性表的一種，這道題目使用循環(huán)單鏈表記錄nnn個(gè)人圍坐一圈最為契合。我們只需要數(shù)到第mmm個(gè)結(jié)點(diǎn)就刪除，刪除操作對(duì)于鏈表來(lái)說比較容易，而且不需要有i = (i+1) % n這樣的整除操作。但是問題在于python并沒有像c++那樣有內(nèi)置對(duì)鏈表的支持，因此需要建立一個(gè)鏈表的類，建立是比較麻煩的，但是操作比較簡(jiǎn)單，如下：

class LNode: # 建立鏈表結(jié)點(diǎn) def __init__(self,elem,next_=None): self.elem=elem self.next=next_class LCList: # 建立循環(huán)鏈接表 def __init__(self): self._rear=None def is_empty(self): return self._rear is None def prepend(self,elem): # 前端插入 p=LNode(elem) if self._rear is None: p.next=p # 建立一個(gè)結(jié)點(diǎn)的環(huán) self._rear=p else: p.next=self._rear.next self._rear.next=p def append(self,elem): # 尾端插入 self.prepend(elem) self._rear = self._rear.next def pop(self): # 前端彈出 if self._rear is None: raise LinkedListUnderflow('in pop of CLList') p = self._rear.next if self._rear is p: self._rear =None else: self._rear.next=p.next return p.elem def printall(self): # 輸出表元素 if self.is_empty(): return p = self._rear.next while True: print(p.elem) if p is self._rear:break p=p.nextclass LinkedListUnderflow(ValueError): # 自定義異常 passclass Josephus(LCList): def __init__(self,n,k,m): LCList.__init__(self) for i in range(n): self.append(i+1) self.turn(k-1) while not self.is_empty(): self.turn(m-1) print(self.pop(),end=('n' if self.is_empty() else ', ')) def turn(self,m): for i in range(m): self._rear = self._rear.next

到此這篇關(guān)于使用python從三個(gè)角度解決josephus問題的方法的文章就介紹到這了,更多相關(guān)python josephus問題內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！