python環状単鎖表のジョセフ問題は詳しく説明します。

タイトル:
一つのリングチェーンテーブルは、最初のノードから後ろに、ポインタが一つの結点を移動するごとに、1をカウントし、m番目のノードまで数えると、その結点を削除し、次のノードから1カウントを開始し、ループを繰り返す。リングシングルチェーンテーブルに一つの結点が残っているまで、その結点を返す。
この問題は有名なジョセフ問題です。
コード:
まず、環状単一チェーンテーブルのデータ構造を示します。

class Node(object):
 def __init__(self, value, next=0):
  self.value = value
  self.next = next #   

class RingLinkedList(object):
 #        
 def __init__(self):
  self.head = 0 #   

 def __getitem__(self, key):
  if self.is_empty():
   print 'Linked list is empty.'
   return
  elif key < 0 or key > self.get_length():
   print 'The given key is wrong.'
   return
  else:
   return self.get_elem(key)

 def __setitem__(self, key, value):
  if self.is_empty():
   print 'Linked list is empty.'
   return
  elif key < 0 or key > self.get_length():
   print 'The given key is wrong.'
   return
  else:
   return self.set_elem(key, value)

 def init_list(self, data): #       data
  self.head = Node(data[0])
  p = self.head #        
  for i in data[1:]:
   p.next = Node(i) #            
   p = p.next #           
  p.next = self.head

 def get_length(self):
  p, length = self.head, 0
  while p != 0:
   length += 1
   p = p.next
   if p == self.head:
    break
  return length

 def is_empty(self):
  if self.head == 0:
   return True
  else:
   return False

 def insert_node(self, index, value):
  length = self.get_length()
  if index < 0 or index > length:
   print 'Can not insert node into the linked list.'
  elif index == 0:
   temp = self.head
   self.head = Node(value, temp)
   p = self.head
   for _ in xrange(0, length):
    p = p.next
   print "p.value", p.value
   p.next = self.head
  elif index == length:
   elem = self.get_elem(length-1)
   elem.next = Node(value)
   elem.next.next = self.head
  else:
   p, post = self.head, self.head
   for i in xrange(index):
    post = p
    p = p.next
   temp = p
   post.next = Node(value, temp)

 def delete_node(self, index):
  if index < 0 or index > self.get_length()-1:
   print "Wrong index number to delete any node."
  elif self.is_empty():
   print "No node can be deleted."
  elif index == 0:
   tail = self.get_elem(self.get_length()-1)
   temp = self.head
   self.head = temp.next
   tail.next = self.head
  elif index == self.get_length()-1:
   p = self.head
   for i in xrange(self.get_length()-2):
    p = p.next
   p.next = self.head
  else:
   p = self.head
   for i in xrange(index-1):
    p = p.next
   p.next = p.next.next

 def show_linked_list(self): #           
  if self.is_empty():
   print 'This is an empty linked list.'
  else:
   p, container = self.head, []
   for _ in xrange(self.get_length()-1): #
    container.append(p.value)
    p = p.next
   container.append(p.value)
   print container

 def clear_linked_list(self): #      
  p = self.head
  for _ in xrange(0, self.get_length()-1):
   post = p
   p = p.next
   del post
  self.head = 0

 def get_elem(self, index):
  if self.is_empty():
   print "The linked list is empty. Can not get element."
  elif index < 0 or index > self.get_length()-1:
   print "Wrong index number to get any element."
  else:
   p = self.head
   for _ in xrange(index):
    p = p.next
   return p

 def set_elem(self, index, value):
  if self.is_empty():
   print "The linked list is empty. Can not set element."
  elif index < 0 or index > self.get_length()-1:
   print "Wrong index number to set element."
  else:
   p = self.head
   for _ in xrange(index):
    p = p.next
   p.value = value

 def get_index(self, value):
  p = self.head
  for i in xrange(self.get_length()):
   if p.value == value:
    return i
   else:
    p = p.next
  return -1

次いでジョセフアルゴリズムを与える。

 def josephus_kill_1(head, m):
  '''
       ，   RingLinkedList     ，     。
  :param head:             ，  m      
  :return:           
         ，             ，      o(m*len(ringlinkedlist))
  '''
  if head == 0:
   print "This is an empty ring linked list."
   return head
  if m < 2:
   print "Wrong m number to play this game."
   return head
  p = head
  while p.next != p:
   for _ in xrange(0, m-1):
    post = p
    p = p.next
   #print post.next.value
   post.next = post.next.next
   p = post.next
  return p

分析:
私はこの問題を解決するために最も原始的な方法を採用しました。時間の複雑さはoです。
しかし、実際にチェーンの長さと削除するステップの長さを決定したら、最終的に残っている結点は必ず固定されています。したがって、これは固定の関数です。私たちはドラマMとNだけでインデックスを確定すればいいです。この関数は数論に関連しています。詳しくは書きません。
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。