约瑟夫环描述：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

举例：　n = 9, k = 1, m = 5

【解答】出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。

该过程可以用循环链表的方法模拟实现，不是此文的重点，不给出代码实现。

网上有人给出了约瑟夫环的数学方法，但看它的叙述让人很费解，现给出本人的描述：

撇开题目，n个人编号0,1,2,...,n-1，游戏进行一轮踢出1位同学(m-1)，剩n-1人(编号0,1,2,...,m-2,m,...,n-1)，对n-1人重新排队得(m,...,n-1,0,1,2,...,m-2)，对这n-1人重新“标”号(0,1,2,...,n-2)，好了，现在可以进行假设，现假设n-1人进行n-2次踢人后得到的最后胜利者的"标"号为x，那么请问他在上次n人游戏时的“编”号x'是多少？

这就是对应了，我们根据上段的描述可以得出：(标号+m)%n=编号，故x'=(x+m)%n

推广开了，得n人游戏的最后胜利者是f[n]=(f[n-1]+m)%n; (n>1)和f[1]=0;　　　　　　　　　　

注意别忘了在得到结果后要+1还原，因为编号是从0开始，而题目描述是从1开始。　　　　　　　　　　　　.#

现给出几点说明：

1.该数学方法没有参数k，前提是假定从0编号的人开始喊1（其实这个无关紧要，还原时+k就可以）；

2.该数学方法只求出了最后胜利者，即冠军，但亚军季军还须另外想办法，所以用循环链表模拟还是具有其优势的。

3.给出n=1:9且m=5的结果做参考（别忘了+1还原哦）

　　0　　1　　0　　1　　1　　0　　5　　2　　7

【参考文献】http://baike.baidu.com/view/717633.htm

-----------------------------------------------------------------------------------------

循环链表实现之——

#include <iostream>

using namespace std;

struct CLNode

{

    int data;

    CLNode *pnext;

};

CLNode* CreateCList(int n)//创建n个人的循环链表

{

    if(n<1)return NULL;

    int i=0;

    CLNode* head=new CLNode;//辅助头结点

    CLNode* ppre=head;

    CLNode* pcur=NULL;

    while (i<n)

    {

        pcur=new CLNode;

        pcur->data=++i;

        pcur->pnext=NULL;

        ppre->pnext=pcur;

        ppre=pcur;

    }

    pcur->pnext=head->pnext;

    pcur=head->pnext;

    delete head;//删除辅助头结点

    return pcur;

}

int Josephus(CLNode* head,int k,int m)//从k开始报数，报数为m的出局

{

    int winner=0;

    if(head->pnext==head){winner=head->data;delete head;return winner;}//n=1的情况

    int i=1;

    CLNode *pcur=head;

    CLNode *ppre=head;

    while(ppre->pnext!=head){//找出head的前一个结点，即尾结点，用ppre指向该结点

        ppre=ppre->pnext;

    }

    while(1){//找到第k个人，以便开始报数

        if(i==k)break;

        pcur=pcur->pnext;

        ppre=ppre->pnext;

        i++;

    }

    while(1){

        i=1;

        if(pcur->pnext==pcur){winner=pcur->data;delete pcur;return winner;}//被删除得只剩下一个结点时，就是最后胜利者

        while(1){

            if(i==m)break;//找到报m数的人，用pcur指向该结点

            pcur=pcur->pnext;

            ppre=ppre->pnext;

            i++;

        }

        ppre->pnext=pcur->pnext;

        cout<<pcur->data<<" ";//打印被删除结点的值

        delete pcur;

        pcur=ppre->pnext;

    }

}

void main()

{

    int n=1,k=1,m=5;

    while(n<=9){

        /*cout<<"n=";

        cin>>n;   

        cout<<"k=";

        cin>>k;

        cout<<"m=";

        cin>>m;*/

        cout<<"n="<<n<<"    ";

        CLNode* head=CreateCList(n);

        cout<<Josephus(head,k,m)<<endl;        //输出最后胜利者

        n++;

    }

}

输出：

n=1     1

n=2     1 2

n=3     2 3 1

n=4     1 3 4 2

n=5     5 1 3 4 2

n=6     5 4 6 2 3 1

n=7     5 3 2 4 7 1 6

n=8     5 2 8 7 1 4 6 3

n=9     5 1 7 4 3 6 9 2 8

请按任意键继续. . .