首页 > 试题广场 >

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

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

热度指数：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

输出

备注:

算法知识视频讲解

Huster水仙

发表于 2023-02-13 22:28:53

约瑟夫问题递推法模拟的时间开销太大不得不回头考虑递推关系：将编号改为从0开始,记f(n,m)为原问题的解由于第一次遍历了0~(m-1)%n，则第二次遍历相当于将整个队伍循环左移了k位(k=m%n) 所以子问题f(n-1,m)的解循环右移k位即为原问题的解f(n,m) f(n, 展开全文

热爱洗屁屁的羊

发表于 2021-07-18 02:36:40

约瑟夫问题：在n个人中（编号为1~n）,从第一个人开始数数，每当计数为m时，此人为A，A自杀踢出；然后下一个从新从1开始计数，当再次数到m时，此人为B，B自杀踢出。当最后剩下一人时结束。模型等化：将n个人等效为一个环形链表。每次踢出一个人时，链表长度就减小1。方法一：递归方法利用递归方法计算存活展开全文