首页 > 试题广场 >

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

[编程题]环形链表的约瑟夫问题(进阶)
  • 热度指数：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

输出

3

备注:
算法知识视频讲解
添加回答
Python
牛客968728591号头像 牛客968728591号

利用递推解决约瑟夫环问题 

n, m = map(int, input().split())
live = 0
for i in range(2, n+1):
    live = (live+m)% i    # 活下来的犹太人（同一个人a）倒数第i轮中所处的位置与倒数第i-1轮中所处的位置之间的关系
print(live+1)
发表于 2020-04-05 18:11:29 回复(0)
Python
牛客979233817号头像 牛客979233817号 
n,m=map(int,input().split(" "))
r=0
for i in range(2,n+1):
        r=(r+m)%i
print(r+1)
约瑟夫问题有数学公式可以带入计算，正常循环的方式反而会导致超时
发表于 2020-03-23 10:50:37 回复(0)
提交观点

问题信息

链表 数学
上传者：小小
难度：
3条回答 6021浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号