说约瑟夫问题，网上是有一大堆各种各样的文章，想必也给出了各种各样的代码，但这却不能阻挡我写这篇博文的心啊，要知道我才刚刚开通个博客不写点什么总觉得空虚。。。。

那么就先来讲一下我所要解决的问题：N个人围坐成一圈，从1开始顺序编号；游戏开始，从第一个人开始由1到m的顺序报数，报道m的人退出圈外，问最后留下来那个人原来的序号。

（百度了一下发现，原题目不是推出圈外而是“39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式”。。。）

好吧回归正题，我们继续讲这个算法。

在这里我们用c++语言来实现这个算法。网上有人给出了递归算法，那么我这里就讲一种我最开始想到的方法吧。（好吧其实是那个递归的我需要一点时间理解。。。）

首先我们来理清一下思路。假设有10个人，那么我们容易想到用一个数组。所以先得有一个数组。那么怎么样去判断这个人还在不在？我们可以先把数组元素初始化为1，每当一个人出局，就把相应元素设置为0。

然后呢，我们增加一个变量来统计淘汰的人数，一旦到了14人，就是（人数-1），就不用再继续啦。

现在我们就开始编写c++代码。

首先还是引入头文件什么的，这里说明一下，我们这里就先不采用动态创建数组，我们假设一开始就知道有多少人，报到数字几要出局。因此我们这里定义两个常量（准确地说是文本替换），一个是人数all，一个是报到要出局的数字，定义为out。

#include <iostream>
using namespace std;
#define all 10
#define out 8

显然我们这里设置它人数为10人，报到数字8就要出局。

int people[all];
int k=0,i,j,flag=1;

k是一个从0开始的计次，k%all就是当前正在检验的人的序号（注意，这里说是检验，是因为这个数组元素不一定有报数的资格。），而flag是一个标示，用于判断是否要退出循环。j用于统计被淘汰了多少人，i的话。。。。。似乎很常见，不介绍了。这几个变量我们等下看具体实现的时候会更清楚。

然后对数组进行初始化：

for(i=0;i<all;i++){
        people[i]=1;
    }

然后把i，j置零。

i=0;
j=0;

准备工作就完成了，下面开始真正这个算法。

    while(1){
        if(people[k%all]){
            i++;
            if(i==out){
                people[k%all]=0;
                i=0;
                j++;
            }            
        }
　　　　　k++;
        if(j==all-1){
                flag=0;
            }
        if(!flag){
            break;
        }    
    }

下面来说说这个代码。

while（1）就是要让他死循环。。

上文提到k，这是从零开始的一个变量，表示当前正在检验第k%n个数组元素。考虑到为什么是k%n，因为考虑到他是一个循环报数的过程。

if(people[k%all])

这是为了看看这个人元素是不是0，是0就没有报数资格了。

如果有的话，那么就i++。

如果什么时候i=out了，就证明这个人要退出圈外。也就是把数组相应元素设置为0。并且j++，记住j是用来记录淘汰人数的。做完这一步的话k要自增，表示要检验下一个。

那么这个循环会不断地跑啊跑。。。。。一直到j=all-1，也就是说，这个人淘汰了之后，场上就只剩下一个人了！！！！我们就要跳出循环了，所以设置flag=0。跳出循环。

但我们还要看看剩下的是哪一个。。。所以还得加个for循环找出剩下的。

for(i=0;i<all;i++){
    if(people[i]){
        cout<<i+1;
    }
}

至于他为什么是i+1。。。。因为序号是从1开始标号的。

那么理论上教程就要结束了，但是既然写博客就不能那么简单。。。。。。。

上面的是程序直接输出一个结果，不够生动有趣。

为了生动有趣，我还写了个可以动的演示过程。。。。。

代码我会一起打包放在后面。。。。。这里截几张图。。。

这是运行的时候

 瞬间高大上有木有。。。。。。。

好啦那么到这里这篇东西就写完了。。。。。。祝大家学习进步咯。。。。。

附件：约瑟夫算法（其中有两个cpp文件，1.cpp是正常的，flash.cpp是有趣的。。。。）

2016-10-29 

一道约瑟夫算法题的简单设计