首页 > 试题广场 >

环形链表的约瑟夫问题(进阶)

[编程题]环形链表的约瑟夫问题(进阶)

热度指数：1928 时间限制：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>

int get_num(int n, int m) {
    if (n == 1) {
        return 1;
    }
    return (get_num(n - 1, m) + m - 1) % n + 1;
}

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d\n", get_num(n, m));
    return 0;
}

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