约瑟夫问题又称为“约瑟夫置换”或者“约瑟夫环”，是一个出现在计算机科学和数学中的问题
历史背景：
版本一：这个问题是以[弗拉维奥·约瑟夫]命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个
版本二：Josephus有过的故事：39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏
【ps：发现了数据结构&算法何其伟大，关乎到生死存亡呀哈哈哈】
应用问题转化：
【N个人围绕在一个圆桌子上玩报数游戏，报到N这个数字，淘汰，然后从下一个人继续开始报数，报到N淘汰，循环下去，最后剩余2个人，也
可以循环，最终只会有一个人胜出】
言归正传：怎么使用循环链表来描述这个问题？可直接参考如下代码
/*****************************************循环链表*******************************************/
void circularLinkedList(int M,int N){
PersonListNode *head = (PersonListNode *)malloc(sizeof(PersonListNode));//定义一个头结点
head ->next = head;
head ->num = 1;
PersonListNode *temp = head; //将头结点复制给temp
for (int i = 2; i<= N; i++) {//构建循环链表，
temp ->next = (PersonListNode *)malloc(sizeof(PersonListNode)); // 当i=2时，temp->next为开始结点，也就是头结点的下一个结点
temp = temp->next; // 当i=2时，将开始结点赋值给temp
temp->num = i;
temp->next = head; // 将当前结点指向头结点，循环结束时，temp指向的是尾结点
}
while (temp != temp ->next) {//循环开始时，temp指向的是尾结点
for (int j=1; j<M; j++) {
temp =temp->next;//此时在M的间隔中间，只需要完成结点替代、遍历
}
//执行完for时就说明此时j=M，该俘虏需要自杀，for循环执行完，当前temp的下一个人就是目标俘虏
PersonListNode *targetPersonNode = temp->next;
cout<<"编号为"<<targetPersonNode->num<<"的俘虏自杀"<< endl;
//此时需要将自杀俘虏之后俘虏与自杀俘虏之前的俘虏进行关联，此时的temp为自杀前一个俘虏的结点
temp->next = temp->next->next;
free(targetPersonNode);//将当前自杀的俘虏移除，重新来过
}
cout<<"此时胜出俘虏编号为"<< temp->num<<endl;
}
int main()
{
int M,N;//M 规则（隔M个数） N 人数（N个人）
cout << "输入俘虏人数N " <<endl;
cin >> N;
cout << "输入规则M间隔数"<<endl;
cin >> M;
//单链表实现思路[目前有点问题，待完善]
// singleLinkedList(M, N);
//循环链表实现思路。M为3 N为8 此时7号俘虏胜出
circularLinkedList(M,N);
return 0;
}
待完善【单链表解法、数组解法 及其对比】
网友评论