使用双向循环链表解决 约瑟夫环问题-数据结构和算法

硅谷探秘者 751 0 0
约瑟夫环问题描述

        有m个人,围成一个环,编号为 1、2、3、、、m,从第一个人开始循环报数(从1开始数),假设数到n的那个人出局,然后从下一个人继续数数(从1开始数),数到n出列,以此循环,最后那个人为胜利者,求胜利者的编号,以及出局者的顺序。

解决方案

        使用双向循环链表

        测试数据 m=9,n=5

        输出:5 1 7 4 3 6 9 2 8

代码(c++描述) 

Node.h

#pragma once
class Node
{
public:
	int index;
	Node * prve;
	Node * next;
	Node(int index);
	~Node();
};

CircularList.h

#pragma once
#include "Node.h"
class CircularList
{
public:
	Node * root;//头节点
	Node * last;//尾节点
	int size=0;
	CircularList();
	~CircularList();

	void addNode(int num);//添加 num 个节点,编号为(0-num)
	Node * removeNode(Node * n);//删除节点
	void prinft();//打印节点

	int begin(int n);

};

Node.cpp

#include "Node.h"
#include <iostream>
Node::Node(int index)
{
	this->next = NULL;
	this->index = index;
}
Node::~Node()
{
}

CircularList.cpp

#include "CircularList.h"
#include "Node.h"
#include <iostream>
using namespace std;
//构造函数
CircularList::CircularList()
{
}
//析构函数
CircularList::~CircularList()
{
}
//添加节点
void CircularList::addNode(int num)
{
	root = new Node(1);
	last = root;
	for (int i=2;i<=num;i++)
	{
		Node * n = new Node(i);
		last->next = n;
		n->prve = last;
		last = n;
	}
	size = num;
}
//打印节点
void CircularList::prinft()
{
	Node * n = root;
	while (n != NULL)
	{
		cout << n->index << "\t";
		n = n->next;
	}
	cout << endl;
}
//删除节点
Node * CircularList::removeNode(Node * n)
{
	Node * node = n->next;
	n->prve->next = node;
	node->prve = n->prve;
	n->next = NULL;
	n->prve = NULL;
	cout << n->index<<" ";
	delete(n);
	size--;
	return node;
}

//找出最后一个节点
int CircularList::begin(int n)
{
	cout << "出局人的顺序是:" << endl;
	//形成循环链表
	if (last == NULL) 
	{
		return -1;
	}
	else 
	{
		last->next = root;
		root->prve = last;
	}
	int i = 1;//当前数字
	Node * node = root;//当前节点
	while (size>1)
	{
		if (i==n)
		{
			i = 1;
			node = removeNode(node);
		}
		else 
		{
			i++;
			node = node->next;
		}
	}
	cout << node->index << endl;
	return node->index;
}

Test.cpp

#include <iostream>
#include "CircularList.h"

void main()
{
	CircularList * c = new CircularList();
	c->addNode(9);//人数(编号从1开始)
	c->begin(5);//数到5的人删除(从1开始)
	system("pause");
}

猜你喜欢
数据结构与算法 9485 :如上图的一个,如何判断一个中是否存在,以及如何求出的入口以及何如求出的长度。方案一:利hash首先准备一个hash如hashMap等,然后从头部遍历,每次遍历一个
数据结构与算法 934 代码:组a是未排序集合,已排序的集合是逻辑上的一个集合,可以看作是head,实现是一个,add方集合添加,每次找到对应的位置,使有序,toArray方使已排序的集合输出成int
前端(h5) 841 h2h1----h2--------h3h1----h3----h2--------h42.案例如图:本文就介绍如何使js设计,巧妙利实现将顺序的目录,转换成树状目录。3.js代码scr
数据结构与算法 11454 -图的着色描述:图的m-着色判定——给定无连通图Gm种不同的颜色。这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色使G中任意相邻的2个顶点着不同颜色?个人感
weblog 1664 vue使v-model(绑定)自动收集!DOCTYPEhtmlhtml head metacharset="UTF-8" title/title scriptsrc="js
数据结构与算法 910 原文接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂度 空间复杂度基础 线性(必学) (必学
数据结构与算法 808 prim(普里姆)求出。对于任何一个,理实现只是一个方面,更重要的是要明白它的应范围或应场景,最小生成树的应非常广泛,例如:假设要在n个城市之间建立通信联络网,则连接n个
数据结构与算法 1379 广度优先搜索(dfs、深搜)java实现-邻接矩阵示图的定点之间的关系如下图的:则邻接矩阵示为: privatestaticintmap[][]={ {0,3,6
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio
目录
祝愿神州十三飞行乘组平安归来