# date:2020-08-03 10:19:54
# desc:约瑟夫环的数组、循环链表两种实现方式
# 通过对比，发现循环链表的实现方式更优雅。学习编程有重要的一点，就是每种数据结构都有它适合做的事情，我们要选用合适的数据结构做合适的事情。

#################### 数组实现方式代码 BEGIN ####################
# 表示30个人
people_list = [x for x in range(1,31)]
print(people_list)
# 初始位置
cur_pos = 0
# 模拟报数
def baoshu():
    global cur_pos
    #判断是不是该从第一个位置开始
    if cur_pos == len(people_list):
        cur_pos = 0
    #当前人完成报数
    cur_pos += 1

def joseph_cycle_array():
    while True:
        #print("当前位置:{}".format(cur_pos))
        #print("当前总人数:" ,end="")
        #print(people_list)
        #模拟前8个人报数
        for i in range(8):
            baoshu()
        # 即将离队人姓名
        people_name = people_list[cur_pos]
        #print("即将离队位置:{},即将离队人姓名:{}".format(cur_pos, people_name))
        print("即将离队人姓名:{}".format(people_name))
        # 将这个人从队伍中删除
        people_list.remove(people_name)
        #print("----------")
        #如果队伍剩下15人，结束
        if len(people_list) == 15:
            break
#################### 数组实现方式代码 END ####################

#################### 循环链表实现方式代码 BEGIN ####################
# 代码来自:https://blog.csdn.net/cliukai/article/details/100103475
def joseph_cycle_link_list():
    # 1 定义一个类
    class people:
        def __init__(self):
            self.name = ' '
            self.next = None
    
    # 初始化第一个链表
    head = people()
    head.name = '1'
    ptr = head
    
    # 2， 对30个人进行初始化，用字符串进行初始化
    for ii in range(2,31):
        new_people = people()
        new_people.name = str(ii)
        ptr.next = new_people
        ptr = ptr.next
    
    
    # 形成环形链表
    ptr.next = head
    
    # 3， 开始遍历，用while remain_people ！=15 来判断
    #     嵌套1个循环，用for循环，每逢9，删除一个链表，并打印出来
    remain_people = 30
    ptr = head
    while remain_people != 15:
        for ii in range(1,8):
            ptr = ptr.next
        # 打印9号链表
        print(ptr,'{}号下船了'.format(ptr.next.name))
        # 删除9号链表
        ptr.next = ptr.next.next
        remain_people -= 1
        # 指针向前运动一次
        ptr = ptr.next
#################### 循环链表实现方式代码 BEGIN ####################

if __name__ == '__main__':
    joseph_cycle_array()
    #joseph_cycle_link_list()