约瑟夫问题(Josephus problem)的klog(n)解法

  1. 云栖社区>
  2. 博客>
  3. 正文

约瑟夫问题(Josephus problem)的klog(n)解法

尹宁 2018-06-14 15:12:14 浏览2849
展开阅读全文

约瑟夫问题是一个经典的算法问题,其解决过程涉可能用到的数据结构有数组、链表,涉及的算法包括模拟、递归、递推、动态规划等等,因此非常适合做一道面试题。

 

问题描述:

首先n个候选人围成一个圈,依次编号为0..n-1。然后指定一个正整数k,并0号候选人开始按从1到k的顺序依次报数,n-1号候选人报数之后,又再次从0开始。当有人报到K时,这个人被淘汰,从圈里出去。下一个人从1开始重新报数。重复上述过程,直至剩下一个人,求问最后这一人在最开始的圈中的编号。

 

例如,n=5(共有5个人),k=3(每次第三个人出列)时,问题的解是3(最后剩下编号为3的人)

 

关于其背景的描述可以参考 百度百科-约瑟夫问题Wikipedia-Josephus problem

 

约瑟夫问题存在多种解法:

  1. 最朴素的使用数组的模拟方法,时间复杂度O(n^2)
  2. 使用链表(队列

网友评论

登录后评论
0/500
评论
尹宁
+ 关注