约瑟夫环问题

已知 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;
}