约瑟夫问题的解答

约瑟夫问题是一个很臭名昭著的算法题,今天闲着没事在网上乱逛,又看到了这个问题,在大脑里搜索,记忆中已经找不到这个算法的描述了,于是乎从0开始又做了一遍。这里是一个比较传统的算法,对题目描述的完全模拟,比较笨,复杂度姑且认为是o(n)吧。之后我会考虑江湖上曾经盛传的一个逆向思维的算法,貌似效率要好一点,我做出来了再写文章。

闲言少叙,说归正传。问题描述(来自互联网):n个人围成一圈,每人有一个各不相同的编号,选择一个人s作为起点,然后顺时针从1到k数数,每数到k的人退出圈子,圈子缩小,然后从下一个人继续从1到k数数,重复上面过程。求最后推出圈子的那个人原来的编号x。

解题思路(来自我本人):这明显是个循环问题,而且是可知的有限循环,循环次数n-1,所以就for吧。

一般来说从正向去考虑,头脑中出现如下场景:就是n个人排排坐,然后随便找个人,告诉他数1,然后他就数,接下来按照顺时针或者逆时针方向走下去,数了一圈又一圈,知道有个倒霉蛋数到k,当然他也可能是幸运儿,如果最后剩下的那个要被扔到河里之类的。基本就是这么个思路,然后按照数据结构的思想去建模,应该是个头尾相接的链表,然后元素被一个一个的拿掉。

至于算法,首先我需要构造一个n个人的数组,为了图省事,我把它做成2维的,如下:

1 => 1 => 1

2 => 2 => 2

3 => 3 => 3

...

n => n => 4

这是一张map,第一列是下标是内存偏移量,不可变,或者变起来麻烦,所以有了第二列,作为序号;第三列数字是这n个人的原始编号。这样构造数组的原因是,在运算过程中,人会不断的减少,所以序列的序号会变,我们变第二列,而最后我们需要知道这个人的原始序号,直接从第三列读取就OK了。

其实还有个办法就是把每次序号变化记录下来,这样会节约空间,但是我认为这些都不是核心的东西,所以无所谓,就这么办吧,如果有人追求完美可以搞一下。

然后就是从中一个一个的把元素抽掉,我们完全模拟题目描述:

设有n个人,编号为0,1,2...n-1,数1的人的编号是s,最后数到k的人出局(n,s和k是整数, -1< s

则,第一轮出局的人的编号是o (o = s + (k % n) - 1),此人出局;进入下一轮计算:s = o + 1,让o他之后的人编号向前滑动一个,覆盖o,n -= 1。根据新的s和k值进行计算,依此循环,直到n=2的时候,那个最后留下的人x = s,然后通过s的地址去那个2维数组里找到相应的号码就OK了。

以上就是这个最本,最直接的算法:写出来就是一个for(;n>1;n++) 的一个循环,具体的代码实现就不写了,很简单,有兴趣的同学可以试试。

接下来想一想那个江湖上盛传的一个逆向解答的,就是从n=2开始的算到n=n,这个算法的复杂度貌似会更低,稍后奉上,敬请期待。

标签:约瑟夫算法 Josephus 排列 数据结构 算法设计

添加新评论