一群小孩围成一圈，每个小孩都会带有一个随机的密码。然后设定一个数m，从第一个小孩数起，数到第m个的时候，该小孩离开。小孩离开时，其携带的密码将更新这个m值，顺序往下数的第m个小孩会继续出列。依次这样数下去，最后一个小孩是胜利者，问：胜利者是第几个小孩？

这就是大家所熟知的约瑟夫环。

单循环链表天然地很适合解决这个问题，下面用C语言实现了一下：

#include
#include
#include
#define OK 1;
#define ERROR 0;
#define OVERFLOW -2;

typedef int ElemType;
typedef struct Node
{
    ElemType num;
    ElemType password;
    struct Node *next;
}Node;
typedef struct Node CLinkList; /* 定义LinkList */

void main(){
	int num=10;
	int m=10;
	CLinkList *L;
	/* 输入约瑟夫环的总结点数*/
	printf("有多少个小孩参与游戏(设定小于100):");
	scanf("%d",&num);
	if(num=100){
	    /* 如果输入的数字超出范围，就默认总结点数为10 */
	    printf("你的输入不符合，下面采用默认数字10\n");
	    num=10;
	}
	/* 输入第一个需要出列的数字 */
	printf("第一个报到哪个数必须出列 (设定小于100):");
	scanf("%d",&m);
	if(m=100){
	    printf("你的输入不符合，下面采用默认数字10\n");
	    m=10;
	}
    InitList(L);
    Creat_Joseph(L,num);
    ListTraverse(L,num);
	Joseph_Run(L,m);
}

/* 释放删除的结点 */
void FreeNode(CLinkList *p){
	CLinkList *temp=p;
	while(temp->next!=p)
		temp=temp->next;
	temp->next=p->next;
	printf("编号%3d的小孩离队了，他携带的密码是%3d\n",p->num, p->password);
	free(p);
}

/* 初始化结点 */
int InitList(CLinkList *l){
	l=(CLinkList *) malloc (sizeof(CLinkList));
	if(!l)
		return OVERFLOW;
	return OK;
}
/* 创建每个结点携带的密码 */
void Creat_Joseph(CLinkList *l,int length){
	int i;
	CLinkList *p=l;
	l->next=l;
	l->num=1;
	srand( (unsigned)time(NULL));
	l->password=rand()%(length+3)+1;
	printf("以下小孩（约瑟夫环结点）携带的密码随机生成的:\n");
	/* 打印约瑟夫环的第一个结点 */
	printf("小孩编号: %3d      带的密码: %3d\n",l->num,l->password);
	for(i=1;inext=temp;
		temp->next=l;
		temp->num=i+1;
		temp->password=rand()%(2*length)+1;
		/* 打印除第一个结点外的其它结点 */
		printf("小孩编号: %3d      带的密码: %3d\n",temp->num,temp->password);
		p=p->next;
	}
}

void ListTraverse(CLinkList *L,int length)
{
    int i;
    CLinkList *p=L->next;
    for(i = 0; i < length; i++)     {         printf("%d:%d ",p->num, p->password);
        p=p->next;
    }
    printf("\n");
    return OK;
}

/* 根据结点携带的密码释放下一个结点 */
void Joseph_Run(CLinkList *l, int m){
    int i,k;
    CLinkList *temp,*p;
	if(l->next==l)
        /* 打印最后一个结点 */
		printf("最后编号 %d 的小孩获胜！",l->num);
	else{
		temp = l;
		for(i=1; inum);
		    temp=temp->next;
		}
		p=temp->next;
		k=temp->password;
		/* 释放中招的结点 */
		FreeNode(temp);
		/* 递归 */
		Joseph_Run(p,k);
	}
}

程序运行结果：

有多少个小孩参与游戏(设定小于100):6
第一个报到哪个数必须出列 (设定小于100):8
以下小孩（约瑟夫环结点）携带的密码随机生成的:
小孩编号:   1      带的密码:   5
小孩编号:   2      带的密码:   9
小孩编号:   3      带的密码:  12
小孩编号:   4      带的密码:   2
小孩编号:   5      带的密码:   5
小孩编号:   6      带的密码:   2
2:9 3:12 4:2 5:5 6:2 1:5
编号  1的小孩安全
编号  2的小孩安全
编号  3的小孩安全
编号  4的小孩安全
编号  5的小孩安全
编号  6的小孩安全
编号  1的小孩安全
编号  2的小孩离队了，他携带的密码是  9
编号  3的小孩安全
编号  4的小孩安全
编号  5的小孩安全
编号  6的小孩安全
编号  1的小孩安全
编号  3的小孩安全
编号  4的小孩安全
编号  5的小孩安全
编号  6的小孩离队了，他携带的密码是  2
编号  1的小孩安全
编号  3的小孩离队了，他携带的密码是 12
编号  4的小孩安全
编号  5的小孩安全
编号  1的小孩安全
编号  4的小孩安全
编号  5的小孩安全
编号  1的小孩安全
编号  4的小孩安全
编号  5的小孩安全
编号  1的小孩安全
编号  4的小孩安全
编号  5的小孩安全
编号  1的小孩离队了，他携带的密码是  5
编号  4的小孩安全
编号  5的小孩安全
编号  4的小孩安全
编号  5的小孩安全
编号  4的小孩离队了，他携带的密码是  2
最后编号 5 的小孩获胜！
Process returned 23 (0x17)   execution time : 8.506 s
Press any key to continue.

以上内容仅供参考，原文来自：http://www.nowamagic.net/librarys/veda/detail/1867