请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);
  }

温馨提示:答案为网友推荐,仅供参考
第1个回答  2013-10-18
假设N=13,第一圈报数的情况是123 123 123 123 1,所以退出的是3,6,9,12,
然后剩下124578 10 11 13,继续报数,这个时候 因为13号刚抱完1,所以1号开始报2,然后接着报数,报道3的就退出,这样循环,直到最后一个人

相关了解……

你可能感兴趣的内容

本站内容来自于网友发表,不代表本站立场,仅表示其个人看法,不对其真实性、正确性、有效性作任何的担保
相关事宜请发邮件给我们
© 非常风气网