C语言约瑟夫环问题如何求解？

理解约瑟夫问题

我们明确一下问题的描述：

N个人围成一圈，从某个指定的人开始报数，数到k的那个人就被淘汰，然后从下一个人重新开始报数，数到k的人再次被淘汰，如此循环，直到所有人都被淘汰,求最后剩下的人的初始位置。

举个例子： N = 5, k = 3 编号为1, 2, 3, 4, 5的人围成一圈。

1. 从1开始数：1, 2, 3 (淘汰3)
2. 从4开始数：4, 5, 1 (淘汰1)
3. 从2开始数：2, 4, 5 (淘汰5)
4. 从2开始数：2, 4 (淘汰4) 最后剩下的人是 2。

这个问题有两种经典的解法：

1. 模拟法（循环链表实现）：最直观,最容易理解。
2. 递归法：更高效,体现了问题的数学本质。

下面我们分别用C语言实现这两种方法。

方法一：模拟法（使用循环链表）

这是最符合问题描述的解法，我们创建一个循环链表来表示围成一圈的人，然后按照规则一步步淘汰,直到链表中只剩下一个节点。

算法思路

1. 创建节点：创建N个节点，每个节点代表一个人，并存储其编号,将这些节点链接成一个单链表。
2. 构建循环：将链表的最后一个节点的 next 指针指向第一个节点,形成一个循环链表。
3. 开始模拟：
   • 设置一个指针 current 指向链表的起始位置。
   • 设置一个计数器 count。
   • 循环执行，直到链表中只剩一个节点：
     • 从 current 开始，向前移动 count。
     • 当 count 达到 k-1 时，current 的下一个节点就是要被淘汰的人。
     • 删除 current 的下一个节点，并将 current 指针移动到被删除节点的下一个位置（即新的报数起点）。
     • 重置 count 为0,开始下一轮。

C语言实现

#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
    int number;      // 人的编号
    struct Node *next; // 指向下一个节点的指针
} Node;
// 创建循环链表
Node* createCircularList(int n) {
    if (n <= 0) {
        return NULL;
    }
    Node *head = (Node*)malloc(sizeof(Node));
    head->number = 1;
    Node *current = head;
    for (int i = 2; i <= n; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->number = i;
        current->next = newNode;
        current = newNode;
    }
    // 将最后一个节点的next指向头节点，形成循环
    current->next = head;
    return head;
}
// 使用循环链表模拟约瑟夫问题
int josephusSimulation(int n, int k) {
    if (n <= 0 || k <= 0) {
        return -1; // 无效输入
    }
    // 1. 创建循环链表
    Node *head = createCircularList(n);
    Node *current = head;
    // 2. 找到尾节点，以便于删除操作
    // 循环结束时，tail是最后一个节点，tail->next是head
    Node *tail = head;
    while (tail->next != head) {
        tail = tail->next;
    }
    // 3. 开始模拟，直到只剩一个节点
    while (current->next != current) {
        // 报数 k-1 次，找到要删除的节点的前一个节点
        for (int i = 1; i < k - 1; i++) {
            current = current->next;
        }
        // current->next 就是要被淘汰的节点
        Node *toDelete = current->next;
        printf("淘汰: %d\n", toDelete->number);
        // 删除节点
        current->next = toDelete->next;
        // 如果删除的是头节点，需要更新头节点指针
        if (toDelete == head) {
            head = toDelete->next;
        }
        // 移动current到下一个报数起点
        current = toDelete->next;
        // 释放被淘汰节点的内存
        free(toDelete);
    }
    // 最后剩下的节点的编号就是结果
    int winner = current->number;
    // 释放最后一个节点的内存
    free(current);
    return winner;
}
int main() {
    int n, k;
    printf("请输入总人数 N: ");
    scanf("%d", &n);
    printf("请输入报数 K: ");
    scanf("%d", &k);
    int winner = josephusSimulation(n, k);
    if (winner != -1) {
        printf("\n最后剩下的人的初始位置是: %d\n", winner);
    } else {
        printf("输入的参数无效，\n");
    }
    return 0;
}

代码分析

• Node 结构体：定义了链表的节点，包含 number（编号）和 next（指针）。
• createCircularList：一个辅助函数,用于创建包含N个节点的循环链表。
• josephusSimulation：核心模拟函数。
  • 它首先创建链表。
  • tail 指针用于辅助删除操作,它总是指向最后一个节点。
  • 外层 while 循环保证我们一直进行淘汰，直到只剩一人 (current->next == current)。
  • 内层 for 循环负责“报数”，移动 current 指针到要淘汰节点的前一个位置。
  • 删除节点并更新指针后，必须释放被删除节点的内存,否则会造成内存泄漏。
• main 函数：处理用户输入,调用模拟函数并打印结果。

方法二：递归法

递归解法更高效，时间复杂度为 O(N)，空间复杂度为 O(N)（由递归调用栈产生），它不需要显式地创建数据结构,而是通过数学公式来求解。

算法思路

设 f(N, k) 为N个人、报数为k时最后剩下的人的编号（编号从0或1开始）,我们推导递归公式：

