著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到剩余一个人为止。一开始要站在什么地方才能避免被处决? 解决思路： 建立一个有40个元素的数组， 将元素的初值赋为1，第一个元素从1开始计数，凡是遇到计数值为3的倍数的元素，将其值赋为0，遍历结束后从数组首元素接着计数......直到数组中只有一个为值1 的元素为止，其下标加1,即为最后幸存者
。
#include <stdio.h>
#define N 41 //总人数
#define NUM 3 //出局的数字
void print (int *a, int n)
{
int i;
for (i = 0;i < n; i++)
{
printf ("-",a[i]);
}
putchar ('\n');
}
/*
将所有人的值编为1，出局的的人编为0，直到只有一个1为止
*/
void Joseph (int *a)
{
int temp = 0; //报数
int count = N; //当前剩余1的数量
while (1)
{
int i;
//遍历报数，超出总人数则第一个人接着报数
for (i = 0;i < N; i++)
{
if (a[i] == 0) //遇到出局的人跳过报数
{
continue;
}
temp++;
if (temp % NUM == 0) //判断是否出局，若出局值编为0
{
count--;
a[i] = 0;
}
}
if (count == 1) //剩余一人结束报数
break;
}
}
int main ()
{
printf ("Function : Joesphus.\n");
int a[N] = {};
int i;
for (i = 0;i < N; i++)
{
a[i] = 1;
}
print (a,sizeof(a)/sizeof(a[0]));
Joseph (a);
print (a,sizeof(a)/sizeof(a[0]));
for (i = 0;i < N; i++)
{
if (a[i] == 1)
{
printf ("Winner is %d !\n", i+1); //数组下标从0开始，所以第n个元素是第n+1个人的序号
}
}
return 0;
}
