约瑟夫问题C语言代码实现

约瑟夫环是一个经典的算法问题，也称为“进圈游戏”。在这个游戏中，人们按顺序报数，从某个数字开始，每次到特定数值的人出圈，然后下一个人接着从头开始报数。当你遇到特定的数字（如7），则跳过它并继续下一个。

以下是使用C语言实现约瑟夫环的基本步骤：

#include <stdio.h>

void josephus(int n, int k) {
    int count = 0; // 当前轮次数
    int current = 1; // 当前报数者

    while (count < n - 1) { // 游戏直到只剩一人
        printf("%d ", current); // 输出当前报数者
        count++; // 增加计数
        current = (current + k - 1) % n; // 计算下一轮应该由谁报数，忽略k-1
    }
    printf("胜利者: %d\n", current); // 最后一个人就是胜利者
}

int main() {
    int n, k;
    printf("请输入人数(n)和报数间隔(k): ");
    scanf("%d %d", &n, &k);
    josephus(n, k);
    return 0;
}

相关问题

约瑟夫问题c语言代码链表

下面是一个使用链表实现约瑟夫问题的C语言代码：

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

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

Node* create(int n) {
    Node *head = NULL, *tail = NULL;
    for (int i = 1; i <= n; i++) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->num = i;
        p->next = NULL;
        if (head == NULL) {
            head = p;
            tail = p;
        } else {
            tail->next = p;
            tail = p;
        }
    }
    tail->next = head; // 链表首尾相接
    return head;
}

void josephus(Node *head, int m) {
    Node *p = head, *pre = NULL;
    while (p->next != p) {
        for (int i = 1; i < m; i++) {
            pre = p;
            p = p->next;
        }
        pre->next = p->next;
        printf("%d ", p->num);
        free(p);
        p = pre->next;
    }
    printf("%d ", p->num);
    free(p);
}

int main() {
    int n, m;
    printf("请输入总人数n和出圈的数字m：");
    scanf("%d%d", &n, &m);
    Node *head = create(n);
    josephus(head, m);
    return 0;
}

使用方法：

1. 编译运行上述代码；
2. 根据提示输入总人数n和出圈的数字m；
3. 程序输出每个出圈的人的编号，最后输出剩下的最后一个人的编号。

运用循环单链表实现约瑟夫问题c语言代码

约瑟夫环是一个经典的算法问题，通常用于演示递归和模运算的概念。在循环单链表中实现约瑟夫问题，首先需要创建一个节点结构和一个头指针，然后模拟人们从列表中按顺序移除并跳过指定步骤的过程。

以下是一个简单的C语言代码示例：

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

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

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

void josephusProblem(Node* head, int steps) {
    if (head == NULL || steps <= 0) {
        printf("Invalid input.\n");
        return;
    }

    Node* victim = head;
    for (int i = 1; i <= steps - 1; i++) {
        victim = victim->next;
    }
    
    while (victim != NULL) {
        Node* temp = victim->next;
        free(victim);
        victim = temp;
        if (victim == NULL) {
            victim = head;
            while (victim->next != head) {
                victim = victim->next;
            }
        } else {
            for (int i = 1; i < steps; i++) {
                victim = victim->next;
            }
        }
    }
}

// 添加节点到链表
void appendToList(Node** head, int value) {
    Node* newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

int main() {
    Node* head = NULL;
    int n, steps;
    printf("Enter the number of people: ");
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        appendToList(&head, i);
    }
    printf("Enter the step count: ");
    scanf("%d", &steps);

    josephusProblem(head, steps);
    printf("The last person standing is at position %d\n", head->data);

    return 0;
}

在这个代码里，用户先输入人数和步骤数，然后程序会创建一个循环链表，并应用约瑟夫环算法。`josephusProblem`函数负责执行约瑟夫环的规则，最后输出存活的人及其位置。