利用双向循环链表实现约瑟夫环问题(C++版)

素颜马尾好姑娘i 2022-04-03 11:18 269阅读 0赞

1.问题简述

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

2.实现思路

(1)建立一个孩子类(相当于数据结构中的结点),在类中定义数据域孩子的编号和左右指针.

(2)建立一个圆桌类,类中定义参与游戏的人数和孩子类数组,并在构造方法中初始化孩子类数组.定义构建双向循环链表的方法Bulid(),

注意在此方法中要单独考虑第一个孩子结点和最后一个孩子节点(即头节点和尾节点).然后定义删除结点的方法Run(),也是游戏运行的方法.

(3)定义main()方法,实现约瑟夫环(开始可以定义人数比较少,方便调试).

3.代码

#include <iostream>
    using namespace  std;
    
    //1.定义小朋友节点类
    class Child
    {
    
    public:
    	int childNo;         //当前小孩的编号
    	Child* leftchild;    //记录小孩对象的左邻居
    	Child* rightchild;   //记录小孩对象的右邻居
    
    
    public:
    	//构造函数
    	Child(int num = 0)
    	{
    		childNo = num;
    		leftchild = NULL;
    		rightchild = NULL;
    	}
    
    };
    
    //2.定义圆圈游戏类
    class Circle
    {
    public:
    	int scale;  //当前正在参与游戏的人数
    	Child children[1000];
    
    public:
    	// 构造函数：初始化每个小孩对象节点的编号
    	Circle(int num = 1000)
    	{
    		scale = num;
    
    
    		for (int i = 0; i < num; i++)
    		{
    			children[i] = Child(i);
    		}
    	};
    
    	//构建节点的循环链表函数：确立每个小孩的左右邻居
    	void Build()
    	{
    		for (int i = 0; i < scale; i++)
    		{
    			if (i == 0)
    			{
    				children[i].rightchild = &children[1];
    				children[i].leftchild = &children[scale - 1];
    			}
    			else if (i == (scale - 1))
    			{
    				children[i].rightchild = &children[0];
    				children[i].leftchild = &children[scale - 2];
    			}
    			else
    			{
    				children[i].rightchild = &children[i + 1];
    				children[i].leftchild = &children[i - 1];
    			}
    		}
    
    	}
    	//游戏运行函数：从当前节点顺时针循环开始数num个数
    	void Run(int T)
    	{
    		int count = 1;
    		Child* current = &children[0];
    		while (scale > 1)
    		{
    			//quit the circle
    			if (count == T)
    			{
    				// 当前数到T的小孩退出游戏，参与游戏人数减少1个
    				scale = scale - 1;
    
    				//把当前的这个小孩的左右邻居用链表连接起来(相当于删除改结点)
    				current->leftchild->rightchild = current->rightchild;
    				current->rightchild->leftchild = current->leftchild;
    				current = current->rightchild;
    				count = 1;
    			}
    			else  //count the next	            		
    			{
    				count = count + 1;
    				current = current->rightchild;
    			}
    
    		}
    
    		//打印最后一个小孩的编号
    		cout << "The last child id is " << current->childNo << endl;
    	}
    };
    
    int main()
    {
    
    	Circle nodes(5); // 圆圈类内有100个节点对象（小孩）
    
    	nodes.Build();
    
    	nodes.Run(3);     // 开始循环运行数“7”的游戏，输出最后的获胜者
    
    	system("pause");
    	return 0;
    
    }