首页 > 试题广场 >

环形链表的约瑟夫问题

[编程题]环形链表的约瑟夫问题

热度指数：3198 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。

输入描述:

一行两个整数 n 和 m， n 表示环形链表的长度， m 表示每次报数到 m 就自杀。

输出描述:

输出最后存活下来的人编号(编号从1开始到n)

示例1

输入

5 2

输出

备注:

算法知识视频讲解

helloxuanbao

/*简单模拟*/
#include <stdio.h>
#include <stdlib.h>

typedef struct nd {
    int val;
    struct nd *next;
} node;

node *create_node(int val) {
    node *n = (node *) malloc(sizeof(node));
    n->val = val;
    n->next = NULL;
    return n;
}

node *josephus_kill(node *head, int m) {
    int tmp = 1;
    node *pre, *cur = head;
    while (cur->next != head)
        cur = cur->next;
    pre = cur;
    cur = head;
    while (cur->next != cur) {
        if (tmp == m) {
            tmp = 1;
            pre->next = cur->next;
            free(cur);
            cur = pre->next;
            continue;
        }
        pre = cur;
        cur = cur->next;
        tmp++;
    }
    return cur;
}

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);
    
    node dh = {0, NULL}, *cur = &dh;
    for (int i = 0; i < n; i++) {
        cur->next = create_node(i + 1);
        cur = cur->next;
    }
    cur->next = dh.next;
    cur = josephus_kill(dh.next, m);
    printf("%d\n", cur->val);
    return 0;
}

发表于 2022-05-08 20:05:57 回复(0)