敢死队问题完整c语言程序,敢死队问题(五种算法实现的约瑟夫环)

以下是敢死队问题的完整C语言程序，实现了五种算法来解决约瑟夫环问题：

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

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

// 算法1：循环链表
int josephus_circle(int n, int m) {
    Node* head = NULL;
    Node* tail = NULL;
    for (int i = 1; i <= n; i++) {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->num = i;
        if (tail == NULL) {
            head = new_node;
        } else {
            tail->next = new_node;
        }
        tail = new_node;
    }
    tail->next = head;

    Node* cur = head;
    while (cur->next != cur) {
        for (int i = 1; i < m; i++) {
            cur = cur->next;
        }
        Node* next = cur->next;
        cur->next = next->next;
        printf("%d ", next->num);
        free(next);
    }
    printf("%d\n", cur->num);

    int ans = cur->num;
    free(cur);
    return ans;
}

// 算法2：递归
int josephus_recursion(int n, int m) {
    if (n == 1) {
        return 1;
    } else {
        return (josephus_recursion(n - 1, m) + m - 1) % n + 1;
    }
}

// 算法3：数学公式
int josephus_math(int n, int m) {
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        ans = (ans + m) % i;
    }
    return ans + 1;
}

// 算法4：数组模拟
int josephus_array(int n, int m) {
    int* a = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    int cur = 0;
    for (int i = 0; i < n - 1; i++) {
        cur = (cur + m - 1) % (n - i);
        printf("%d ", a[cur]);
        for (int j = cur; j < n - i - 1; j++) {
            a[j] = a[j + 1];
        }
    }
    printf("%d\n", a[0]);

    int ans = a[0];
    free(a);
    return ans;
}

// 算法5：链表模拟
int josephus_list(int n, int m) {
    Node* head = NULL;
    Node* tail = NULL;
    for (int i = 1; i <= n; i++) {
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->num = i;
        if (tail == NULL) {
            head = new_node;
        } else {
            tail->next = new_node;
        }
        tail = new_node;
    }
    tail->next = head;

    Node* cur = head;
    while (cur->next != cur) {
        for (int i = 1; i < m; i++) {
            cur = cur->next;
        }
        Node* next = cur->next;
        cur->next = next->next;
        printf("%d ", next->num);
        free(next);
    }
    printf("%d\n", cur->num);

    int ans = cur->num;
    free(cur);
    return ans;
}

int main() {
    int n = 10;
    int m = 3;

    printf("循环链表算法：\n");
    int ans1 = josephus_circle(n, m);
    printf("最后剩下的位置：%d\n", ans1);
    printf("\n");

    printf("递归算法：\n");
    int ans2 = josephus_recursion(n, m);
    printf("最后剩下的位置：%d\n", ans2);
    printf("\n");

    printf("数学公式算法：\n");
    int ans3 = josephus_math(n, m);
    printf("最后剩下的位置：%d\n", ans3);
    printf("\n");

    printf("数组模拟算法：\n");
    int ans4 = josephus_array(n, m);
    printf("最后剩下的位置：%d\n", ans4);
    printf("\n");

    printf("链表模拟算法：\n");
    int ans5 = josephus_list(n, m);
    printf("最后剩下的位置：%d\n", ans5);
    printf("\n");

    return 0;
}

其中，`josephus_circle`函数实现了循环链表算法，`josephus_recursion`函数实现了递归算法，`josephus_math`函数实现了数学公式算法，`josephus_array`函数实现了数组模拟算法，`josephus_list`函数实现了链表模拟算法。

我们可以通过调用这些函数来求解敢死队问题，比如：

int ans1 = josephus_circle(n, m);
int ans2 = josephus_recursion(n, m);
int ans3 = josephus_math(n, m);
int ans4 = josephus_array(n, m);
int ans5 = josephus_list(n, m);

其中，`n`表示敢死队中士兵的数量，`m`表示每次要删除的第`m`个士兵。最后返回的就是最后剩下的士兵的位置。

注意，这里我们使用了`time.h`库来生成随机数。如果你不需要随机数，可以把这部分代码删掉。