Josephus_problem_bidirectional 双向约瑟夫问题

题目描述

约瑟夫问题是一个经典的问题，我们不妨将这个经典问题进行扩展，变成一个双向的约瑟夫问题。

　　已知 n 个人（不妨分别以编号 1，2，3，...，n 代表 ）围坐在一张圆桌周围，首先从编号为 k 的人从 1 开始顺时针报数，1, 2, 3, ...，记下顺时针数到 m 的那个人，同时从编号为 k 的人开始逆时针报数，1, 2, 3, ...，数到 m 后，两个人同时出列。然后从出列的下一个人又从 1 开始继续进行双向报数，数到 m 的那两个人同时出列，...；。依此重复下去，直到圆桌周围的人全部出列。直到圆桌周围只剩一个人为止。

 　　如果双向报数报到 m 时落在同一个人身上，那本次出列的只有一个人。

　　例如：5,1,2。则总共5个人，从1开始顺时针报数，数到2，定位编号2；同时从1开始报数数到2，定位编号5；2和5同时出列。然后继续开始报数，顺时针报数3,4，定位到4；逆时针报数4,3，定位3；4和3同时出列。最后剩余的为编号1。输出为：2-5,4-3,1,。

　　如果输入：6,2,3。则输出：4-6,2,1-3,5,。其中第2次只输出一个2，表示第二次双向报数时，恰好都落在编号2上，所以只有一个编号出列。

输入：n,k,m

输出：按照出列的顺序依次输出编号。同时出列编号中间用减号"-”连接。

非法输入的对应输出如下

a)

输入：n、k、m任一个为0
输出：n,m,k must bigger than 0.

b)

输入：k>n
输出：k should not bigger than n.

解题思路

这里就需要用到双向循环链表（

struct p {
	int id;
	struct p* prior, * next;
};
struct p first, * ppre = &first, * pnex = (struct p*)malloc(sizeof(struct p));
	first.id = 1;
	first.next = pnex;
	first.prior = NULL;
	struct p* kth=NULL;//kth是第k个人（开始元素）
	if (k == 1) kth = &first;
	for (int i = 1; i < n - 1; i++)
	{
		pnex->id = i + 1;
		if (i + 1 == k)
		{
			kth = pnex;
		}
		pnex->prior = ppre;
		pnex->next = (struct p*)malloc(sizeof(struct p));
		ppre = pnex;
		pnex = pnex->next;
	}
	pnex->id = n;
	if (k == n) kth = pnex;
	pnex->prior = ppre;
	pnex->next = &first;
	first.prior = pnex;//循环

接下来还是一个过程模拟。注意双向之后就会多出几个问题：

（1）怎么判断出圈结束？也就是说有两种出口，要么最后是两人一起出圈，要么只剩一个了。另外由于有两个指针，怎么判断剩余几人？（我采用的是使用一个变量cnt）

（2）输出会不一样，要讨论几个人出圈的问题

（3）怎么去考虑出圈之后剩余元素的连接？

显然需要讨论，建议不要直接上手、先模拟一下，不然很容易出现RE。

我的做法是把两种方向的当前数字的指针命名为f(irst)cur(rent)，s(econd)cur(rent)，有三种情况：

对应的代码分别是：

//同一个数的情况  *1
fcur->next->prior = fcur->prior;
fcur->prior->next = fcur->next;//delete

//两个数的情况
//相邻  *2
if (fcur->next == scur){
	fcur->prior->next = scur->next;
	scur->next->prior = fcur->prior;//delete
}
else if (scur->next==fcur){
	scur->prior->next = fcur->next;
	fcur->next->prior = scur->prior;//delete
}
//不相邻  *3
else{
	fcur->prior->next = fcur->next;
	fcur->next->prior = fcur->prior;

	scur->prior->next = scur->next;
	scur->next->prior = scur->prior;//delete
}

贴源代码

到这里就基本完整了，但诸如在“%d-%d”中始终是由小到大的这个方向的数在前的这些细节可能还需要打磨一下吧。

#include<iostream>
#include<cstdlib> 
using namespace std;

struct p {
	int id;
	struct p* prior, * next;//两个方向
};

int main()
{
	int n, k, m;
	scanf_s("%d%*c%d%*c%d", &n, &k, &m);
	if ((n < 1) || (k < 1) || (m < 1))
	{
		cout << "n,m,k must bigger than 0.\n";
		return 0;
	}
	if (k > n)
	{
		cout << "k should not bigger than n.\n";
		return 0;
	}

	struct p first, * ppre = &first, * pnex = (struct p*)malloc(sizeof(struct p));
	first.id = 1;
	first.next = pnex;
	first.prior = NULL;
	struct p* kth=NULL;
	if (k == 1)
	{
		kth = &first;
	}
	for (int i = 1; i < n - 1; i++)
	{
		pnex->id = i + 1;
		if (i + 1 == k)
		{
			kth = pnex;
		}
		pnex->prior = ppre;
		pnex->next = (struct p*)malloc(sizeof(struct p));
		ppre = pnex;
		pnex = pnex->next;
	}
	pnex->id = n;
	if (k == n)
	{
		kth = pnex;
	}
	pnex->prior = ppre;
	pnex->next = &first;
	first.prior = pnex;
	
	/*cur=&first;
	for(int w=0;w<n+1;w++)
	{
		printf("%d\n",cur->id);
		cur=cur->next;
	}
	cur = &first;
	for (int w = 0; w < n + 1; w++)
	{
		printf("%d\n", cur->id);
		cur = cur->prior;
	}还是为了检验链表的建立*/

	int cnt=n;//用于检测剩余几个数
	struct p *fcur, *scur;
	fcur = scur = kth;
	while (cnt!=2&&cnt!=1)
	{
		for (int i = 1; i <= m - 1; i++)
		{
			fcur = fcur->next;
			scur = scur->prior;
		}//分别步入
		
        if (fcur == scur)
		{
			printf("%d,", fcur->id);
			cnt--;
			fcur->next->prior = fcur->prior;
			fcur->prior->next = fcur->next;//delete
			fcur = fcur->next;
			scur = scur->prior;//next
		}//*1
		else
		{
			printf("%d-%d,", fcur->id, scur->id);
			cnt -= 2;
			if (fcur->next == scur)
			{
				fcur->prior->next = scur->next;
				scur->next->prior = fcur->prior;//delete
				fcur = scur->next;
				scur = fcur->prior;//next
			}
			else if (scur->next==fcur)
			{
				scur->prior->next = fcur->next;
				fcur->next->prior = scur->prior;//delete
				fcur = fcur->next;
				scur = scur->prior;//next
			}//*2
			else
			{
				fcur->prior->next = fcur->next;
				fcur->next->prior = fcur->prior;

				scur->prior->next = scur->next;
				scur->next->prior = scur->prior;//delete

				fcur = fcur->next;
				scur = scur->prior;//next
			}//*3
		}
	}
	if (cnt == 2)
	{
		printf("%d-%d,", fcur->id, scur->id);
	}
	else
	{
		printf("%d,", fcur->id);
	}
	printf("\n");

	return 0;
}

——2022.9.25