【约瑟夫环问题】
已知 n 个人(n>=1)围坐一圆桌周围,从 1 开始顺序编号,从序号为 1 的人开始报数,顺时针数到 m 的那个人出列。下一个人又从 1 开始报数,数到m 的那个人又出列。依此规则重复下去,直到所有人全部出列。请问最后一个出列的人的初始编号。
【要求】
输入人数 n,所报数 m,输出最后一个人的初始编号。
【约瑟夫环问题解决思路】
首先因为是圆桌问题,使用链表解决的话需要构建循环链表。
接着是出列问题,这里我的设计思路是将指向链表的指针移动到需要出列的人的位置,然后根据正常的链表删除进行操作即可。
#include <iostream>
using namespace std;
typedef struct node{
int data;
node * next;
} LNode, *LinkNode; // LNode 定义结构体变量, LinkNode 定义结构体指针
int main()
{
int n, m;
LinkNode head, p, r;
cin >> n >> m;
head = new LNode; // 先给第一个节点申请存储空间
head->data = 1;
head->next = NULL;
r = head;
for(int i=2; i<=n; i++)
{
p = new LNode; // 申请一个新节点
p->data = i;
p->next = NULL; // 后继为空
r->next = p; // 前驱指向当前节点
r = p; // 后移指针,始终保持指向最后一个节点
}
r->next = head; // 首位相连
int num = 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m-2; j++) // 从一循环到m-2,然后指针移到了应当删除节点的前一个
r = r->next;
LinkNode tmp = r->next; // 保存要删除的结点
cout << r->next->data << " "; // 输出
num = r->next->data; // num留到最后输出,输出的是最后一个结点
r->next = r->next->next; // 将要被删除的结点的前后结点相连
r = r->next; // r 后移 从下一个结点开始下一个循环
delete tmp; // 释放删除节点的空间
}
cout << endl;
cout << num << endl;
return 0;
}