约瑟夫生死着游戏c语言课程设计

### C语言实现约瑟夫环问题的课程设计

#### 1. 约瑟夫环简介
约瑟夫环是一个经典的计算机科学问题，源自于一个历史故事。该问题描述了一群人围成一圈并按照一定规则逐步淘汰成员，最终剩下最后一名幸存者的场景。

#### 2. 数组方法实现约瑟夫环
通过数组可以方便地模拟约瑟夫环中的人员状态变化。以下是基于数组的方法来解决问题的具体代码：

#include <stdio.h>

int josephus_circle(int n, int m) {
    int *a = (int *)malloc(n * sizeof(int)); // 动态分配内存给数组
    for (int k = 0; k < n; ++k)
        a[k] = 0;

    int i = 0;
    int count = 0;
    
    while (count < n - 1) {
        if ((a[i % n] == 0) && (--m == 0)) { // 当前位置未被淘汰且已达到报数上限
            printf("%d ", i % n);             // 输出被淘汰的人的位置索引
            a[i % n] = 1;                     // 将当前位置标记为已淘汰
            m = M;                            // 更新下一个报数上限M
            count++;
            m--;
        }
        i++;                                  // 移动到下一位置继续判断
        if (m <= 0)                           // 如果当前轮次结束重置计数值
            m = M;
    }

    free(a);
    return i % n;                             // 返回最后一个存活者的位置
}

此段代码实现了基本功能，即初始化所有人的生存状态，并根据指定参数`n`(人数)`m`(初始报数上限)，依次输出每次被移除个体的位置直至只剩一人[^3]。

#### 3. 链表方式下的优化版本
为了提高可读性和灵活性，还可以采用单向循环链表的方式来表示参与者之间的关系。这种方式不仅能够直观反映实际物理布局，而且便于处理动态增删节点的操作。

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

Node* create_node(int value){
    Node* node=(Node*)malloc(sizeof(Node));
    node->data=value;
    node->next=NULL;
    return node;
}

void solve_josephus_problem_with_list(int num_people,int step_size){
    if(num_people<=0 || step_size<1)return ;

    /* 创建头结点 */
    Node *head=create_node(0),*tail=head,*current,*prev;
    head->next=head;

    /* 构建完整的环形列表 */
    for(int i=1;i<num_people;++i){
        tail->next=create_node(i);
        tail=tail->next;
        tail->next=head;
    }

    current=head;
    prev=current;

    do{
        for(int cnt=1;cnt<step_size;++cnt){
            prev=current;
            current=current->next;
        }

        printf("Eliminated person at position:%d\n",current->data);

        /* 删除选定节点 */
        prev->next=current->next;
        
        /* 若删除的是头部，则更新头部指针 */
        if(current==head)head=current->next;

        /* 清理释放空间 */
        free(current);
        current=prev->next;
    }while(prev!=current);

    printf("\nThe last survivor is located at position:%d.\n",current->data);
}

这段改进后的程序利用了链表结构的优势，使得逻辑更加清晰易懂的同时也提高了执行效率[^5]。