约瑟夫环问题及其尽可能的优化

约瑟夫问题描述:
n个人围成一个圈,编号为0,1,2,..,n-1,设定一个常数k,然后从0号开始从1依次报数,报到k的那个人退出圈,后面一个人继续从1开始报数,依次类推,求最后剩下的人的编号

方法1:
模拟游戏过程的方法,将n个人串成一个循环链表,不停地去遍历链表,直到最后剩下一个结点。
优点:方法直观,写起来很容易
缺点:模拟了全部游戏过程,非常耗时,并且在n较大时占用较大的内存空间

方法2:
数学递推的方式。
假设当前k<=n,记n个人的时候最后剩下的人的编号是f(n)。因为整个游戏过程存在大量重复的行为,我们自然可以想到将f(n)化成前面求出来的量。
当前圈是0,1,2,…,k-2,k-1,k,…,n-2,n-1
我们将第一个数到k的人去除,那么圈就变成
0,1,2,…,k-2,k,…n-2,n-1(其中k-1被去除)
因为此时整个圈的人数变成了n-1,我们就可以往f(n-1)上靠拢。
由于接下来开始报数的人是编号k的人。而f(n-1)表示的开始报数的是其编号0的人,那么我们这里就作一个映射
k,k+1,…….,n-2, n-1, 0, 1,……….,k-2 (将去掉一个人后的圈尾放到圈头)
0,1,……….,n-2-k,n-1-k,n-k,n-k+1,…..,n-2 (这是正常的得到f(n-1)的圈子)
观察上面一个映射我们可以发现f(n) = (f(n-1) + k) % n。意思就是说f(n-1)中的编号在加上k后就能转换成f(n)中的编号,并且如果>=n的话还要取模n使其在范围[0, n-1]之间。

由于递推或递归时都会遇到f(n)的n比k小的情况,所以我们要继续分析当n<k时上述递推式能不能继续满足。
假设当前k>n,那么第一次踢人时可能走完一圈,也有可能走完好几圈,所以第一个被踢的人编号是k mod n – 1。记:
p = k mod n (注意为了与前面一致,这里先不减1)
此时圈变成
0, 1, 2, …, p-2, p, …, n-2, n-1 (其中p-1被去除)
和前面一样,将圈尾调到圈头:
p, p+1, ……, n-2, n-1, 0, 1, …….., p-2 (这是f(n)的圈子去掉一个人后调整得到的)
0, 1, ………, n-2-p, n-1-p, n-p, n-p+1, …., n-2 (这是正常的得到f(n-1)的圈子)
观察可得到递推式f(n) = (f(n-1) + p) % n。即
f(n) = (f(n-1) + k%n) % n
因为最后都有个模n的操作,所以两个表达式是一样的,所以k和n不用比较大小关系,两个递推式都可以用。

方法2的优化1:
首先考虑对两个递推式的优化
f(n) = (f(n-1) + k) % n
f(n) = (f(n-1) + k%n) % n
为减少计算量,我们自然是要选用第一个表达式。
进一步考察模n这一操作的来源,发现在f(n-1)+k和f(n-1)+k%n后由于部分数据出现超过[0, n-1]这个闭区间,所以才需要模n使其保持在区间内。
我们分开来考虑,对f(n-1)+k,由于f(n-1)是在[0, n-2]这个区间内的,所以在+k后只需简单地判断其是否>=n即可,如果>=n就减上n,否则不需要进行操作。这样就避免了模n这个耗时的操作。
对k>n的情况,即表达式为f(n-1) + k%n时。虽然f(n-1)的确在区间内,但k比较大,导致相加后超过范围,由于不能确定k到底大到什么程度,所以这里不可避免地要对k取n的模,那么取n的模后加上f(n-1)还会超过n吗?会的。所以和上面一样进行一个判断,需要的话减n即可。
综合起来,就是
if k > n:
k %= n
f(n) = f(n-1) + k
if f(n) >= n:
f(n) -= n

由于递推的过程中始终是前项推后项,所以出于节省空间的考虑可以不用建立dp数组,直接保存上次得到的值不断循环更新即可。

