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

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

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

// 定义节点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;

// 创建节点
Node *createNode(int data) {
    Node *newNode = (Node *) malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建环形链表
Node *createList(int n) {
    Node *head = createNode(1);
    Node *prev = head;
    for (int i = 2; i <= n; i++) {
        Node *newNode = createNode(i);
        prev->next = newNode;
        prev = newNode;
    }
    prev->next = head;  // 链表头尾相连，形成环形链表
    return head;
}

// 算法一：顺序删除
int josephus1(Node *head, int m) {
    Node *p = head;
    while (p->next != p) {  // 当链表中只剩一个节点时退出循环
        for (int i = 1; i < m - 1; i++) {
            p = p->next;    // 找到第m个节点的前一个节点
        }
        Node *del = p->next;    // 删除第m个节点
        p->next = del->next;
        printf("%d ", del->data);
        free(del);
        p = p->next;    // 将p指向下一个节点
    }
    printf("%d\n", p->data);
    return p->data;
}

// 算法二：循环链表
int josephus2(Node *head, int m) {
    Node *p = head;
    while (p->next != p) {  // 当链表中只剩一个节点时退出循环
        for (int i = 1; i < m - 1; i++) {
            p = p->next;    // 找到第m个节点的前一个节点
        }
        Node *del = p->next;    // 删除第m个节点
        p->next = del->next;
        printf("%d ", del->data);
        free(del);
        p = p->next;    // 将p指向下一个节点
    }
    printf("%d\n", p->data);
    return p->data;
}

// 算法三：递推公式
int josephus3(int n, int m) {
    int p = 0;
    for (int i = 2; i <= n; i++) {
        p = (p + m) % i;
    }
    return p + 1;
}

// 算法四：数学归纳法
int josephus4(int n, int m) {
    if (n == 1) {
        return 1;
    } else {
        return (josephus4(n - 1, m) + m - 1) % n + 1;
    }
}

// 算法五：Bit操作
int josephus5(int n, int m) {
    int p = 0;
    for (int i = 2; i <= n; i++) {
        p = (p + m) & (i - 1);
    }
    return p + 1;
}

// 主函数
int main() {
    int n = 10;
    int m = 3;
    printf("顺序删除：");
    josephus1(createList(n), m);
    printf("循环链表：");
    josephus2(createList(n), m);
    printf("递推公式：");
    printf("%d\n", josephus3(n, m));
    printf("数学归纳法：");
    printf("%d\n", josephus4(n, m));
    printf("Bit操作：");
    printf("%d\n", josephus5(n, m));
    return 0;
}

在这个程序中，我们首先定义了一个节点结构体，并定义了createNode函数用于创建节点。然后我们定义了createList函数用于创建指定个数的环形链表。

接着，我们实现了五种不同的算法来解决敢死队问题。其中，算法一和算法二都是基于链表的顺序删除和循环删除实现的，算法三是基于递推公式实现的，算法四是基于数学归纳法实现的，算法五是基于Bit操作实现的。

最后，在主函数中，我们分别使用五种算法解决了一个10个人的敢死队问题，并输出了解决结果。