华为OD机试 Python 报数问题

旧城等待， 2024-03-08 06:17 97阅读 0赞

### 题目 ###

描述  
你和你的朋友们围成一个圈玩游戏，从第一个人开始，依次报数：1、2、3…当数到3的时候，那个人就得退出游戏。然后从他的下一个朋友继续开始，1、2、3…同样的，数到3的人又得退出。这样一直进行下去，直到圈里只剩下一个人。人会是谁？

任务：

给你参与游戏的人数（比如10个人），最后那个人是原来是第几个人？

输入：

一个数字，表示有多少人在玩游戏（小于1000）。  
输出：

一个数字，表示最后留下的那个幸运儿原本是第几个。  
示例：

如果有2个人在玩，第1个人会被数到3并退出，所以最后留下的是第2个人。

### 代码 ###

class Person:
        def __init__(self, position):
            self.position = position
            self.next_person = None
            self.prev_person = None
    
    class GameCircle:
        def __init__(self):
            self.first_person = None
            self.last_person = None
            self.total_people = 0
    
        def add_person(self, position):
            person = Person(position)
            if not self.first_person:
                self.first_person = person
                self.last_person = person
                person.prev_person = person
                person.next_person = person
            else:
                person.prev_person = self.last_person
                person.next_person = self.first_person
                self.first_person.prev_person = person
                self.last_person.next_person = person
                self.last_person = person
            self.total_people += 1
    
        def remove_person(self, person):
            if self.total_people == 1:
                self.first_person = None
                self.last_person = None
            else:
                person.prev_person.next_person = person.next_person
                person.next_person.prev_person = person.prev_person
                if person == self.first_person:
                    self.first_person = person.next_person
                if person == self.last_person:
                    self.last_person = person.prev_person
            self.total_people -= 1
    
    def find_last_person(n):
        game = GameCircle()
        for i in range(1, n+1):
            game.add_person(i)
        
        current_person = game.first_person
        while game.total_people > 1:
            for _ in range(2):
                current_person = current_person.next_person
            next_person = current_person.next_person
            game.remove_person(current_person)
            current_person = next_person
        
        return game.first_person.position
    
    if __name__ == '__main__':
        num_people = int(input())
        print(find_last_person(num_people))