作业帮 > 综合 > 作业

请C语言高手讲解下我问的这题比较笨的问题.

来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/10/06 22:46:48
请C语言高手讲解下我问的这题比较笨的问题.
有n人围成一圈,顺序排号,从第1个人开始报数(从1到3)报数,凡报到3的人,退出圈子.问最后留下的是原来的第几号的那位.我用数字试验了下,感觉不懂、、、
/*约瑟夫环的故事 
 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏.
 解决问题的核心步骤:(程序的基本算法)
  1.建立一个具有n个链结点,无头结点的循环链表;
  2.确定第1个报数人的位置;
  3.不断地从链表中删除链结点,直到链表为空.*/
  void JOSEPHUS(int n,int k,int m) //n为总人数,k为第一个开始报数的人,m为出列者喊到的数
  {
  /* p为当前结点 r为辅助结点,指向p的前驱结点 list为头节点*/
  LinkList p,r,list; /*建立循环链表*/
  for(int i=0;i<n;i++)
  {
  p=(LinkList)malloc(sizeof(LNode));
  p->data=i;
  if(list==NULL)
  list=p;
  else
  r->link=p;
  r=p;
  }
  p->link=list; /*使链表循环起来*/
  p=list; /*使p指向头节点*/
  /*把当前指针移动到第一个报数的人*/
  for(i=0;i<k;i++)
  {
  r=p;
  p=p->link;
  }
  /*循环地删除队列结点*/
  while(p->link!=p)
  {
  for(i=0;i<m-1;i++)
  {
  r=p;
  p=p->link;
  }
  r->link=p->link;
  printf("被删除的元素:%4d ",p->data);
  free(p);
  }