Question

一个有关c++约瑟夫环的问题

急！！约瑟夫环的实现过程谁能详细解说一下 尤其是求余的那一步一直没弄懂 求余的作用是什么 拜托各位谁能给一个详细的解释 百度百科就算了 里面的数学方法我看过了 还是没弄懂为何要求余 本人刚接触c++ 各位多担待
#include<stdio.h>
int main()
{ int n,k,s=1;
scanf("%d%d",&n,&k);
for(i=2;i<=n;i+=1)
{
s=(s+k)%i;
if(s==0)s=i;
}
printf("ans=%d\n",s);
return 0;
}
能不能解释一下这个里面的求余

Answer 1

求余是因为他是个环形的数到最后时又从头开始
比如说现在是1-5 5个人 1号开始报数如果它报5以内的没问题你直接加就行了
但是报5以上的就不行了比如说6直接数是数不到的 实际中因为是环形坐的其实1和6是同一个人 也就是说他按5为周期重复的 求余就是为了排除周期的影响直接定位

解决问题的核心步骤：
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;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被删除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最后被删除的元素是：％4d",P->data);
}