環状単鎖表のジョセフ問題Python版

题目:1つの环形単链表、最初から结点を后ろにして、指针は1つの结点を移动するたびに、カウントに1を加えて、m番目のノードまで数える时、この结点を削除して、それから次のノードから1をカウントして、环形単链表の中で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*len(ringlinkedlist)).しかし、実際には、チェーンテーブルの長さと削除するステップ長を決定すれば、最終的に残りのノードは固定されているに違いないので、これは固定された関数であり、私たちは根劇MとNでインデックスを決定すればいいだけで、この関数は数論に関連しており、具体的には詳しくは書かない.