5369 约瑟夫问题2

### 约瑟夫问题概述

约瑟夫环（Josephus Problem）描述了一种特定情境下的淘汰机制，即一群编号为 1 至 n 的个体围坐成圈，从某一点开始按固定方向计数，每数到指定数值 m 的个体被淘汰出局，剩余者继续此过程直至最后一名幸存者被确定[^2]。

### 数组方法解析

采用数组模拟约瑟夫环的过程能够简化逻辑处理。初始化长度为 n 的布尔型列表 `alive` 表示各成员存活状态；通过遍历并更新索引来追踪当前正在考虑的位置以及累计已移除元素的数量，从而决定下一个应被淘汰者的身份[^1]。

def josephus_problem_array(n, m):
    alive = [True] * n       # 所有人都活着的状态标记
    result = []             # 记录每次被淘汰人的原始位置
    index = 0               # 当前考察对象所在下标
    count_alive = n         # 剩余生命数目
    
    while count_alive > 0:
        cnt = 0
        
        # 寻找第m个活人
        while cnt < m:
            if alive[index]:
                cnt += 1
                
            if cnt == m:
                break
            
            index = (index + 1) % n
        
        # 移除此人
        alive[index] = False
        result.append(index + 1)
        count_alive -= 1
        
        # 更新起始点至下一活人处
        index = (index + 1) % n
        while not alive[index]:
            index = (index + 1) % n
            
    return result

上述代码片段展示了如何利用Python中的列表结构来表示参与游戏人群的生命状况，并实现了基于数组版本的解法。每当找到符合条件的对象后立即将其状态设为死亡(`False`)，同时记录下对应的初始序号以便最终输出完整的淘汰序列。

### 单向链表实现方式

另一种常见的解决策略是构建一个带有自连接特性的单项链表模型，在这里每个节点代表一位参与者及其后续接替人选的信息。为了确保操作效率，通常会引入额外辅助变量如前置指针(predecessor pointer)，使得删除动作可以在常数时间内完成而不必重新扫描整个链条寻找目标项之前的所有元素[^3]。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* create_circle(int n){
    if (n <= 0) return NULL;
    
    Node* head = malloc(sizeof(Node));
    head->data = 1;
    head->next = head;
    
    Node* current = head;
    for(int i=2;i<=n;++i){
        Node* temp = malloc(sizeof(Node));
        temp->data=i;
        temp->next=head;
        
        current->next=temp;
        current=current->next;
    }
    
    return head;
}

void solve_josephus_linkedlist(int n,int s,int m){
    Node* circle=create_circle(n);
    Node* start=circle,*prev=NULL;
    
    // 定位起点
    for(int i=1;i<s && start!=NULL;i++){
        prev=start;
        start=start->next;
    }

    Node* p=start;
    do{
        // 向前走(m-1)步到达要杀掉的人前面那个结点
        for(int step=1;step<m;p=p->next,++step){};
        printf("%d ",p->next->data);  
        // 删除结点
        Node* to_delete=p->next;
        p->next=p->next->next;
        free(to_delete);

        // 继续循环直到只剩最后一个结点了
    }while(p->next != p);
}

这段C语言程序定义了一个简单的函数用于创建含有给定数量节点形成的闭环链表，并提供了执行具体约瑟夫规则的方法——先定位到实际出发点`s`，之后按照既定间隔逐轮筛选直至仅剩唯一胜出者为止。