本文主要是介绍数据结构与算法 约瑟夫环问题 Josephus问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
有 n 个人围成一个圈，从第 k 个人开始从 1 开始一个人一个人的报数，数到第 m 个人，让他出列；然后从出列的下一个人重新开始报数，数到第 m 个人，再让他出列，……，如此反复直到圆圈中只剩一个人为止，请模拟这一工作过程。即已知：人数 n，初始编号 k，出列值 m，而且每次的 m 值都不一样；输出整个过程中，出列编号的序列 L，以及最后留下的元素位置。建立一个无头结点的单向循环链表，定义指针pPer指向第一个结点，指针pFront指向出列的前一个结点，这是为了在出列的结点被删除（delete）后，能够将前后两个结点连接起来。
/**************************************
Exp_1：Josephus Problem
Author：Shawn__L
Date：2018.5.20
**************************************/
#include "stdafx.h"
#include<iostream>
using namespace std; int m,n;
typedef struct Person
{ int k; //编号 int m; //密码 Person *next;
}Person; Person * pPer = NULL; //pPer指向第一个结点，此链表没有头节点
Person * pFront = NULL; //pFront指向出列的前一个结点void init() //初始化函数
{ Person *temp; Person *p; cout << "请输入人数："; cin >> n; cout<<endl;temp = new Person; cout << "请输入第1个人的密码："; cin >> temp->m; temp->k = 1; pPer = temp; p = temp; for (int i = 2; i <= n; i++) { temp = new Person; cout << "请输入第" << i << "个人的密码："; cin >> temp->m; temp->k = i; p->next = temp; p = temp; } temp->next = pPer; //首尾相连 pFront = temp; //考虑m=1的情况 cout<<endl;
} void Josephus(int n) //Josephus问题计算函数
{ int count=1;if (n == 1) {cout<<"\n\n"<<"剩下的最后一个结点为："<<pPer->k;return; } Person *p; //指向出列结点，以便delete p; for( ;count != m;count++) { pPer = pPer->next; pFront = pFront->next; //pPer移动,pFront就要移动，保持在出列结点的前一个结点 } p = pPer; //此时pPer指向出列结点，p用来释放出列者的内存 m = pPer->m; pFront->next = pPer->next; cout << pPer->k << " "; pPer = pPer->next; //pPer的位置即将释放，pPer应该指向下一个位置 delete p; Josephus(n-1);
} int main() //主函数
{ cout << "请输入第一轮m的值："; cin >> m; cout<<endl;init(); cout << "出列顺序为："; Josephus(n); cout<<"\n\n";return 0;
} 这篇关于数据结构与算法 约瑟夫环问题 Josephus问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
