约瑟夫环问题:
在一间房间总共有n个人(下标0~n-1),只能有最后一个人活命。
按照如下规则去杀人:
- 所有人围成一圈
- 顺时针报数,每次报到q的人将被杀掉
- 被杀掉的人将从房间内被移走
- 然后从被杀掉的下一个人重新报数,继续报q,再清除,直到剩余一人
- 要求模拟这个问题
#include<stdio.h>
#include<malloc.h> void Joseph(int count,int doom); void Joseph(int count,int doom){
int alive = count; //幸存人数;
int curIndex = 0; //当前下标;
int preIndex = count -1; //前一个人下标;
int index;
int *circle = NULL; circle = (int *)malloc(sizeof(int) * count);
for(index = 0;index < count; index++){
circle[index] = (index + 1) % count; //初始化链表;
}
while(alive > 0){
int num = doom % alive -1; //直接计算出需要移动的人数,定位要出圈的人;
for(index = 0; index < (num == -1 ? alive - 1 : num);index++){
preIndex = curIndex;
curIndex = circle[curIndex]; //该人出圈;
//curIndex++;
}
printf("%d\n",curIndex + 1);
alive--;
circle[preIndex] = circle[curIndex]; //真正的出圈操作;
curIndex = circle[curIndex]; //继续处理下一个人; }
free(circle);
} int main(){
int count;
int doom; printf("请输入总人数,厄运数 :");
scanf("%d%d",&count,&doom);
Joseph(count,doom); return 0;
}