1. 基本情况：如果只有1个人 (N=1)，那么最后剩下的就是他自己。f(1, k) = 0 (如果编号从0开始) 或 f(1, k) = 1 (如果编号从1开始)。

   
   （图片来源网络，侵删）

2. 递归情况：

   • 假设我们已经知道了 f(N-1, k) 的结果，即对于 N-1 个人，最后剩下的人的编号（在 N-1 人的编号体系下）。
   • 现在我们有N个人，第一个人被淘汰的人是编号为 k-1 的人。
   • 淘汰之后，剩下 N-1 个人，他们组成了一个新的圈，这个新圈的起始点是原来编号为 k 的人。
   • 我们现在需要解决的问题变成了：在一个新的、由 N-1 个人组成的圈里,最后剩下的人是谁？
   • 这个新圈的人的编号和原圈有一个偏移量，原圈中编号为 k 的人，在新圈中是编号为 0；原圈中编号为 k+1 的人，在新圈中是编号为 1,以此类推。
   • 如果 f(N-1, k) 给出了在新圈中最后剩下的人的编号（设为 x），那么这个人在原圈中的编号就是 (k + x) % N。

递归公式（编号从0开始）： f(N, k) = (f(N-1, k) + k) % N

递归公式（编号从1开始）： f(N, k) = (f(N-1, k) + k - 1) % N + 1

C语言实现

#include <stdio.h>
// 递归函数，编号从0开始
int josephusRecursive(int n, int k) {
    // 基本情况：当只有一个人时，他自己是幸存者，编号为0
    if (n == 1) {
        return 0;
    }
    // 递归情况：
    // 1. 先求解 n-1 个人的问题，得到幸存者在新圈中的编号 x
    int x = josephusRecursive(n - 1, k);
    // 2. 将新圈中的编号 x 映射回原圈的编号
    return (x + k) % n;
}
// 包装函数，使输入输出更符合直觉（编号从1开始）
int findTheWinner(int n, int k) {
    // 递归函数返回的是0-based的编号，所以结果+1
    return josephusRecursive(n, k) + 1;
}
int main() {
    int n, k;
    printf("请输入总人数 N: ");
    scanf("%d", &n);
    printf("请输入报数 K: ");
    scanf("%d", &k);
    int winner = findTheWinner(n, k);
    printf("\n最后剩下的人的初始位置是: %d\n", winner);
    return 0;
}

代码分析

• josephusRecursive：核心递归函数。
  • Base Case: if (n == 1) return 0; 这是递归的终止条件。
  • Recursive Step: return (x + k) % n; 完成了从 n-1 规模问题到 n 规模问题的转换。
• findTheWinner：一个包装函数。
  • 它调用核心递归函数，并将返回的 0-based 编号转换为 1-based 编号（通过 +1）,这样更符合人类的习惯。
• 优点：代码简洁，逻辑清晰，没有内存管理问题,效率高。
• 缺点：对于非常大的 n（接近递归深度限制），可能会导致栈溢出，但对于大多数情况,它都是最佳选择。

方法三：迭代法（基于递归公式）

为了避免递归可能带来的栈溢出问题，我们可以将递归公式改写为迭代（循环）的形式。

算法思路

我们从基本情况开始，逐步向上计算，直到算出 f(N, k)。

1. 初始化 survivor = 0 (对应 f(1, k))。
2. 从 i = 2 循环到 i = N：
   • 在每一步，我们都计算 f(i, k)。
   • 根据公式 f(i, k) = (f(i-1, k) + k) % i。
   • 用上一步的 survivor (即 f(i-1, k)) 来计算当前步的 survivor (即 f(i, k))。

C语言实现

#include <stdio.h>
// 迭代法求解，编号从0开始
int josephusIterative(int n, int k) {
    int survivor = 0; // f(1, k) = 0
    for (int i = 2; i <= n; i++) {
        survivor = (survivor + k) % i;
    }
    return survivor;
}
// 包装函数，使输入输出更符合直觉（编号从1开始）
int findTheWinner_Iterative(int n, int k) {
    return josephusIterative(n, k) + 1;
}
int main() {
    int n, k;
    printf("请输入总人数 N: ");
    scanf("%d", &n);
    printf("请输入报数 K: ");
    scanf("%d", &k);
    int winner = findTheWinner_Iterative(n, k);
    printf("\n最后剩下的人的初始位置是: %d\n", winner);
    return 0;
}

代码分析

• josephusIterative：核心迭代函数。
  • survivor 变量保存了当前规模 i 下的解。
  • for 循环从 i=2 开始，一步步将 survivor 的值更新为更大规模问题的解。
  • 这个方法的时间复杂度是 O(N)，空间复杂度是 O(1)，是所有方法中最高效、最节省内存的。
• findTheWinner_Iterative：同样是包装函数，用于将 0-based 结果转换为 1-based。

总结与对比

推荐：

• 如果是为了学习和理解问题本身，模拟法是最好的选择。
• 如果追求代码的简洁和数学之美，递归法非常优雅。
• 如果在实际应用中需要解决大规模问题，或者对性能和内存有严格要求，迭代法是最佳选择。