据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus和他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。请你编写一个函数,计算一下Josephus 和他的朋友应该安排在什么位置,才能免于一死(最后剩下他们两人)。
要求人的总数与报数均由键盘输入,不能指定成41和3。
程序输入:
由用户输入总人数n(2<n<1000)与报数值m(2<m<=n),分两次完成输入,输入的值均为大于2的整数,输入时要有提示信息。
要求将求最后剩余人的方法封装成一个函数,p为一维数组,n为总人数,m 为报数,函数头为void josephus(int * p, const int n, const int m);,在此函数中求最终幸存者的位置编号并进行打印(位置编号从1开始),请实现josephus函数。
程序输出:
输出最后剩余人的号码。
输入示例:
请输入人的总数:41
请输入报数值:3
输出示例:
Josephus 和他的朋友的位置:16 31
解题提示:
1、可以使用数组表示所有人,数组元素值为零,就表示人未出局,如果出局对应值为1,数组下标可以表示人的编号(编号=下标+1)。数组里最后为0的元素所对应的下标+1就应该是Josephus 和他的朋友的位置。
(选择使用,可以不使用) 数组可以使用calloc函数进行分配内存,例如。用户输入的总人数为n,则可使用 int * arr = (int *)calloc(n, sizeof(int));在堆区分配一块内存,指针arr当做数组来使用。推荐使用calloc函数,因为calloc函数在分配完内存之后会对内存做置0操作,相当于arr里每一个元素均设置为0;而malloc函数则不会进行置0操作。使用calloc函数前需包含 stdlib.h 头文件。
2、总人数为41,报数值为3时,出列顺序为:

3、main函数中的参考代码:
int main(void)
{
int * arr;
int n, m;
printf("请输入人的总数:");
scanf("%d", &n);
printf("请输入报数值:");
scanf("%d", &m);
arr = (int *)calloc(n, sizeof(int));
josephus(arr, n, m);
free(arr);
return 0;
}