周末到了，首先祝大家周末愉快。可怜我周末都没得休息，继续努力 ：）大家该哈皮的去哈皮吧。

昨天，其实从前天开始就开始准备约瑟夫环，昨晚就准备开始写，不过想来想去对其数学推导出递推式还是没有想明白。大家有空帮忙看看，到底这个递推式是怎么出来的呢？我下面会一步步将自己的思考列下来。多谢多谢。

一开始将题目和模拟法稍微写一下，之后是关于数学方法的疑惑，大家可以直接略过上面的一些内容，跳到关键部分。 

【题目】 

约瑟夫环问题，每一个学习过数据结构或者C语言的人应该都会遇到过的问题。不论是在课本的教授内容中，还是在习题里面，都应该会出现过它的身影。 

基本的题目内容如下：

n个人围成一圈，编号从1到n，报数1，2，3，从编号为1的人开始报数，报到3的离开，下面的人接着从1开始报数，依次下去，写程序求最后剩下来的一个人编号是几。

这里题目中报数为到3为止，其实可以扩展到m。也就是n个人，报到m的人出列，同时也可以扩展到以某一个人为开始，而并不是从第1个人开始。

【模拟法】

一般在数据结构课上遇到这个问题的时候，是讲解循环链表的时候，这个题目是用来检验循环链表学习的结果的。所以一开始我们用最“朴素”的方法来解决。

一般这种方法，被称之为模拟法，也就是模拟问题发生的过程，直到得到最后的结果，这种解法是最容易想到的，但是一般也是效率最低的。

使用模拟法来解决，我们可以使用循环链表，也可以使用数组来模拟循环。这里我们使用循环链表，循环链表尽管比数组要写得麻烦，但是思考起来简单直观。

解决问题的核心步骤如下：

1．  建立一个循环链表，将每个节点进行编号

2．  开始报数，当报到3，删除该节点，然后接着报数

3．  直到只剩下最后一个节点的时候结束，将该节点的值输出

Code 

用数组的话，就是要实现循环，也就是当数到n的时候，不会再进行n+1，而是从1再开始。这个我们可以用取余数来得到。

开始模拟，首先第一个退出的人肯定是m%n，然后需要将之后的位置进行调整，（是否可以不进行调整？用标志位似乎也不是特别好）此时如果还要数组循环的话，就需要与n-1进行取余操作。然后一直这样继续。这里就不给出代码了。

这里我们只是输出了最后一个人的号码，其实也可以将出列的顺序打印出来，还可以将出列的节点保存起来，以后使用。

这里的时间复杂度为O(m*n)。 

【数学方法】

对于约瑟夫环问题，最简单的模拟法研究了意义也不是很大。我们的目的是找到更快的算法。也就是不使用模拟法，而是使用数学解法。

我差不多花了半天多的时间专门在这个上面（恩，其实还有晚上的部分时间。。。），在google上换了n个关键词（其实夸张了，也就四个，“约瑟夫环问题”，“约瑟夫环数学”，“约瑟夫环 数学原理”，“约瑟夫环 推导”）。搜到的结果包括关于约瑟夫环的国内的博客，百度知道（汗，其实还有搜搜问问），以及各个论坛都看了个差不多，基本上都是几篇帖子转来转去，对于关键的那个地方，大家基本统一的用“显而易见”来一句概括。（啊！！！我最讨厌这句了，我怎么就不能一眼看出，显而易见呢，各位神人啊，下次能不能讲得更明白些让我这种人也能够懂啊。。。） 

不过也有收获，就是找到几个不错的网站，同时也知道了原来《具体数学》中介绍过约瑟夫环，但是似乎只是介绍了m=2的情况，而将扩展没有介绍。不过现在也没用这本书，同时这段时间看来是没有空去啃了，等有空了，要读一读这本书，原来还是Knuth写的。

其实网上所有的说法，其答案是一致的，解释从本质上也是一致的，但是就是让人理解很难理解，当然，肯定有人理解的。。。

网上的一种说法，列出也是园子里面兄弟的链接：

http://www.cnblogs.com/woodfish1988/archive/2007/02/18/652251.html 

我这里就不摘录了，大家有兴趣可以按照链接过去看。我这里就开始写自己的理解。其实相差不大。

【思考过程】 

首先一开始的序列

序列1： 1, 2, 3, 4, …, n-2, n-1, n

此时出队列的第一个人，位置为k，号码肯定是m%n。这个应该没有问题，也就是取余操作使得数组类似能够有循环的功能。

此时序列2： 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n

此时k出队列，序列2中为n-1个人了。

根据序列2，得到序列3：

k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…, k-2, k-1

从序列2得到序列3很简单，也就是将k+1作为开始，然后将1连到n的后面，其实只是位置的不同，但是本质两个序列是一样的。所以同样，这里也是n-1个元素。

序列3可以映射得到序列4：

1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1

这里我就乱掉了，这个映射是可以做，但是映射关系是怎样的？

OK,先不管映射关系，我们继续来推导。

对于序列4，我们假设能够得到解，也就是最后一个退出的人的号码，设置为x。如果我们能够通过映射关系，将x在序列3中对应的号码x’求出来，那我们就可以得到序列3的解，因为序列3其实和序列2是同一个，所以序列2的解我们也就得到了，序列2就是序列1去掉一个k，这个k对于序列1的解没有任何影响，所以序列1的答案就是求出来的x’。

那关键就是如何通过x得到x’ ，也就是映射关系的问题。

对于序列4，如果我们要得到1到n-1序列中的值，我们也是做取余操作，只不过除数变为n-1了。

但是如何得到关系为 x'=(x+m)%n，从而得到递推式

f(i)=(f(i-1)+m)%i

还是没法理解出来。

f(1)=1肯定是

有没有谁能帮忙解惑一下，谢谢。。。