Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
一种最通常的想法是弄个数组，将每一个位置的值都初始化为1，然后进行遍历，数到m时，将其置为0。遇到为0的就跳过继续向下，到最后一个就循环回来。直到只剩一个元素为止。
数组的实现方法：
#include <stdio.h>
#include <malloc.h>
#define n 1000000
#define m 4
int main()
{
int flag, i, j = 0;
int k=0;
int list[n];
int arr[n];
for (i = 0; i < n; i++){
arr[i] = 1;
}
for (i = 1; i < n; i++)
{
flag = 0;
while (flag < m)
{
if (j == n) j = 0; //到了末尾就循环
if (arr[j]){ //当为1时记录经过的个数，0时跳过
flag++;
}
j++;
}
arr[j - 1] = 0; //删除出队的数据
list[k] = j; //将数据存入结果数组中
k++;
}
list[k]=j-1; //存入最后一个数
/*
for(i=0;i<n;i++){
printf(" %d ",list[i]);
}
*/
printf("\n");
}
当数据为1000000时，Fedora 测试时间为real 0m0.270s
或者采用循环链表，即数到了就删除一个节点。直到只剩一个节点为止。虽然指针的操作比数组要慢，但是随着程序的循环进行，链表中的元素越来越少，遍历的数据量也就相应的减少了。
链表实现方法：
#include<stdio.h>
#include<stdlib.h>
#define N 1000000
#define M 4
typedef struct node{
int id;
struct node* next;
}node;
int main(){
int i=1;
node *pre=NULL;
node *head;
int list[N];
for(i;i<=N;i++){ //队列的初始化
node *n=(node*)malloc(sizeof(node));
n->id=i;
if(pre){
pre->next=n;
}else{
head=n; //第一个元素
}
pre=n;
}
pre->next = head; //循环队列
int j=0;
node *p=head;
node *q=p;
while(p->next != p){
for(i=1;i<M;i++){ //向后数M个
q=p;
p=p->next;
}
q->next = p->next; //删除节点
list[j]=p->id; //记录结果
j++;
free(p);
p=q->next; //找回P的位置
}
list[j]=p->id; //最后一个数据
/*
for(j=0;j<N;j++){
printf(" %d ",list[j]);
}
*/
printf("\n");
}
非常巧的是，这种算法在数据达到100万的时候正好与数组的算法效率相当。Fedora测试耗时real 0m0.276s
这里要介绍的一种优化了的方法，既能达到数组的访问速度，又能像链表一样有选择性的遍历。
大体的逻辑是这样的：要想要数组的访问速度，存储结构必然是数组。链表的特性是存储了下一个数据的指针。所以就想到在数组中存储下一个数据的位置。访问时，数组中的内容作为下一个数据的地址。想要修改“链表”的格式，只修改数据内容就行了。这就实现了跳跃有选择的访问。
#include<stdio.h>
#include<stdlib.h>
#define N 1000000
#define M 4
int main(){
int a[N];
int i,j=0,k=0;
int list[N];
for(i=0;i<N;i++){
a[i]=i+1; //每一个位置的内容是下一个位置
}
a[9]=0; //最后一个要指回来
while(j != a[j]){ //位置和内容一致了就是剩下最后一个了
for(i=1;i<M;i++){
j=a[j]; //通过访问数组值的方式访问数组
}
list[k]=a[j]; //记录数据
k++;
a[j]=a[a[j]]; //相当于循环队列中的删除节点
}
list[k]=a[j]; //记录最后一个
/*
for(i=0;i<N;i++){
if(list[i] == 0){
list[i]=N; //因为是循环的所以最后一个数据为N，而不是地址0
}
printf(" %d ",list[i]);
}
*/
printf("\n");
}
应用这种数据结构，程序的访问速度就快的多了。当数据为100万时，测试耗时仅：real 0m0.026s 与前两种方法差出几乎十倍！
本篇博客出自 阿修罗道，转载请注明出处：http://blog.csdn.net/fansongy/article/details/6882586