约瑟夫环问题代码示例

约瑟夫环问题

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。->摘自百度百科

那么约瑟夫环是怎么实现的呢,毋庸置疑,循环链表

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
  int data;
  struct node* next;
}node;

node *create(int n)
{
 node *p=NULL,*head;
 head=(node*)malloc(sizeof(node));
 p=head;
 node *s;
 int i=1;
 if(n!=0)
 {
   while(i<=n)
   {
     s=(node*)malloc(sizeof(node));
     s->data=i++;
     p->next=s;
     p=s;
   }
   s->next=head->next;
 }
 free(head);
 return s->next;
}
int main(void)
{
 int n=41;
 int m=3;
 int i;
 node *p=create(n);
 node *temp;
 m%=n;
 while(p!=p->next)
 {
   for(i=1;i<m-1;i++)
   {
     p=p->next;
   }
   printf("%d->",p->next->data);
   temp=p->next;
   p->next=temp->next;
   free(temp);
   p=p->next;
 }
 printf("%d\n",p->data);
 return 0;
}

然后让我们来看看相似的题
编号为1~N的N个人按照顺时针方向围坐一圈,每人持有一个密码(正整数,可以*输入),开始人选一个正整数作为报数上限M,从第一个人按照顺时针方向自1开始顺序报数,报道M时停止报数,报M的人出列,将他的密码作为新的M值,从他顺时针方向上的下一个人开始从1报数,如此下去,直至所有人全部出列为止

以下是代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct node
{
  int num;
  int code;
  struct node *next;
}node;

node *create(int n)  //创建一个n个数据元素的循环链表
{
  node *p=NULL,*head;
  head=(node*)malloc(sizeof(node)); //创建一个头节点
  p=head;          //将p指向头节点
  if(p==NULL)    //如果头节点创建失败
  {
    return 0;
  }
  /*生成一组随机数存储密码的值*/
  time_t ts;
  srand((unsigned int)time(&ts)); //生成随机数种子
  node *s;
  if(n!=0)
  {
     for(int i=1;i<=n;i++)
     {
       s=(node*)malloc(sizeof(node));   //生成一个新的节点
       s->num=i;         //每个节点编号
       s->code=rand()%11+1;     //随机生成每个人的密码
       p->next=s;      //第一次使头节点指向s,之后使上一个数据元素指向节点s
       p=s;          //使p的位置后移
     }
     s->next=head->next;
     free(head);
  }
  return s->next;
}
int main(void)
{
  int n;
  int m;
  printf("\n--------------------------------------\n");
  printf("        请输入有几个人参加游戏:         \n");
  scanf("%d",&n);
  node *p=create(n);     //生成一个循环链表
  node *temp;              //声明一个临时变量作为交换
  while(p->next!=p)
  {
    m=p->code;
    m%=n;
    for(int i=1;i<m-1;i++)
    {
      p=p->next;            //使p指向出列数据的上一个数据元素
    }
    printf("%d>>",p->next->num);    //打印出列人的编号
    temp=p->next;
    p->next=temp->next;
    free(temp);
    p=p->next;
  }
  printf("%d\n",p->num);    //打印最后一个人的编号
  return 0;
}    

下面是代码运行情况