wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

杂项

启发式合并

高精度

一些经典问题

约瑟夫环

[[ item.c ]]

约瑟夫环

## 约瑟夫环
**问题描述**
从标记$$1\sim n$$的圆圈，第$$1$$个人开始，每个人依次顺时针地杀死他旁边的，**仍然存活的人**
具体地，第一轮，编号是$$1$$的杀死编号$$2$$，接着编号$$3$$杀死编号$$4$$，以此类推
直到只有一个人幸存下来，问幸存下来的这个人，他的初始编号是多少？

**算法分析**
考虑递归过程中，子问题和原问题之间，**编号的映射关系**

> 子问题中，假设最后存活的人的编号是`J`，对应到原问题，编号是多少呢？

**对于偶数的情况**
![](/media/content_img/josephus01.png)

**对于奇数的情况**
![](/media/content_img/josephus02.png)

递推关系如下
```math
\displaystyle
\begin{cases}
J(1) = 1 \\
J(2n) = 2J(n) - 1 \\
J(2n+1) = 2J(n) + 1
\end{cases}
```

**封闭形式**
根据$$J(2n) = 2J(n) - 1$$这样的递推形式，考虑$$J(n)$$的封闭形式，不妨先看$$n = 2^m$$的情形，$$J(2^m) = ?$$
> 当$$n = 2^m$$时
```math
\displaystyle
J(n) = 2J(\dfrac{n}{2}) - 1 = 2\left( 2J(\dfrac{n}{2^2}) - 1 \right) - 1 \\
= 2^2 J(\dfrac{n}{2^2}) - 2^1 - 2^0 = 2^3 J(\dfrac{n}{2^3}) - 2^2 - 2^1 - 2^0 \\
= 2^m J(1) - 2^{m-1} - \cdots - 2^1 - 2^0 = 1
```

可知形如$$J(2^m) = 1$$

> 对于一般形式的递推，怎么求？

不难发现，$$J(2n+1) - J(2n) = 2$$，即可以先求出偶数项，然后根据偶数项来推相邻的奇数项

> 实际上
```math
\displaystyle
J(2^m+1) = J(2^m) + 2 = 2 + 1 \\
\quad \\
J(2^m + 3) = J(2^m + 2) + 2 = 2J(2^{m-1} + 1) - 1 + 2 \\
=2\left( J(2^{m-1}) + 2 \right) + 1 = 6 + 1
```

以此归纳，不妨设$$n = 2^m + l$$，$$0 \leqslant l < 2^m$$，即将$$n$$分成若干个$$2^m$$段
记$$l$$是剩下的**不完整**的段，我们有$$J(2^m + l) = 2l + 1$$

看完文章有啥想法

算法小站

wiki 主题

杂项

约瑟夫环

目录