qq_54413972
qq_54413972
2021-05-31 16:38
采纳率: 100%
浏览 19

用循环列表求解n=8 k=4的约瑟夫环问题

 

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • technologist_24
    CSDN专家-黄老师 2021-05-31 16:39
    已采纳
    #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;
    
    }
    
    
    
    

    如果对你有帮助,可以点击我这个回答右上方的【采纳】按钮,给我个采纳吗,谢谢

    点赞 评论
  • QA_Assistant
    有问必答小助手 2021-06-01 10:17

    您的问题已经有小伙伴解答了,请点击【采纳】按钮,采纳帮您提供解决思路的答案,给回答的人一些鼓励哦~~

    ps:开通问答VIP,享受5次/月 有问必答服务,了解详情↓↓↓

    【电脑端】戳>>>  https://vip.csdn.net/askvip?utm_source=1146287632
    【APP 】  戳>>>  https://mall.csdn.net/item/52471?utm_source=1146287632

    点赞 评论

相关推荐