方法2的优化2:
前述优化已经能较快的解决大部分问题了,但是当n非常非常大的时候还是会比较耗时。为了进一步加快速度,我们重新分析最开始考虑递推的过程。
我们将n个的圈按游戏规则踢掉一个后转化成了n-1的圈,从而得到递推表达式。那么我能在第一圈未结束时尽可能踢掉更多的人吗?
当k < n时,圈子一次性能踢掉n / k个人,此时圈子变成:
0, 1, 2, …, k-2, k, …, 2k-2, 2k, …, 3k-2, 3k, …, [n/k]k-2, [n/k]k, …, n-2, n-1 (其中k-1,2k-1,3k-1,…,[n/k]k-1都被踢掉了)
因为踢掉了n / k个人,所以f(n)应该由f(n – n / k)递推得到。那么此时如何去找他们之间的映射关系呢?
踢掉n/k个人后,接下来开始报数的是[n/k]k,并且从[n/k]k到n-1的人数是肯定小于k的。此时按前述的方法调整圈子:
[n/k]k, [n/k]k+1, …, n-2, n-1, 0,1, …, k-2, k, …, 2k-2, 2k, …, [n/k]k-2 (注意其中被踢掉的人)
0, 1, ….., n-2-[n/k]k, n-1-[n/k]k, n-[n/k]k…. (后面先不写,先分析前面的映射关系)
根据前面写出的一部分,我们可以得到递推关系 f(n) = (f(n-n/k) + [n/k]k) % n
需要注意两点:
1.递推是f(n)与f(n-n/k)之间
2.偏移量是[n/k]k
这里的偏移量很好理解,前面每踢一个人,后面偏移时都要多一个k,因为踢了[n/k]个人,所以要偏移[n/k]k。还有越过n-1时要模n控制区间。
继续往后分析,在调整后的圈子里0,1,2…并不是一直连续的,到了k-2,k时可以发现因为k-1被踢了,所以此时递推式中要补偿1,变成了f(n) = (f(n-n/k) + [n/k]k + 1) % n。再到了2k时则变成了f(n) = (f(n-n/k) + [n/k]k + 2) % n。依次类推可以得出f(n-n/k)的值即n-n/k个人时剩余的那个人的编号是非常影响f(n)的递推的,而且是分段性影响。
我们继续往后写一段映射关系,以期确定分段的端点。
0, 1, …, k-2, k, … (原n个人圈子踢人后调整后后面一段)
n-[n/k]k, n-[n/k]k+1, …, n-[n/k]k+k-2, n-[n/k]+k, … (n-n/k个人的圈子去掉前面一段)
由于原圈子在过0之后我们可以得到一个很明显的规律,即每过k个补偿就加1,所以
当f(n-n/k) >= n-[n/k]k时,
f(n)=(f(n-n/k) + [n/k]k + p) % n
其中p表示补偿量,p = (f(n-n/k) – (n – [n/k]k)) / k。先减去(n-[n/k]k)是为了将其编号映射到原圈子中,再通过除以k确定后面踢了几个人来得到补偿量
那么没有越过0呢,即映射到原圈子后编号在0的左边(不是指负数),此时因为没有额外的踢人,所以补偿量一直为0,但是不能代上面的公式,因为此时p算出来为负数。即
当f(n-n/k) < n-[n/k]k 时
f(n)=f(n-n/k) + [n/k]k
并且此时因为映射后的编号没有过0,所以不需要模n

当k >= n时,因为遍历一次圈子无法踢人,要遍历两次或几次才能踢一个人,不满足优化2中提到的遍历一圈就踢几个人,所以此时按优化1处理即可。

综上可得如下伪代码:
if k > n:
k %= n
f(n) = f(n-1) + k
if f(n) >= n:
f(n) -= n
else if f(n-n/k) >= n-[n/k]k:
p = (f(n-n/k) – (n – [n/k]k)) / k
f(n)=(f(n-n/k) + [n/k]k + p) % n
else:
f(n)=f(n-n/k) + [n/k]k

以上是一次循环内的内容,循环的终点即是递推出n为止。由于这里与前面递推有所不同,并不是相邻项f(n)和f(n-1)之间的递推,而是相差了一个n/k。问题在于这个n/k会不断的变化,所以还是要设置dp数组保存前面的各项值,以供随时调用。

优先2中由于一次踢掉了尽可能多的人,所以n衰减的速度非常快,尤其是n较大且k较小的时候,运算次数远小于优化1.

发表评论