題目描述

約瑟夫問題是一個經典的問題，我們不妨將這個經典問題進行擴展，變成一個雙向的約瑟夫問題。

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