耶稣有15个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：15人围坐一圈，从第一个开始报号：1，2，3，1，2，3……，凡是报到“3”就退出圈子，最后留在圈内的人就是出卖耶稣的叛徒，请找出它原来的序号。（C语言）这其实是一个约瑟夫环的问题。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：15个人（序号0~14)，从0开始报数，报到2的退出，剩下的人继续从0开始报数。求叛徒的序号。

我们知道第一个人(序号一定是3%15-1=2) 出列之后，剩下的14个人组成了一个新的约瑟夫环（以序号为3%15=3的人开始）:
  3  3+1  3+2  ... 15-2, 15-1, 0, 1, 并且从3开始报0。
现在我们把他们的编号做一下转换：

3     --> 0
3+1   --> 1
3+2   --> 2
...
...
3-3   --> 15-2
3-2   --> 15-1解x' ----> 解为x


注意<x’就是最终的解>

变换后就完完全全成为了14个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是15个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+3)%15

如何知道14个人报数的问题的解？对，只要知道13个人的解就行了。13个人的解呢？当然是先求12个人的情况 ---- 这显然就是一个倒推问题！

好了，思路出来了，下面写递推公式：
令f表示i个人报数报m退出最后剩下的序号，最后的结果自然是f[15]

递推公式
f[1]=0;
f=(f[i-1]+m)%i;  (i>1)

有了这个公式，我们要做的就是从1到15的顺序算出f的数值，最后结果是f[15]。因位序号是从1开始，我们只需输出f[15]+1
由于是逐级递推，不需要保存每个f，程序也是异常简单：

1. #import<Foundation/Foundation.h>
   
2. 
   
3. int main(int arge, const char * argv[])
   
4. {
   
5.         int  s=0;                                 
   
6.         for (i=2; i<=15; i++) s=(s+3)%i;         
   
7.         printf ("叛徒的编号是 %d\n", s+1);
   
8.      return 0;
   
9. }

复制代码

是不是超级简单！比链表，递归什么的都简单到家了，所以说明数学还是很重要的，真的要学好编程，数学也不能落下呢！

耶稣有15个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：15人围坐一圈，从第一个开始报号：1，2，3，1，2，3……，凡是报到“3”就退出圈子，最后留在圈内的人就是出卖耶稣的叛徒，请找出它原来的序号。（C语言）这其实是一个约瑟夫环的问题。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：15个人（序号0~14)，从0开始报数，报到2的退出，剩下的人继续从0开始报数。求叛徒的序号。

我们知道第一个人(序号一定是3%15-1=2) 出列之后，剩下的14个人组成了一个新的约瑟夫环（以序号为3%15=3的人开始）:
  3  3+1  3+2  ... 15-2, 15-1, 0, 1, 并且从3开始报0。
现在我们把他们的编号做一下转换：

3     --> 0
3+1   --> 1
3+2   --> 2
...
...
3-3   --> 15-2
3-2   --> 15-1解x' ----> 解为x


注意<x’就是最终的解>

变换后就完完全全成为了14个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是15个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+3)%15

如何知道14个人报数的问题的解？对，只要知道13个人的解就行了。13个人的解呢？当然是先求12个人的情况 ---- 这显然就是一个倒推问题！

好了，思路出来了，下面写递推公式：
令f表示i个人报数报m退出最后剩下的序号，最后的结果自然是f[15]

递推公式
f[1]=0;
f=(f[i-1]+m)%i;  (i>1)

有了这个公式，我们要做的就是从1到15的顺序算出f的数值，最后结果是f[15]。因位序号是从1开始，我们只需输出f[15]+1
由于是逐级递推，不需要保存每个f，程序也是异常简单：

1. #import<Foundation/Foundation.h>
   
2. 
   
3. int main(int arge, const char * argv[])
   
4. {
   
5.         int  s=0;                                 
   
6.         for (i=2; i<=15; i++) s=(s+3)%i;         
   
7.         printf ("叛徒的编号是 %d\n", s+1);
   
8.      return 0;
   
9. }

复制代码

是不是超级简单！比链表，递归什么的都简单到家了，所以说明数学还是很重要的，真的要学好编程，数学也不能落下呢！