一个很有趣的算法题
Josephus有过的故事：39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
虽然这个故事很扯淡→_→......但是其中的算法思维却值得我们深入的思考
这个故事可以简化成一个非常经典的数学的应用问题：就是已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。开始从编号为k的人报数，数到数字为m的那个人出列；继续，他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
这是一个典型的循环链表题目。我们需要创建一个循环链表，依照游戏规则，依次进行删除结点操作。直至链表为空，打印出的元素顺序即为出局顺序。
大概的思路就是：
建立一个具有n个链结点，无头结点的循环链表；确定第1个报数人的位置；不断地从链表中删除链结点，直到链表为空。
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
void JosephRing(int len, int doom){
int alive = len;
int num = 0; //计数，当num==doom时，淘汰这个人
int index = 0;
int arr = (int )calloc(sizeof(int) , len);
memset(arr, 0, sizeof(int) * len); //index 0代表在圈里 1代表被淘汰
while(alive > 0){
if(0 == arr[index]){
num++;
// printf("num = %d, %d, %dn", num, index, arr[index]);
}
if(num == doom && arr[index] == 0){
alive--;
arr[index] = 1;
printf("kill %dn", index);
num = 0;
// int k = 0;
// for(k = 0; k < 50; k++){
// printf(" %d ", arr[k]);
// }
// printf("n");
}
index++;
index = index % len;
}
free(arr);
}
int main(char argc, char *argv){
JosephRing(100, 15);
}